Some identities for the Catalan and Fine numbers

2005/02/25 by David Callan, Callan, David · 1 citation
Mathematics · Physics and Astronomy · #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Advanced Mathematical Theories and Applications #math.CO #msc:05A15 #msc:05A19

paper · pdf · doi:10.48550/arxiv.math/0502532

LaTeX, 17 pages

arxiv created 2005/02/25 · arxiv updated 2009/12/01

Abstract

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 = 1/(n+1) Sum_k (n+1)choose(2k+1) (n+k)choose(k) counts ordered trees on n edges by number of interior vertices adjacent to a leaf, and C_n = 2/(n+1) Sum_k (n+1)choose(k+2) (n-2)choose(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.

Cited by

• Extending Fine sequences: a link with forbidden patterns

Related

• On Enumeration of Dyck Paths with colored hills
• Combinatorial proofs of totals of some statistics on Catalan words
• A derivation of the Catalan numbers from a bijection between permutations and labeled trees
• A variant of Touchard's Catalan number identity
• Identities involving weighted Catalan, Schroder and Motzkin paths