We have a $n$-sided convex polygon $P$. How many $r$-sided polygons $(r<n)$, with its vertices among those of $P$, can be formed such that it has no sides (edges) in common with $P$?

I tried to use the inclusion-exclusion principle, defining $A_m$ to be the property that our polygon has at least $m$ sides in common with $P$. Then we need to find $\binom{n}{r}-|A_1 \cup A_2 \cup \cdots \cup A_{r-1}|$. But I didn't make much progress along these lines, as finding $|A_m|$ for $m>2$ is not easy.

Please help me out. Thank you.

  • $\begingroup$ @hardmath Yes, that's what I meant. $\endgroup$ – pkwssis Dec 26 '14 at 15:53

It's a good question standing on some nice principles. I would encourage you to find the answer on your own and if you are unable to do so kindly reply and tell me. I would recommend a similar approach to John Hughes.

Name the vertices $a_1, a_2, \dots, a_n$. Then focus on the gaps. The number of gaps is $(r-1)$ (say, $g_1 + g_2 + \dots + g(r-1))$. Then use these gaps as variables of a multinomial. The sum of these gaps ranges from $r - 1$ to $n - r - 1$. Now use the multinomial theorem, and/or Stars and bars theorem 1. (There has to be at least one gap between the vertices). Now you will get a sum of binomial coefficients which can be solved easily using the Hockey stick identity.

Any error (if any) in the proposed solution is regretted. Comment if any further explanation is required.

  • $\begingroup$ I did manage to solve it. Thank you. $\endgroup$ – pkwssis Dec 27 '14 at 3:46

Label the vertices of $P$, in order, $1, \ldots, n$, starting at any vertex you like.

An $r$-sided polygon in $P$ then corresponds to an increasing sequence of $r$ indices between 1 and $n$. For $n = 5$, for instance, you might take $1, 3, 5$, meaning that your "internal" polygon has vertices $1$, $3$, and $5$. The only tricky thing in your case is that no two adjacent numbers can be picked.

[Reason: any $r$-sided polygon has a lowest index. If your indexes don't increase, then you get a crossing (why?). If adjacent numbers are picked, you get an edge of $P$.]

Thus you need to count how many length-$r$ subsequences $1, 2, \ldots, n$ has, where (a) no two elements of the sequence are adjacent, and (b) you don't pick both "1" and $n$ to be in the subsequence.

So: pick a starting vertex, and then pick a "gap" between adjacent vertices. In fact, pick $r-1$ numbers. So a starting vertex of 2 and the sequence $(1,1,2)$ in a 10-sided polygon would define the subpolygon

(2, 4, 6, 9)

with gaps of size 1, 1, and 2. (A 'gap' is how many vertices you skipped over.)

The only problem is that you might start with vertex 1 and end with vertex $n$, and thus include the edge $n, 1$. So let's pick $r$ gaps instead. (In the example above, they are $(1, 1, 2, 3)$). These must have the properties that

  1. They're positive
  2. They sum to $n - r + 1$
  3. The sum of all except that last one, plus $r$, must be no more than $n$

The "last edge" problem makes this ugly. So let's split into two subproblems:

  1. How many internal polygons are there that don't contain vertex 1?

  2. How many are there that DO contain vertex 1?

For part 1, in a 10-vertex polygon, if your internal 3-vertex polygon has a list of verts like (2, 5, 7), you can imagine that you start counting "gaps" at a fictitious vertex 0, and you get gaps of $1, 2, 1, 3$ for this sequence. The sum of the gaps is $10 - 3$. In short:

The answer to part 1 is a "stars and bars" problem for $n$ stars and bars among which are $r+1$ stars. (stars correspond to vertices)

Can you do part 2 yourself?

  • $\begingroup$ "An r-sided polygon in P can be described by an increasing sequence of r indices between 1 and n. For n=5, for instance, you might take 2,3,5" I didn't get that.. could you please explain? $\endgroup$ – pkwssis Dec 26 '14 at 15:27
  • $\begingroup$ First number the vertices of $P$ starting with $1$ and going consecutively. The sequence gives the vertices of the polygon. Each polygon will be a selection of $r$ vertices from $P$. Listing them in increasing order first makes sure you only count the combination once and (if you follow that order) makes sure the polygon doesn't cross. $\endgroup$ – Ross Millikan Dec 26 '14 at 16:00
  • $\begingroup$ That's what I meant Ross, yes. But you also have to not consider all selections of $r$ vertices from $P$, since none of $P$'s edges are allowed in the internal polygon. $\endgroup$ – John Hughes Dec 26 '14 at 17:12
  • $\begingroup$ If we consider gaps of edges rather than gaps of vertices, I think that the last edge problem won't arise. $\endgroup$ – pkwssis Dec 27 '14 at 3:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.