1
$\begingroup$

Consider a cycle of length $(2n+2)$. Now we quadrangulate this cycle into $n$ quadrants. We want to enumerate the number of quadrangulations, and we denote this number by $q_n$. Now we triangulate this quadrangulation by triangulating each quadrant. We denote the number of triangulations $t_n$. It is clear that $t_n = 2^nq_n$.

Do I count some triangulations multiple times? That is, will some triangulation be the result of multiple different quadrangulations?

$\endgroup$
1
  • $\begingroup$ When I talk about quadrangulations, I mean planar quadrangulations. $\endgroup$
    – utdiscant
    Sep 18 '10 at 20:21
4
$\begingroup$

No triangulation occurs multiple times. At least one of the triangles $T$ of the triangulation has two edges on the boundary. There is a unique quadrant (I would say quadrilateral) $Q$ made up of two triangles of the triangulation, one of which is $T$. Remove the three edges of $T$, obtaining two quadrangulated cycles (possibly degenerate), and induct.

Note that not every triangulation of a $(2n+2)$-cycle is obtained by bisecting the quadrilaterals of a quadrangulation. Also, it is well-known that the number of quadrangulations of a $(2n+2)$-gon is $\frac{1}{2n+1}\binom{3n}{n}$.

$\endgroup$
3
$\begingroup$

Another way to think about this is that each triangulation gives you a binary tree, while each quadrangulation gives you a ternary tree (consider the dual graphs). If a triangulation comes from a quadrangulation then the correspondence gives you a perfect matching on the binary tree. Now show that every tree has at most one perfect matching. This translates to: every triangulation comes from at most one quadrangulation.

$\endgroup$
1
  • $\begingroup$ This approach seems easiest to prove. $\endgroup$
    – utdiscant
    Sep 18 '10 at 23:11

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.