How many quadrilaterals formed from n-gon no adjacent sides

[member 428835]

Homework Statement

How many quadrilaterals can be formed from n-polygon (convex) given no adjacent sides of the polygon are used?

Relevant Equations

Nothing comes to mind.

My thought it to think of the orientation as a string: let V denote a selected vertex and E denote a vertex that's not selected. There are then 4 V's to distribute and $n-4$ E's to distribute. Then just choosing quadrilaterals without restriction we have $n!/(4!(n-4)!)$. However, we want no adjacent sides. I'm thinking instead of selecting V,V,V,V we now position VE,VE,VE,VE with the remaining $n-8$ E's going anywhere without restriction. Thus the number of quadrilaters without adjacent sides is $(n-8+4)!/((n-8)!4!)$. Is this correct, or am I missing something?

 

[anuttarasammyak]

I have not investigated your answer but have you checked it for easy primitive cases, n=3,4,5,6 which would confirm/correct your answer ? For n=6 I find three quadrilaterals of such a condition.

 

[haruspex]

I have not investigated your answer but have you checked it for easy primitive cases, n=3,4,5,6 which would confirm/correct your answer ? For n=6 I find three quadrilaterals of such a condition.

Don’t you mean n=8, 9, ...? (I get 2, 18, ...)

 

[anuttarasammyak]

Don’t you mean n=8, 9, ...? (I get 2, 18, ...)

Did I take it wrong ?

 

[haruspex]

Did I take it wrong ?
View attachment 301590

Sorry, I read it as no two adjacent vertices. In my defence, I was influenced by the OP's attempt, which seems to have made the same mistake.

Fwiw, I now get 0, 3, 7, 38 for n=5, 6, 7, 8.

 

[member 428835]

Sorry, I read it as no two adjacent vertices. In my defence, I was influenced by the OP's attempt, which seems to have made the same mistake.

Fwiw, I now get 0, 3, 7, 38 for n=5, 6, 7, 8.

You read it correct. So $n > 8$ to even get a solution. But you say there's a mistake; can you elaborate?

 

[haruspex]

You read it correct.

But it says "adjacent sides". For two adjacent sides to be part of the quadrilateral it would have to use three consecutive vertices, not just two. See the diagram in post #4.

 

[member 428835]

But it says "adjacent sides". For two adjacent sides to be part of the quadrilateral it would have to use three consecutive vertices, not just two. See the diagram in post #4.

Doesn't "no adjacent sides" imply you cannot have adjacent vertices? Diagram in 4 has these, and so is not the description I am looking for.

Example: vertices v1, v2, v3, v4, v5, v6, v7, v8, implies v1,v3,v5,v7 and v2,v4,v6,v8 are the only two solutions, since none of these quadrilateral sides are adjacent with the octogon.

 

[haruspex]

Doesn't "no adjacent sides" imply you cannot have adjacent vertices?

No. Look at e.g. the pink triangle in post #4. It uses two sides of the hexagon, but they are not adjacent in it.
Have you quoted the problem exactly as given to you? If it meant not use any sides of the polygon, why insert the word "adjacent"?

 

[member 428835]

No. Look at e.g. the pink triangle in post #4. It uses two sides of the hexagon, but they are not adjacent in it.
Have you quoted the problem exactly as given to you? If it meant not use any sides of the polygon, why insert the word "adjacent"?

Sorry, by adjacent I should have said "no same side" as the n-gon.

 

[haruspex]

Sorry, by adjacent I should have said "no same side" as the n-gon.

Ok.
I would try using inclusion-exclusion. Are you familiar with that?

 

[member 428835]

Ok.
I would try using inclusion-exclusion. Are you familiar with that?

I am. But I thought my approach was correct?

 

[haruspex]

I am. But I thought my approach was correct?

With n=8 your formula gives 1. Shouldn’t it be 2? For n=9 your formula gives 5, but I count 9.

 

[anuttarasammyak]

Sorry, by adjacent I should have said "no same side" as the n-gon.

On polygon ABCD
a is number of vertexes of n-polygon between A and B
b is number of vertexes of n-polygon between B and C
c is number of vertexes of n-polygon between C and D
d is number of vertexes of n-polygon between D and A
I guess the number of cases satisfying
a+b+c+d=n-4
a,b,c,d $\ge$ 1
multiplied by n/4, which express A is on which vertex and remove count redundancy, would be the answer.


In addition when the condition of "no adjacent sides of n-polygon" is also permitted, the cases of
$$a=0, db\neq0$$
$$b=0, ac\neq0$$
$$c=0, bd\neq0$$
$$d=0, ca\neq0$$
should be taken account also.

 

[haruspex]

On polygon ABCD
a is number of vertexes of n-polygon between A and B
b is number of vertexes of n-polygon between B and C
c is number of vertexes of n-polygon between C and D
d is number of vertexes of n-polygon between D and A
I guess the number of cases satisfying
a+b+c+d=n-4
a,b,c,d $\ge$ 1
multiplied by n/4, which express A is on which vertex and remove count redundancy, would be the answer.


In addition when the condition of "no adjacent sides of n-polygon" is also permitted, the cases of
$$a=0, db\neq0$$
$$b=0, ac\neq0$$
$$c=0, bd\neq0$$
$$d=0, ca\neq0$$
should be taken account also.

A problem with that approach is symmetries. In your diagram in post #4, each of the rectangles would be counted twice. In a larger polygon there may be squares counted four times and quadrilaterals with no symmetries.

 

[Prof B]

Homework Statement:: How many quadrilaterals can be formed from n-polygon (convex) given no adjacent sides of the polygon are used?

How is a quadrilateral "formed" from an n-gon? How is the convexity of the n-gon relevant? Why do you call it an n-polygon instead of an n-gon?

A possibly related question was already posed: https://www.physicsforums.com/threads/no-of-quadrilaterals-in-a-polygon.480827/

 

[member 428835]

How is a quadrilateral "formed" from an n-gon? How is the convexity of the n-gon relevant? Why do you call it an n-polygon instead of an n-gon?

A possibly related question was already posed: https://www.physicsforums.com/threads/no-of-quadrilaterals-in-a-polygon.480827/

Formed by selecting 4 vertices. I call it an n-gon in post 10.

 

[haruspex]

Formed by selecting 4 vertices. I call it an n-gon in post 10.

I think the easiest/surest way is to break it into cases.
Let N211 be the number of ways of choosing four vertices such that two are adjacent and the other two isolated, etc.
N1111+N211+N22+N31+N4=ⁿC₄
N4=n
N31=n(n-5)
N22=n(n-5)/2
N211 is the slightly tricky one.

n ways to pick the 2. There are n-4 positions available to the two isolates. In n-5 ways these would also be adjacent, so N211=n(^n-4C₂-(n-5))

 

[Prof B]

Formed by selecting 4 vertices. I call it an n-gon in post 10.

There are 3 quadrilaterals with vertex set {A,B,C,D}. Do you want to count all 3 or only the convex one?

 

[haruspex]

There are 3 quadrilaterals with vertex set {A,B,C,D}. Do you want to count all 3 or only the convex one?

It doesn’t matter much because the ratio is 3:1 for all n.

 

[Prof B]

It doesn’t matter much because the ratio is 3:1 for all n.

Not necessarily. What if ABCD contains an edge of the n-gon but ACBD does not?

 

[Prof B]

On polygon ABCD
a is number of vertexes of n-polygon between A and B
b is number of vertexes of n-polygon between B and C
c is number of vertexes of n-polygon between C and D
d is number of vertexes of n-polygon between D and A
I guess the number of cases satisfying
a+b+c+d=n-4
a,b,c,d $\ge$ 1
multiplied by n/4, which express A is on which vertex and remove count redundancy, would be the answer.

If the quadrilaterals are required to be convex then your analysis is correct. The number of cases is called a "composition" and you can find a formula here.

According to Georg Polya, understanding the question is the first step in problem solving.

 

[haruspex]

Not necessarily. What if ABCD contains an edge of the n-gon but ACBD does not?

Good point.