3
$\begingroup$

So I was reading A Path to Combinatorics for Undergraduates by Titu Andreescu and Zuming Feng, and I came across this question:

Let n be an integer greater than $4$, and let $P_1 P_2 \ldots P_n$ be a convex $n$ sided polygon. Zachary wants to draw $n-3$ diagonals that partition the region enclosed by the polygon into $n-2$ triangular regions and that may intersect only at the vertices of the polygon, In addition, he wants each triangular region to have at least $1$ side that is also a side of the polygon. In how many ways can Zachary do this?

After researching a bit i found out that $C_{n-2}$ (the $(n-2)^{\text{th}}$ Catalan number) counts the number of triangulations for a convex n-sided polygon, but I don't know how to account for the triangulations that have triangles which don't have a side in common with the polygon. I would really appreciate it if someone could help me solve the problem.

$\endgroup$
1
  • $\begingroup$ Think about a triangle transcribed in a hexagon, these triangulations should appear similar $\endgroup$ May 31, 2017 at 4:26

2 Answers 2

3
$\begingroup$

The answer is $n \cdot 2^{n-5}$. Fix the side $P_1P_2$ and we first observe that this side must appear in one of the triangles. Let's say that it appears in the triangle $P_1P_2P_i$, with $3 \le i \le n$. This triangle divides the $n$-agon in two polygons (or one when $i = 3$ or $i = n$), one with $i - 1$ sides and the other with $n - i - 2$ sides.

Assume first that $i = 3$ (the case $i = n$ is similar). The remaining polygon is $P_1P_3P_4 \ldots P_n$ and we should triangulate it. The side $P_1P_3$ should be present in one of the triangles and the third vertex of this triangle must be $P_4$ or $P_n$, otherwise, we would get a triangle without any side in common with the original polygon. So we have $2$ possibilities at this point and if we continue with a similar reasoning, it's easy to see that we will have $2^{n-4}$ possibilities if $i = 3$.

If $i = n$, we also have $2^{n-4}$ possibilities and if $3 < i < n$, we now have indeed two polygons and by a similar argument, we have $2^{i-4} \cdot 2^{n-i-1} = 2^{n-5}$ possibilities for each $i$.

Therefore the total number of triangulations with the required property is $$ 2^{n-4} + (n-4)2^{n-5} + 2^{n-4} = n \cdot 2^{n-5}. $$

$\endgroup$
0
$\begingroup$

Here is a slightly different reasoning from the older answer presented here. We will prove that there is $n\cdot 2^{n-5}$ ways to triangulate a convex $n$-sided polygon in such way that every triangle has a side common with the polygon.

Each triangulation has at least one ear. (If $n>3$ a polygon has at least $2$ ears. If we consider the dual graph of triangulation, it is easy show that $t_2-t_0=2$, where $t_2$ is the number of ears and $t_0$ is the number of triangles which have $0$ common sides with the polygon. $t_0=0$ is our case, so there are exactly $2$ ears if $n>3$. We won’t really use this fact though. Or rather, we will prove the same statement in the process.)

There are $n$ ways of choosing where the first ear of triangulation will be for a convex polygon, since any pair of neighbour edges can be chosen. Let us call the farthest vertices of these edges A and B. It is clear that there must be a diagonal drawn either from A or from B (but not both). Moreover, if a diagonal is drawn from A, its other end is the vertex next to B. And vice versa, if a diagonal is drawn from B, its other end is the vertex next to A.

The very same reasoning as for diagonal AB can be made for a new diagonal. And so on. Each time there is exactly $2$ ways to choose next diagonal. This process will end when we won’t be able to draw a diagonal. This means we reached a second ear.

The overall number of diagonals in triangulation is $n-3$. There was $n$ ways to choose the first one and $2$ ways to choose any other. The answer is not $n\cdot 2^{n-4}$ though since every triangulation is counted $2$ times: starting from both its ears. Finally the answer is $n\cdot 2^{n-4}\cdot 1/2= n\cdot 2^{n-5}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .