Some Bijections and Identities for the Catalan and Fine Numbers
Séminaire lotharingien de combinatoire, Tome 53 (2005-2006)
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.
@article{SLC_2005-2006_53_a4,
author = {David Callan},
title = {Some {Bijections} and {Identities} for the {Catalan} and {Fine} {Numbers}},
journal = {S\'eminaire lotharingien de combinatoire},
publisher = {mathdoc},
volume = {53},
year = {2005-2006},
url = {http://geodesic.mathdoc.fr/item/SLC_2005-2006_53_a4/}
}
David Callan. Some Bijections and Identities for the Catalan and Fine Numbers. Séminaire lotharingien de combinatoire, Tome 53 (2005-2006). http://geodesic.mathdoc.fr/item/SLC_2005-2006_53_a4/