A derivation of the Catalan numbers from a bijection between permutations and labeled trees

2001/12/11 by Bennet Vance, Vance, Bennet
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

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

10 pages

arxiv created 2001/12/11 · arxiv updated 2009/11/30

Abstract

We present an algorithmic mapping from permutations of length dn to labeled n-node d-ary trees and back again. Given such a bijection, one can interpret each of the factorials in the formula for the Catalan numbers as a count of permutations.

Related

• Modular Catalan Numbers
• Some identities for the Catalan and Fine numbers
• Continued fractions and Catalan problems
• More bijective Catalan combinatorics on permutations and on signed\n permutations
• Variations of the Catalan numbers from some nonassociative binary operations