The no. of ways dividing a polygon with $n+1$ sides into triangular regions....

Question

Please if any one can help me explaining this concept, I can't proceed further due to this....

Let $h(n)$ denote the no. of ways dividing a convex polygon region with $(n+1)$ sides into triangular regions by inserting diagonals which does not intersect in interior.
We assume: $h(1)=1$ ,then the formula is:
$$h(n)=\sum_{k=1}^{n-1}h(k)h(n-k)$$

Proof :
$$\text{for}~~n=1,h(1)=1,$$ $$n=2,h(2)=1$$
$\text{for}~~n\geq3,$ consider $a(n+1)$ polygon say $[A_1 ~~A_2~~ A_3 \ldots A_{n+1}]$

for any given $k$ with $1\leq k\leq n-1$ ,We choose $C$ such that if we move clockwise along vertices of polygon we have :=
$A=A_1,A_2,A_3\ldots,C=A_{k+1},A_{k+2}\ldots ,A_{n+1}=B$

ways of dividing $R_1$ into triangles - $h(k)$ and
ways of dividing $R_2$ into triangles $h(n-k)$

$\therefore $ no. of ways = $h(k)h(n-k)$ for any given k with $1\leq k\leq n-1$ ,we choose $C$ such that : $$A=A_1,C=A_{k+1},B=A_{n+1}$$

The triangle $T=[A,B,C]$ divides polygonal region into $3$ parts .
$R_1,T$ and $R_2$ with :
$R_1$ $(k+1)$ polygon
$R_2$ $(n+k-1)$ polygon.

The no. of ways of dividing $R_1$ into $\triangle$'s=$h(k)$
The no. of ways of dividing $R_2$ into $\triangle$'s=$h(n+k)$.

The no. of triangularization of polygon such that :=
$T=[A_1,A_{k+1},A_{n+1}]$ , $1\leq k\leq n-1$

is one of $\triangle=h(k)h(n-k)$

$\therefore$ total no. of ways= $\sum_{k=1}^{n-1}h(k)h(n-k)$

Can someone explain the steps in the proof to me as I can't get how did we get the no. of ways of triangularization .........

Answer 1

Draw a picture. If you think about the polygon having vertices $A_1$, $A_2, \dotsc, A_{n+1}$, you can subdivide into two smaller polygons by drawing a line from $A_1$ to $A_{k+1}$ for $k=2, \dotsc, n-1$. One of those polygons has $k+1<n+1$ vertices, so it has $h(k)$ triangulations by induction. The other has $n-k+1<n+1$ vertices, so it has $h(n-k)$ triangulations by induction. So the total ways of triangulating the original polygon, starting with a line from $A_1$ to $A_{k+1}$, is $h(k)h(n-k)$. There is one other possibility; namely that $A_1A_2A_{n+1}$ is one of the triangles. In this case, the remaining polygon has $n$ vertices, so we get $h(1)h(n-1)$ triangulations in this case. Since all triangulations fall into one of these cases, the total number of triangulations is $$h(n) = \sum_{k=1}^{n-1} h(k)h(n-k),$$ which is what you want. (Incidentally, this series of numbers is called the Catalan numbers.)