Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
When I talk about quadrangulations, I mean planar quadrangulations. –  utdiscant Sep 18 '10 at 20:21

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer

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.

share|improve this answer
    
This approach seems easiest to prove. –  utdiscant Sep 18 '10 at 23:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.