\input lmacros
\documentstyle[12pt]{article}
\headheight 0in
\headsep 0in
\evensidemargin 1in
\oddsidemargin \evensidemargin
\textwidth 6.5in
\topmargin 1.25in
\textheight 8.7in
\begin{document}
\pagestyle{empty}

\begin{center}
{\bf Notes:  Catalan number combinatorics.}
\end{center}

\noindent 1.  Definition: balanced strings.

\medskip

We define the {\it Catalan number} $C_{n}$ to be the number of
balanced strings of $n$ left and $n$ right parentheses.  Balanced
means the parentheses match up in pairs in the usual way: thus
$(()(()))$ is balanced, whereas $()())(()$ is not.

By convention, the empty string is considered balanced, so that $C_{0}
= 1$.

Some small values: $C_{1} = 1$; the only string is $()$.  $C_{2} = 2$;
the two strings are $()()$ and $(())$.  $C_{3} = 5$; the strings are
$(()())$, $((()))$, $()(())$, $(())()$, $()()()$.

A word of warning: the numbers $h(n)$ defined in the textbook as
Catalan numbers are indexed differently, so that $h(n+1) = C_{n}$.

\bigskip

\noindent 2.  Generating function.

\medskip

We shall compute the Catalan numbers by finding their generating
function.  Thus let 
$$ C(x) = \sum _{n} C_{n} x^{n} $$
be the generating function counting all balanced strings with weight
$x^{n}$ for those with $n$ left and $n$ right parentheses.

Define a closed group to be a balanced string in which the initial
left parenthesis is matched by the final right parenthesis.  Notice
that (1) closed groups are of the form $(bbbb)$ where $bbbb$ inside is
any balanced string (including empty), and (2) every balanced string
breaks up uniquely into a sequence of closed groups, for example
$(())()(()()) = (())\;()\;(()())$.  This includes the empty string,
which is the empty sequence of closed groups.

Since the size of a closed group $(bbbb)$ is one more than that of the
balanced string $bbbb$ inside, the generating function counting all
closed groups is $xC(x)$.  The extra factor of $x$ changes each weight
$x^{n}$, the weight of $bbbb$, to $x^{n+1}$, the weight of $(bbbb)$.

Since a balanced string is the same as a sequence of any number of
independently chosen closed groups, and its size is the total of the
sizes of the groups, we have by the repetition principle that 
$$ C(x) = 1/(1-xC(x)) $$
and hence
$$ xC(x)^{2} - C(x) + 1 = 0. $$
Solving this by the quadratic formula gives 
$$ C(x) = (1/2x)(1\pm \sqrt{1-4x}). $$
How do we know which sign is right?
Remember that $C(x)$, as a generating function, is a formal power
series, so the above formula really means that as power series, 
$$ 2xC(x) = 1\pm \sqrt{1-4x}. $$
The left hand side has zero constant term, being a multiple of $x$.
Thus only the minus sign can be correct on the right hand side, as the
constant term would otherwise be $2$.  We conclude that 
$$ C(x) = (1/2x)(1-\sqrt{1-4x}). $$

\bigskip

\noindent 3.  From generating function to numbers.

\medskip

We can solve for the numbers $C_{n}$ by using the binomial theorem in
its extended form to expand the square root in the generating
function.  Thus
$$ 1-2xC(x) = (1-4x)^{1/2} = \sum _{n} {1/2\choose n } (-4x)^{n}. $$
Comparing coefficients, $-2C_{n}$ is the coefficient of $x^{n+1}$ on
the left hand side, hence equals the same coefficient on the right,
which is 
$$ {1/2\choose n+1 }(-4)^{n+1}. $$
Therefore,
$$ C_{n} = -\frac{1}{2}{1/2\choose n+1 }(-4)^{n+1}. $$

Now writing out the binomial coefficient
$$ {1/2\choose n+1 } = \frac{(1/2)(-1/2)(-3/2)\cdots (-[2n-1]/2)}{(n+1)!} $$
and doing a bunch of messy cancellation with the 4's and the 2's and
the minus signs, you finally get the formula
$$ C_{n} = \frac{1}{n+1}{2n\choose n}. $$

From the formula, we get several more values: $C_{0} = 1$, $C_{1} =
1$, $C_{2} = 2$, $C_{3} = 5$, $C_{4} = 14$, $C_{5} = 42$, $C_{6} =
132$.

\bigskip

\noindent 4.  Things there are $C_{n}$ of.

Consider the {\it integer lattice} of all points in the plane with
integer coordinates $(i,j)$.  A {\it lattice path} is a path from one
point in the lattice to another that proceeds by steps of $+1$ in either
coordinate.  Consider the $n\times n$ square with lower left corner
$(0,0)$ and upper right corner $(n,n)$.  To get from $(0,0)$ to
$(n,n)$ by a lattice path, you must have $n$ up steps and $n$ right
steps.  You can mix these in any order, a total of ${2n\choose n }$
ways.

Now consider the problem, how many lattice paths from $(0,0)$ to
$(n,n)$ do not go above the main diagonal?

\vspace{1.2in}

We claim the answer is $C_{n}$ because there is a bijection with
balanced strings.  Namely, to any lattice path write down a string
using ``$($'' for every step to the right and ``$)$'' for each step
up.  Then the set of all lattice paths from $(0,0)$ to $(n,n)$
corresponds bijectively to the set of all ${2n\choose n}$ strings of
$n$ left and $n$ right parentheses, balanced or not.  A string is
balanced just in case the number of right parentheses never exceeds
the number of lefts as you scan it from left to right.  In the lattice
path, at each point $(i,j)$ $i$ is the number of left parentheses and
$j$ the number of rights.  Hence it corresponds to a balanced string
iff $i\geq j$ at every step, which is the same as saying the path
stays on or below the diagonal $i = j$.

A famous version of this problem is the ``ballot problem.''  In an
election, $A$ beats $B$ by $n+1$ votes to $n$.  In how many orders can
the votes be cast so that $A$ is ahead throughout?  Well, this means
the first vote must be for $A$.  Then $n$ votes for each remain and
they must be cast in such an order that the
number for $A$ to any point
is at least the number for $B$.  The pairs $(a,b)$ showing the tallies
for $A$ and $B$, excluding the first vote, then form a lattice path
not going above the diagonal, and there are $C_{n}$ of these.

Another thing $C_{n}$ counts is {\it ordered rooted trees} with $n$
nodes in addition to the root.  Here are some different ordered
rooted trees:

\vspace{1.2in}

Here the bijection uses the fact that
trees and parenthesis strings have the same recursive structure.
Namely, to the empty string, correspond the tree with only a root.  For
a general nonempty string $(aaaa)(bbbb)(cccc)\cdots (xxxx)$, take the trees
corresponding to the insides of each closed group $aaaa$, $bbbb$,
etcetera.  Then form a new tree $T$ by making each of these trees the
``branches'' of $T$, that is, their roots make up the first level of
$T$.  For example:


\vspace{1.2in}

Notice that the number of nodes is correct, since the tree
corresponding to each group has a root which contributes a new node to
$T$, giving one extra node for the parenthesis pair surrounding each
closed group.

\newpage

Catalan numbers also count {\it binary} trees.  These are like ordered
rooted trees, but above each node are at most two branches: the {\it
left} and the {\it right} branch.  Also, even if there is just one
branch above a node, we distinguish whether it is left or right, and
consider that the other branch is empty.  Here are examples of
different binary trees:

\vspace{1.2in}

To associate a binary tree to a balanced string, we need a binary
recursive structure.  We get it this way:  to the empty string
associate the empty tree.  For a general nonempty string, write it
as $(aaaa)bbbb$.  Thus $aaaa$ is the inside of the first closed group
as before, but $bbbb$ consists of all remaining closed groups in their
entirety.  The corresponding binary tree will be the one whose left
branch over the root corresponds to $aaaa$ and its right branch to $bbbb$.
For example:

\vspace{1.2in}

Note that in this correspondence the number $n$ of parenthesis pairs
equals the number of nodes {\it including} the root of the tree.

The tree interpretation of Catalan numbers can even be used to write
down the generating function $C(x)$ directly; in fact many kinds of
ordered trees can be counted easily with ordinary generating
functions.  Let's consider $C(x)$ as the generating function counting
binary trees, with weight $x^{n}$ where $n$ is the number of all
nodes.  A binary tree is either empty (weight 1) or consists of a
root, left subtree, and right subtree, all independently chosen.  The
root is a forced ``choice'' contributing 1 to the number of nodes and
thus a factor $x$ to the weight.  The left and right subtrees each
have $C(x)$ as generating function.  Thus we get the generating
function identity
$$ C(x) = 1+xC(x)^{2} $$
directly from the combinatorics.

A related example involves {\it strictly binary} trees.  In these,
each node is required to be either a leaf (no branches above) or to
have both left and right branches non-empty.  Also it's convenient to
require that the tree itself be non-empty (otherwise just add 1 to the
generating function to count the empty tree too).  Let $F(x)$ be the
generating function, weighted by $x^{n}$, $n$ the total number of
nodes.

A strictly binary tree is either just a root, or a root and two
independently chosen strictly binary subtrees (non-empty by
definition).  Thus
$$ F(x) = x + xF(x)^{2} $$
and so 
$$ F(x) = (1/2x)(1-\sqrt{1-4x^{2}}). $$
From this solution we see that $F(x) = xC(x^{2})$.  Now $xC(x^{2})$ is
just the Catalan number generating function but with each term
$C_{n}x^{n}$ changed to $C_{n}x^{2n+1}$.  This means that strictly
binary trees only exist with odd numbers of nodes and that $C_{n}$
is the number of those with $2n+1$ nodes.

A good exercise is to prove directly that every strictly binary tree
has an odd number of nodes and to find a bijection between strictly
binary trees with $2n+1$ nodes and binary trees with $n$ nodes.
 
\bigskip

\noindent 5. Ballot problem generalized.

\medskip

Above we saw that if $A$ beats $B$ by $n+1$ votes to $n$ then there
are $C_{n}$ balloting sequences where $A$ leads at all times.  More
generally, what if $A$ beats $B$ by $n+t$ votes to $n$?

Equivalently, we are counting lattice paths from $(0,0)$ to $(n+t,n)$
which lie {\it strictly} below the diagonal.  There is a  clever way of
counting these by a geometric  trick.  Remember we are really counting
paths from $(1,0)$ to $(n+t,n)$ since the first vote has to be for $A$.

To begin with, there are ${2n+t-1\choose n }$ lattice paths from $(1,0)$
to $(n+t,n)$ altogether.  Now we want to subtract the number that do
not stay below the diagonal.  Since we are only considering paths that
start at $(1,0)$ these are the paths that
cross the diagonal at some point $(i,i)$ with $i>0$.

To count these bad paths, consider for each bad path $P$ the path
$P'$ which you get by reflecting all of $P$ beyond the first bad point
$(i,i)$ about the diagonal.  Since the reflection of the endpoint
$(n+t,n)$ is $(n,n+t)$, $P'$ will be a path from $(1,0)$ to $(n,n+t)$.
On the other hand, every such path crosses the diagonal somewhere, 
and so is of the form $P'$ for some $P$.  
We therefore have a bijection between bad paths
from $(1,0)$ to $(n+t,n)$ and all paths from $(1,0)$ to $(n,n+t)$.
There are ${2n+t-1\choose n-1 }$ of the latter, so the solution of our
ballot problem is that there are
$$ {2n+t-1\choose n }-{2n+t-1\choose n-1 } =
\frac{t}{n+t}{2n+t-1\choose n } $$
good lattice paths, or balloting sequences.

When $t=1$ we are back to our original Catalan number case and the
solution just given of the ballot problem gives a direct combinatorial
proof of the formula 
$$ C_{n} = \frac{1}{n+1}{2n\choose n}. $$

\end{document}
