Find the generating function for number of quadrangulations

Question

I have this homework to solve, I've got some ideas but not sure it's the right direction.

A set of chords of a convex $2n$-gon is a quadrangulation if no two chords intersect and all faces are quadrangles. Let $a_n$ denote the number of quadrangulations of a convex $2n$-gon. Use the symbolic method to find the generating function $A(x) = \sum_{n\ge0} a_nx_n$. The figure shows the $3$ quadrangulations of a $6$-gon: [Hint: Find a connection to ternary trees]

My work

Find a bijection to ternary trees:

Denote the nodes of the $2n$-gon clockwise with $1- 1^*- 2- 2^*- 3- 3^*- 4 -4^*-...-n- n^*$. Start with the node number $1$. The root of the tree should also be $1$. With all kinds of ternary trees with depth $n$ we can always draw a $2n$-gon quadrangulation with the edge of the tree is the diagonal of the quadrangle. So for example, if the tree is $1$ connects to $2$, we have $1-2$ is the diagonal and can draw a quadrangle with $1- 1^*- 2- 2^*$, keep this process for the other nodes, we obtain one unique quadrangulation.

But the problem is: the other way round is not the same. Because if the node is connected by more than $5$ edges, we would not have the ternary tree anymore. Maybe I need to find here some exception?

And I know the generating function for ternary trees is $T(x)=1+xT(x)^3$

Any suggestion would be highly appreciated!

Answer 1

One way to approach this is the following:

For $n=1$ you have one quadrangulation - a 2-gon, which is just a line.

For $n\ge2$ proceed like this:

• choose a quadrangle in such a way that at least one edge of it is facing outside, i.e. it is not the edge of another polygon except our original $2n$-gon.

• The remaining three edges $e_i, e_j, e_k$ are parts of $2i$-gon, $2j$-gon, and $2k$-gon respectively (even if it's just a 2-gon), since you can not split a polygon with an uneven number of vertices into quadrangles.

• Assuming the $2j$-gon is touched by the other two, $e_j$ shares a vertex with $e_i$ and the other one with $e_k$. Therefore, considering double counting of vertices, $2i + 2j + 2k - 2 = 2n$

So we arrive at our generating function:

$$A(x) = \underbrace{x}_{\text{our $2$-gon for $n=1$}} + A(x)\cdot A(x)\cdot A(x)\cdot\underbrace{\frac{1}{x}}_{i+j+k=n-1\text{, so we divide out x}}$$