\documentclass[12pt]{article} \marginparwidth 0pt \oddsidemargin 0pt \evensidemargin 0pt \marginparsep 0pt \topmargin 0pt \textwidth 6.3in \textheight 8.7in \renewcommand{\baselinestretch}{1.2} \parskip = 3mm %\setstretch{1.5} \setlength{\headheight}{0mm} \usepackage{amsmath,amsthm} \usepackage{graphicx} \usepackage{tikz} \usepackage{pgfplots} \usepackage{adjustbox} %usepackage{amssymb} \usepackage{pathlatex} \usepackage{color} \usepackage{xspace} % load hyperref last \usepackage[colorlinks=true, linkcolor=green, filecolor=brown, citecolor=green]{hyperref} \def\red{\textcolor{red} } \def\v{\vert} \def\a{\ensuremath{\mathcal A}\xspace} \def\b{\ensuremath{\mathcal B}\xspace} \def\s{\ensuremath{\mathcal S}\xspace} \newcommand{\StirlingPartition}[2]{\genfrac{ \{ }{ \} }{0pt}{}{#1}{#2}} \newcommand{\StirlingCycle}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}} \begin{document} \newtheorem{lemma}{Lemma} \newtheorem{theorem}{Theorem} \newtheorem{prop}{Proposition} \newtheorem{cor}{Corollary} %\vspace*{-5mm} \begin{center} {\Large Polygon Dissections and Marked Dyck Paths \\ } \vspace{10mm} DAVID CALLAN \\ Department of Statistics \\ \vspace*{-2mm} University of Wisconsin-Madison \\ \vspace*{-2mm} Medical Science Center \\ \vspace*{-2mm} 1300 University Ave \\ \vspace*{-2mm} Madison, WI \ 53706-1532 \\ {\bf callan@stat.wisc.edu} \\ \vspace{5mm} February 15, 2005 \end{center} \vspace{5mm} Arthur Cayley proved in 1890 that the number of ways to dissect a regular $n$-gon using $i$ noncrossing diagonals is $\frac{1}{i+1}\binom{n-3}{i}\binom{n+i-1}{i}$. Here, a diagonal is a straight line segment joining two nonconsecutive vertices and noncrossing means they do not intersect in the interior though they may share an endpoint. More recently, David Beckwith \cite{beckwith} gave a proof using generating functions and Legendre polynomials, Richard Stanley \cite{stanleyDissections} gave one using the hook-length formula for standard Young tableaux \cite{hook}, J\'{o}sef Przytycki and Adam Sikora \cite{sikora} gave a recursively defined bijection to prove a generalization, and Len Smiley \cite{smiley} used Lagrange inversion to count dissections with various restrictions on the dissected pieces. The purpose of this note is to point out that once the problem is recast in terms of marked lattice paths, a simple combinatorial method of counting Dyck paths applies almost verbatim to obtain Cayley's result. The method also readily yields counts of various restricted dissections, including those in \cite{sikora} and \cite{smiley}. A \emph{balanced $n$-path} is a sequence of $n$ $U$s and $n\ D$s, represented as a path of upsteps $(1,1)$ and downsteps $(1,-1)$ from $(0,0)$ to $(2n,0)$, and a Dyck $n$-path is a balanced $n$-path that never drops below the $x$-axis (ground level). An ascent in a balanced path is a maximal sequence of contiguous upsteps. An ascent consisting of $j$ upsteps contains $j-1$ vertices of the path in its interior. A \emph{$k$-marked} balanced $n$-path is one in which $k$ interior vertices of ascents have been marked. Replacing $n$ by $n+2$ and $i$ by $n-1-k$ in Cayley's formula and rearranging the binomial coefficient product, it says that the number of dissections of a regular $(n+2)$-gon using $n-1-k$ noncrossing diagonals is $\frac{1}{n+1}\binom{n-1}{k}\binom{2n-k}{n}$. Using standard bijections, these dissections correspond one-to-one to $k$-marked Dyck $n$-paths as illustrated in the Appendix below. Now, it is classic that the parameter $X$ on balanced $n$-paths defined by $X=$ ``number of upsteps above ground level'' is uniformly distributed over $\{0,1,2,\ldots,n\}$ and hence divides the $\binom{2n}{n}$ balanced $n$-paths into $n+1$ equal-size classes, one of which consists of the Dyck $n$-paths (the one with $X=n$). Indeed, for $1\le i \le n$, a bijection from balanced $n$-paths with $X=0$ (inverted Dyck paths) to those with $X=i$ is as follows. Number the upsteps from left to right and top to bottom, starting with the last upstep. Then remove the first downstep $d$ encountered directly west of upstep $i$ to obtain two subpaths $A$ and $B$, and reassemble as $B\,d\,A$. (See \cite{callan} for a more leisurely account.) The equidistribution of $X$ is known as the Chung-Feller theorem, first proved by Major Percy A.~MacMahon in 1909 \cite[p.\,168]{macmahon} but named after its 1949 re-discoverers \cite{chung}. MacMahon proved it using formal series of words on an alphabet; Chung and Feller used generating functions. In particular, the number of Dyck $n$-paths is the Catalan number $C_{n}=\frac{1}{n+1}\binom{2n}{n}$. The chief insight of this note is simply that the above bijection can equally well be applied to $k$-marked balanced $n$-paths: the interior vertices of ascents are never disturbed. It again produces $n+1$ equal-size classes one of which consists of the $k$-marked Dyck $n$-paths. Cayley's result will follow as soon as we show that there are $\binom{n-1}{k}\binom{2n-k}{n}$ $k$-marked balanced $n$-paths. To construct them, start with a row of $n$ upsteps. Choose $k$ of the $n-1$ gaps between them for the marked vertices---$\binom{n-1}{k}$ choices---and then insert $n$ downsteps into the remaining gaps and the ``gap'' at either end---$\binom{2n-k}{n}$ ways to insert $n$ balls into $n+1-k$ boxes---and concatenate to form a typical path. Thus there are indeed $\binom{n-1}{k}\binom{2n-k}{n}$ $k$-marked balanced $n$-paths, and Cayley's formula follows. The total number of dissections of an $(n+2)$-gon (with no restriction on the number of diagonals) is the little Schr\"{o}der number $s_{n}$. Thus marked Dyck paths are another manifestation of $s_{n}$. The same method can be used to count other types of dissection of a regular $(n+2)$-gon. For example, dissections into triangles correspond to unmarked Dyck paths. Euler found the number of the former in the 1750s, the first appearance of the Catalan numbers in a combinatorial setting (``the process of induction I employed was quite laborious''). On the other hand, the number of triangle-free dissections is $\frac{1}{n+1}\sum_{k=1}^{\lceil \frac{n-1}{2}\rceil}\binom{n+k}{k}\binom{n-k-1}{k-1}$ \cite{smiley}. Under the bijection below, they correspond to marked Dyck $n$-paths in which every upstep has at least one marked endpoint. It is a nice exercise to show that the number of $(n-k)$-marked balanced $n$-paths in which every upstep has at least one marked endpoint is $\binom{n+k}{k}\binom{n-k-1}{k-1}$. Of course, automated techniques such as %using the computer algebra package \emph{Combstruct} \cite{combstruct} can now be used to verify all these results and more on polygon dissections. However, it will still be a while \linebreak[4] before computers can provide the insight of a nice bijection. \vspace*{2mm} \textbf{Appendix.}\quad A bijection from sets of $n-1-k$ noncrossing diagonals in a regular $(n+2)$-gon to $k$-marked Dyck $n$-paths illustrated with $n=8$ and $k=4$ in six easy steps. { $$ \Einheit=0.6cm. %\PfadDicke{2pt} \Label\o{ \textrm{{\footnotesize 1. noncrossing diagonals}}}(-8.2,0) \Label\o{ \textrm{{\footnotesize 2. canonical triangulation}}}(0,0) \Label\o{ \textrm{{\footnotesize 3. full binary tree}}}(7.2,0) $$ } %\vspace*{17mm} \vspace*{-15mm} \begin{center} % -------------------- See PolygonAndTree.ps -------------------- \begin{adjustbox}{left=14cm} \begin{minipage}[l]{0.5\textwidth} \includegraphics[width=2\linewidth]{PolygonAndTree} \end{minipage} \end{adjustbox} \end{center} \vspace*{-10mm} { $$ \Einheit=0.6cm. %\PfadDicke{2pt} %\Label\o{ \textrm{{\scriptsize }}}(-1,3.0) \Label\o{ \textrm{{\scriptsize Starting from the vertex at left of}}}(-0.5,2.5) \Label\o{ \textrm{{\scriptsize base, insert as dashed lines all}}}(-0.5,2.0) \Label\o{ \textrm{{\scriptsize diagonals from this vertex that do }}}(-0.5,1.5) \Label\o{ \textrm{{\scriptsize not cross existing diagonals, and}}}(-0.5,1.0) \Label\o{ \textrm{{\scriptsize repeat, visiting vertices clockwise}}}(-0.5,0.5) \Label\o{ \textrm{{\scriptsize Place root in base triangle.}}}(7.5,2.5) \Label\o{ \textrm{{\scriptsize Draw tree as indicated}}}(7.5,2.0) \Label\o{ \textrm{{\scriptsize(Etherington \cite{etherington40});}}}(7.5,1.5) \Label\o{ \textrm{{\scriptsize edges crossing dashed lines}}}(7.5,1.0) \Label\o{ \textrm{{\scriptsize (``heavy'') will all}}}(7.5,0.5) \Label\o{ \textrm{{\scriptsize be left-leaning}}}(7.5,0.0) $$ } \vspace*{5mm} \vbox{ $$ \Einheit=0.6cm. %\PfadDicke{2pt} \Pfad(-4,0),3343334344443344\endPfad \SPfad(-4,0),1111111111111111\endSPfad \Label\o{ \textrm{{\scriptsize Traverse tree clockwise from root. As each edge is encountered}} }(4,-1.7) \Label\o{ \textrm{{\scriptsize for the first time, draw a step---up for a north edge,}} }(4,-2.2) \Label\o{ \textrm{{\scriptsize down for an east edge (de Bruijn-Morselt \cite{morselt67}) }} }(4,-2.7) \Label\o{ \textrm{{\footnotesize 5.\ \ labeled Dyck path }}}(4,4.5) \Label\o{ \textrm{{\scriptsize Left edges point north, right edges}}}(-9,-1.7) \Label\o{ \textrm{{\scriptsize east; ``heavy'' edges are labeled,}}}(-9,-2.2) \Label\o{ \textrm{{\scriptsize and never end at a leaf.}}}(-9,-2.7) \Label\o{ \textrm{{\footnotesize 4.\ \ aligned binary tree}}}(-10,4.5) \DuennPunkt(-4,0) \DuennPunkt(-3,1) \DuennPunkt(-2,2) \DuennPunkt(-1,1) \DuennPunkt(0,2) \DuennPunkt(1,3) \DuennPunkt(2,4) \DuennPunkt(3,3) \DuennPunkt(4,4) \DuennPunkt(5,3) \DuennPunkt(6,2) \DuennPunkt(7,1) \DuennPunkt(8,0) \DuennPunkt(9,1) \DuennPunkt(10,2) \DuennPunkt(11,1) \DuennPunkt(12,0) \Pfad(-12,0),22\endPfad \Pfad(-12,1),11\endPfad \Pfad(-12,0),1111\endPfad \Pfad(-11,1),222\endPfad \Pfad(-11,2),1\endPfad \Pfad(-11,3),11\endPfad \Pfad(-10,3),2\endPfad \Pfad(-9,0),22\endPfad \Pfad(-9,1),1\endPfad \DuennPunkt(-8,0) \DuennPunkt(-8,1) \DuennPunkt(-9,0) \DuennPunkt(-9,1) \DuennPunkt(-9,2) \DuennPunkt(-9,3) \DuennPunkt(-10,1) \DuennPunkt(-10,2) \DuennPunkt(-10,3) \DuennPunkt(-10,4) \DuennPunkt(-11,1) \DuennPunkt(-11,2) \DuennPunkt(-11,3) \DuennPunkt(-11,4) \DuennPunkt(-12,1) \DuennPunkt(-12,2) \NormalPunkt(-12,0) \Label\u{ \textrm{{\scriptsize root}}}(-12,.1) \Label\l{ \textrm{{\scriptsize 1}}}(-11.8,.5) \Label\l{ \textrm{{\scriptsize 2}}}(-10.8,1.5) \Label\l{ \textrm{{\scriptsize 3}}}(-10.8,2.5) \Label\l{ \textrm{{\scriptsize 4}}}(-8.8,.5) \Label\l{ \textrm{{\scriptsize 1}}}(-3.2,.7) \Label\l{ \textrm{{\scriptsize 2}}}(-0.2,1.7) \Label\l{ \textrm{{\scriptsize 3}}}(0.8,2.7) \Label\l{ \textrm{{\scriptsize 4}}}(8.8,.7) $$ } \vspace*{5mm} { $$ \Einheit=0.6cm. %\PfadDicke{2pt} \Pfad(-8,0),3343334344443344\endPfad \SPfad(-8,0),1111111111111111\endSPfad \Label\o{ \textrm{{\scriptsize place mark on top vertex of}}}(0,-1) \Label\o{ \textrm{{\scriptsize each labeled upstep}}}(0,-1.6) \NormalPunkt(-7,1) \NormalPunkt(-4,2) \NormalPunkt(-3,3) \NormalPunkt(5,1) \DuennPunkt(-8,0) \DuennPunkt(-7,1) \DuennPunkt(-6,2) \DuennPunkt(-5,1) \DuennPunkt(-4,2) \DuennPunkt(-3,3) \DuennPunkt(-2,4) \DuennPunkt(-1,3) \DuennPunkt(0,4) \DuennPunkt(1,3) \DuennPunkt(2,2) \DuennPunkt(3,1) \DuennPunkt(4,0) \DuennPunkt(5,1) \DuennPunkt(6,2) \DuennPunkt(7,1) \DuennPunkt(8,0) \Label\o{ \textrm{{\footnotesize 6.\ \ marked Dyck path}}}(0,4.5) $$ } In the example all interior ascent vertices happen to be marked, but incorporating one of the dashed diagonals into the original set of noncrossing diagonals would simply delete the corresponding mark from the Dyck path. That the steps are reversible is fairly obvious for all but step $2\rightarrow 3\,(\,=4)$ and we leave the reader to ponder that one (it relies on the fact that a full binary tree has at least one vertex adjacent to two leaves). \begin{thebibliography}{99} \bibitem{beckwith} D. Beckwith, Legendre polynomials and polygon dissections, this \textsc{Monthly} \textbf{105} (1998), 256--257. \bibitem{stanleyDissections} R. Stanley, Polygon dissections and standard Young tableaux, \emph{Journal of Combinatorial Theory, Series A} {\bf 76} (1996), 175--177. \bibitem{hook} K. Glass and C.-K. Ng, A simple proof of the hook length formula, \emph{Amer. math. Monthly} {\bf 111} (2004), 700--703. \bibitem{sikora} J. Przytycki and A. Sikora, Polygon dissections and Euler, Fuss, Kirkman, and Cayley numbers, J. Comb. Theory (A) {\bf92} (2000) 68--76. \newline http://arxiv.org/abs/math.CO/9811086 \bibitem{callan} D. Callan, Pair them up!: A visual approach to the Chung-Feller theorem, {\em College Mathematics Journal} {\bf 26} (1995) 196--198. \bibitem{macmahon} P.~A.~MacMahon, Memoir on the theory of the partitions of numbers \emph{Phil. Trans. Royal Soc. London(A)} \textbf{209}, 1909, 153--175. Also \emph{Collected Works Vol. 1}, (G.~E.~Andrews, ed.), MIT Press, Cambridge, Mass 1978, 1292--1314. \bibitem{chung} K. L. Chung and W. Feller, On Fluctuations in Coin-Tossing, \emph{Proc. Natl. Academy of Sciences}({\bf 35}) 1949, pp. 605-608. \bibitem{smiley} L. Smiley, Triangle-free polygon dissections, \newline http://www.math.uaa.alaska.edu/$\,\widetilde{\ }\,$smiley/schroed.html \bibitem{combstruct} Combstruct, a Maple\texttrademark\ computer algebra package, \htmladdnormallink{http://algo.inria.fr/libraries/ }{http://algo.inria.fr/libraries/} \bibitem{etherington40} Etherington, I. M. H., Some problems of non-associative combinations (I), Edinburgh Mathematical Notes \textbf{32} 1940, i--vi. \bibitem{morselt67} de Bruijn, N. G.; Morselt, B. J. M. A note on plane trees, \emph{J. Combinatorial Theory} \textbf{2} 1967 27--34. \end{thebibliography} \end{document} http://algo.inria.fr/libraries/ \htmladdnormallink{http://algo.inria.fr/libraries/ }{http://algo.inria.fr/libraries/}