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: enter image description here[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}}$$

| cite | improve this answer | |

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.