• member 428835

#### 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?

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.

• member 428835
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, ...)

• member 428835
Don’t you mean n=8, 9, ...? (I get 2, 18, ...)
Did I take it wrong ? 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.

Last edited:
• anuttarasammyak
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?

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.

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.

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"?

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.

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?

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.

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.

Last edited:
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?

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=nC4
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-4C2-(n-5))

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?

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.

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?

• 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.
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.

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