1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\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.