\font\mc=cmr9
\centerline{\bf Three Catalan Bijections}
\bigskip
\centerline{by Donald E. Knuth}
\smallskip
\centerline{Institut Mittag-Leffler and Stanford University}
\centerline{25 February 2005}
\bigskip
\bigskip
\noindent
This note contains three short programs that implement one-to-one
correspondences between four kinds of combinatorial structures:
\smallskip\item{1)} Ordered forests with $n$ nodes and pruning order~$m$;
\smallskip\item{2)} Binary trees with $n$ nodes and Strahler number~$m$;
\smallskip\item{3)} Nested strings (Dyck words) of length $2n$ and
log-height~$m$;
\smallskip\item{4)} Kepler towers with $n$ bricks and $m$ walls.
\smallskip\noindent
In each case the number of structures of size $n$ is the Catalan
number $C_n={2n\choose n}/(n+1)$, and --- surprisingly --- the
bijections also preserve the parameter~$m$.
Given a number $n>1$, each program generates all $C_n$ objects of
one type, bijects them into objects of another type, verifies that
the parameter~$m$ has not changed, and applies the inverse bijection
to prove constructively that the correspondence is indeed one-to-one.
Program 1, called {\mc ZEILBERGER}, converts between (1) and (2).
Program~2, {\mc FRAN\c{C}ON}, converts between (2) and~(3). And
Program~3, {\mc VIENNOT}, converts between (3) and~(4). Incidentally,
Kepler towers appear to be a completely new kind of object, recently
invented by Xavier Viennot and introduced here for the first time.
Simple bijections between (2) and~(4), or between (1) and~(4),
are not yet known, although complex bijections could of course
be obtained by composing those given here.
The first bijection was introduced by Doron Zeilberger in 1990, yet
its computer implementation is not without interest. Although
Zeilberger's algorithm was correct, his proof of correctness
was not quite complete; Program~1 therefore removes any lingering doubts
that may have existed. More significantly, the program demonstrates
a strong property of Zeilberger's bijection that may not have been
noticed before: Node~$x$ is the leftmost child of node~$y$ in the
ordered forest if and only if node $x$ is the left child of
node~$y$ in the corresponding binary tree.
The second bijection was inspired by the work of Jean Fran\c{c}on
in 1984, but it is organized here in a new way, based on a heap-like
data structure. Therefore it appears to solve an open problem that
he stated, namely to construct a ``direct'' parameter-preserving
bijection between objects of types (2) and~(3). Moreover, Program~2
has the interesting property that the bijection and its inverse
both carry out their work in the same direction as they translate
one object to another. By contrast, the inverse bijections in Programs
1 and~3 essentially cause time to run backward when they undo the
effects of forward-runnning bijections.
Program 3 introduces a new bijection that was recently explained
pictorially to the author by its creator, Xavier Viennot. The
resulting computer program has turned out to be remarkably simple
and fast.
All three programs have been written with the conventions of
``literate programming,'' as embodied in the {\tt CWEB} system
developed by Silvio Levy and the author. This style of
presentation features informal, human-oriented English descriptions
alternating with formal, computer-oriented commands. The latter
instructions are expressed in the {\mc C}~programming language;
but mathematicians unfamiliar with~{\mc C} should still be able
to get the gist of the ideas by reading the English commentary.
(A~detailed explanation of how to read {\tt CWEB} programs ---
more than almost anybody needs to know --- can be found in
Chapter~4 of the author's book {\sl The Stanford GraphBase}.)
Incidentally, these programs are independent of each other.
They can be downloaded from the author's web site
{\tt http:/\kern-.1em/www-cs-faculty.stanford.edu/\char`\~knuth/%
programs.html} and used without restriction.
\vfill\eject
% Now I bring in the program files created with cweave
\input cwebmac
\let\INPUT=\input
\def\input#1 {\def\next{#1}\ifx\next\cwebmac\else\INPUT #1\fi}
\def\cwebmac{cwebmac}
\def\inx{}
\def\fin{}
\def\con{\output{\setbox0=\box255
\global\output{\normaloutput\page\lheader\rheader}}\eject}
\outer\def\N#1#2#3.{% beginning of starred section
\ifacro{\toksF={}\makeoutlinetoks#3\outlinedone\outlinedone}\fi
\gdepth=#1\gtitle={#3}\MN{#2}%
\ifon\ifnum#1<\secpagedepth \vfil\eject % force page break if depth is small
\else\vfil\penalty-100\vfilneg\vskip\intersecskip\fi\fi
\message{*\secno} % progress report
\def\stripprefix##1>{}\def\gtitletoks{#3}%
\edef\gtitletoks{\expandafter\stripprefix\meaning\gtitletoks}%
% omit output to contents file
\ifpdftex\expandafter\xdef\csname curr#1\endcsname{\secno}
\ifnum#1>0\countB=#1 \advance\countB by-1
\advancenumber{chunk\the\countB.\expnumber{curr\the\countB}}\fi\fi
\ifpdf\special{pdf: outline #1 << /Title (\the\toksE) /Dest
[ @thispage /FitH @ypos ] >>}\fi
\ifon\startsection{\bf#3.\quad}\ignorespaces}
\def\datethis{\def\startsection{\centerline{\bf Program 1}\bigskip
\let\startsection=\stsec\stsec}}
\input zeilberger.tex
\def\datethis{\def\startsection{\centerline{\bf Program 2}\bigskip
\let\startsection=\stsec\stsec}}
\input francon.tex
\def\datethis{\def\startsection{\centerline{\bf Program 3}\bigskip
\let\startsection=\stsec\stsec}}
\input viennot.tex
\deadcycles=0
\end