Counting the Catalan numbers using sequence constructions

Question

In my lecture today my lecturer derived the equation satisfied by the generating function for the Catalan numbers by using a sequence construction. Specifically, let $\mathcal{T}$ equal the set of triangulations of $(n+2)$-gons, for $n=0,1,2,3...$. Then we should get, as combinatorial classes that

$\mathcal{T}=\epsilon +z\mathcal{T}+(z\mathcal{T})^2+(z\mathcal{T})^3+...$

Where we denote the right hand side by $\mathcal{S}(z\mathcal{T})$.

I know, given the above relation, how we get the equation that the catalan numbers generating function satisfies but I can't see why the above equation (or more correctly, bijection) should be true. I don't see how the above corresponds to counting triangulations. Here $\epsilon$ denotes the neutral combinatorial class consisting of a unique element $\epsilon$ of size zero.

Note I am aware of the method of counting triangulations which give $\mathcal{T}=\epsilon + \mathcal{T}z\mathcal{T}$, but I want to do it using the sequence construction. Note I have been a little slack with notation letting $z$ denote the atomic combinatorial class consisting of a unique element of size one.

Answer 1

Let $v_0, v_1, \dots, v_{n+1}$ be the vertices of the $(n+2)$-gon. The $(z \mathcal T)^k$ term of this relation corresponds to triangulations in which $v_0$ is part of $k$ triangles. (Considering the triangulation as a graph, $v_0$ has degree $k+1$.)

If $v$ is part of $k$ triangles, $v_0$ is adjacent to $v_{i_0}, v_{i_2}, \dots, v_{i_k}$ in the graph, with $i_0 = 1$ and $i_k=n+1$; also, $v_{i_{j-1}}$ and $v_{i_j}$ are adjacent for each $1 \le j \le k$, since these form the third side of a triangle with vertex $v_0$. For each triangle $v_0 v_{i_{j-1}} v_{i_j}$:

• If $i_j = i_{j-1}+1$, then the edge $v_{i_{j-1}} v_{i_j}$ accounts for one edge of the $(n+2)$-gon and does not need to be triangulated, corresponding to the $z$ term of $z\mathcal T$.
• Otherwise, the vertices $v_{i_{j-1}}, v_{i_{j-1}+1}, v_{i_{j-1}+2}, \dots, v_{i_j}$ account for $i_j - i_{j-1}$ of the edges of the $(n+2)$-gon and form an $(i_j - i_{j-1}+1)$-sided polygon themselves that needs to be triangulated, corresponding to the nontrivial terms of $z\mathcal T$.

There are $k$ polygons (sometimes trivial) left to triangulate, and each is counted by $z \mathcal T$, so overall this case is counted by $(z \mathcal T)^k$.