Some Bijections and Identities for the Catalan and Fine Numbers
Séminaire lotharingien de combinatoire, Tome 53 (2005-2006)
Citer cet article
Voir la notice de l'acte provenant de la source Séminaire Lotharingien de Combinatoire website
We establish combinatorial interpretations of several identities for the Catalan and Fine numbers. Analytic proofs are outlined and we also give combinatorial proofs utilizing some new bijections of independent interest. We show that $ C_{n}=\frac{1}{n+1}\sum_{k}\binom{n+1}{2k+1} \binom{n+k}{k}$ counts ordered trees on n edges by number of interior vertices adjacent to a leaf and $ C_{n}=\frac{2}{n+1}\sum_{k}\binom{n+1}{k+2} \binom{n-2}{k}$ counts Dyck n-paths by number of long interior inclines. We also give an analogue for the Fine numbers of Touchard's Catalan number identity.