Abstract
Random Walks and Catalan Factorization
by: Omer Egecioglu and Alastair King
Abstract:
In the theory of random walks, it is notable that the central binomialcoefficients ${2n \\choose n}$ count the number of walks of three differentspecial types, which may be described as `balanced\', `non-negative\' and`non-zero\'. One of these coincidences is equivalent to the well-knownconvolution identity\\[\\sum_{p+q=n} {2p \\choose p}{2q \\choose q} = 2^{2n}.\\]This article brings together several proofs of this `ubiquity of centralbinomial coefficients\' by presenting various relations between these classes ofwalks and combinatorial constructions that lead to the convolution identity.In particular, new natural bijections for the convolution identity based on theunifying idea of Catalan factorization are described.
Keywords:
Central binomial coefficient, random walk, Dyck word, Catalanfactorization, bijection, convolution.
Date:
May 1999
Document: 1999-17
