Some Identities for the Catalan and Fine Numbers
We establish combinatorial interpretations of several identities for the Catalan
and Fine numbers and, along the way, we present some new bijections of independent interest.
Briefly, 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.
