Catalan numbers and triangulation Assume $C_n$ is the number of triangulations of a polygon with $n+2$ sides. Using a combinatorial proof, show that $(4n+2)C_n=(n+2)C_{n+1}$.
I don't even know where to start with this one. I understand the triangulation after doing some googling, but I don't know where to go from here to prove the above using just a combinatorial formula.
 A: I’ll sketch a combinatorial argument.
It takes $n-1$ diagonals to triangulate a polygon with $n+2$ sides. If we view the result as a graph, that graph has $(n+2)+(n-1)=2n+1$ edges, so the sum of the degrees of the vertices is $2(2n+1)=4n+2$. Thus, there are $(4n+2)C_n$ ordered triples $\langle T,v,e\rangle$, where $T$ is a triangulation of an $(n+2)$-gon whose vertices have been labelled $1,2,\ldots,n+2$ clockwise, $v$ is one of its vertices, and $e$ is one of the edges incident at that vertex.
Now consider an $(n+3)$-gon whose vertices have been labelled $1,2,\ldots,n+3$ clockwise. There are $(n+2)C_{n+1}$ ordered pairs $\langle T,e\rangle$, where $T$ is a triangulation of the $(n+3)$-gon, and $e$ is an edge of the $(n+3)$-gon (not an edge of the triangulation of the triangulation) other than $\{1,n+3\}$. (In other words, $e$ is one of the edges $\{k,k+1\}$ for $k=1,2,\ldots,n+2$.)
All that’s needed for a combinatorial proof is to find a bijection between the $(4n+2)C_n$ triples and the $(n+2)C_{n+1}$ pairs. I’ll illustrate both directions of the bijection in the case $n=3$.
Figure (A) shows a triangulation $T$ of a hexagon and the edge $\{2,3\}$, indicated in red. To get the corresponding triangulated pentagon, vertex, and edge, delete the red edge and identify its endpoints; the result is Figure (B). Here the collapsed vertex labelled $2,3$ is the selected vertex, and the blue edge that resulted from collapsing edges $\{1,2\}$ and $\{1,3\}$ of Figure (A) is the selected edge.
The other direction of the bijection is shown in Figures (C) and (D). Figure (C) shows a triangulated pentagon with a selected vertex ($2$) and edge ($\{2,3\}$), each shown in red. Now split the selected vertex into two vertices, $2$ and $2'$, connected by a new edge, and split the selected edge into two edges, $\{2,3\}$ and $\{2',3\}$; the result is shown in Figure (D), with the new edge in blue and the split edges in red.

It’s not too hard to see that this really does describe a bijection and hence that
$$(4n+2)C_n=(n+2)C_{n+1}\;.$$
