within Words - A Recursive Approach to the Catalan Numbers and Fine Numbers"
by David Vella.
In this talk, David presents a new recursive formula for the
Catalan numbers. The proof uses Dyck Words, one of the many objects
that are known to be counted by the Catalan numbers. Dyck Words are
strings of two distinct symbols - such as A and B, such that no initial segment
contains more B's than A's. Thus AABABB is a Dyck word of length 6
but ABBABA is not, since the initial segment ABB has too many B's. It is
well-known that the number of Dyck words of length 2n is given by Cn,
the nth Catalan number. We obtain our recursion by
"factoring" Dyck words into smaller Dyck words which appear inside
them. While this is a very satisfying proof of our recursion, we
also present a second proof, using generating functions, because this approach
can be modified to yield a new formula that expresses the nth Fine
number in terms of the Catalan numbers.