# Find the generating function for number of quadrangulations

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!

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