MIT Combinatorics Seminar

A Bijection Between 2-Triangulations and Pairs of Non-Crossing Dick Paths

Sergi Elizalde (Dartmouth University)

Wednesday September 20, 2006   4:15 pm    Room 2-136


Triangulations of a convex polygon are known to be counted by the Catalan numbers. A natural generalization of a triangulation is a $k$-triangulation, which is defined to be a maximal set of diagonals so that no $k+1$ of them mutually cross in their interiors. It was proved by Jakob Jonsson that $k$-triangulations are enumerated by certain determinants of Catalan numbers, that are also known to count $k$-tuples of non-crossing Dyck paths.

There are several simple bijections between triangulations of a convex $n$-gon and Dyck paths. However, no bijective proof of Jonsson's result is known for general $k$. In this talk I will give a bijective proof for the case $k=2$, that is, I will present a bijection between $2$-triangulations of a convex $n$-gon and pairs $(P,Q)$ of Dyck paths of semilength $n-4$ so that $P$ never goes below $Q$. The bijection is obtained by constructing isomorphic generating trees for the sets of 2-triangulations and pairs of non-crossing Dyck paths.