Congressus Numerantium, 138 (1999), pp. 129-140.
Ömer Egecioglu and Alastair King
Random Walks and Catalan Factorization
Abstract.
In the theory of random walks, it is notable that the
central binomial coefficients ${2n \choose n}$
count the number of walks of three different special types,
which may be described as `balanced', `non-negative'
and `non-zero'. One of these coincidences is equivalent to
the well-known convolution identity
$$\sum_{p+q=n} {2p \choose p}{2q \choose q} = 2^{2n}.$$
This article brings together several proofs of this
`ubiquity of central binomial coefficients'
by presenting various relations between these classes
of walks and combinatorial constructions that lead to
the convolution identity. In particular, new natural
bijections for the convolution identity based on the
unifying idea of Catalan factorization are described.
omer@cs.ucsb.edu