3
$\begingroup$

I'm stuck on such problem: triangulation of the $n$-gon is division of said $n$-gon into $(n-2)$ triangles whose sides are either sides of the $n$-gon or certain non-intersecting diagonals. How many triangulations of the $n$-gon are there? How many of these are there such that every triangle has at least one side that is also a side of the $n$-gon?

The first part is easy - I've managed to deliver a Catalan number recursive expression and then found a formula for $n^{\text{th}}$ Catalan number which is $$ C_{n} = \frac{1}{n+1} {2n \choose n}.$$

What about the second part? Shall it be done by subtracting some set from $n$-th Catalan number ? What should it look like?

Thank you in advance :)

$\endgroup$
5
$\begingroup$

I'll show how we can do this for an $n$-gon in $n2^{n-5}$ ways. First, pick two adjacent sides of the $n$-gon, and add a diagonal to complete the triangle. There are $n$ ways to pick these sides (just pick the vertex they share). The diagonal that we added shares a vertex with two other sides of the $n$-gon (excluding the ones we started with) and can form a triangle with either of them by adding a new diagonal. We can repeat this process on the newest diagonal added until we've triangulated the $n$-gon. The picture below shows an example for the hexagon. enter image description here

There were $n$ ways to choose the starting diagonal, and we had two ways of adding each of the $n-4$ subsequent diagonals. This counts $n2^{n-4}$ triangulations. However, for any triangulation obtained this way, we could start with the last diagonal added and obtain the same triangulation, so we counted each triangulation twice. Hence, there are $n2^{n-5}$ such triangulations.

$\endgroup$
1
  • $\begingroup$ Wow, thank you! That was perfectly clear. $\endgroup$
    – f33tl0v3r
    Dec 22 '20 at 12:23
0
$\begingroup$

I don’t have a solution, but I do have an answer that illustrates a useful tool for attacking such problems.

It’s not hard to find pictures online of the $14$ triangulations of a hexagon, and here are the $42$ triangulations of a heptagon. If we let $t_n$ be the number of triangulations such that every triangle shares at least one side with the $n$-gon, we find that $t_3=1$, $t_4=2$, $t_5=5$, $t_6=12$, and $t_7=28$. Looking up the sequence $1,2,5,12,28$ in OEIS, we get A045623 as the first hit. If $a_n=t_{n+3}$ for $n\ge 0$, that sequence is listed as the number of $1$s in all compositions of $n+1$, but in the COMMENTS it is noted that $a_n$ is indeed our $t_n$. The FORMULA section of the entry offers the recurrence

$$a_{n+1}=2a_n+2^{n-1}$$

for $n>0$, with $a_0=1$ and $a_2=2$; this translates to

$$t_{n+1}=2t_n+2^{n-4}$$

for $n>3$, with $t_3=1$ and $t_4=2$. It also offers the closed form $a_n=(n+3)2^{n-2}$ for $n\ge 1$ and $a_0=1$, which translates to $t_n=n2^{n-5}$ for $n\ge 4$ and $t_3=1$; this can of course be derived from the recurrence.

I’ve not yet seen an argument for either the recurrence or the closed form, and I may not find much time to think about. If I do come up with one, however, I’ll add it (if no one has beaten me to it).

$\endgroup$

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.