## Enumerating triangulations of quadrangulations in cycles

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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?

-

When I talk about quadrangulations, I mean planar quadrangulations. – utdiscant Sep 18 2010 at 20:21

## 2 Answers

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

-

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-

This approach seems easiest to prove. – utdiscant Sep 18 2010 at 23:11
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 12, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9274721145629883, "perplexity_flag": "middle"}