Journal of Integer Sequences, Vol. 20 (2017), Article 17.3.7

A Combinatorial Identity Concerning Plane Colored Trees and its Applications

Ricky X. F. Chen and Christian M. Reidys
Biocomplexity Institute and Department of Mathematics
Virginia Polytechnic Institute and State University
1015 Life Science Circle
Blacksburg, VA 24061


In this note, we obtain a combinatorial identity by counting some colored plane trees. This identity has a plethora of implications. In particular, it solves a bijective problem in Stanley's collection "Bijective Proof Problems", and gives a formula for the Narayana polynomials, as well as an equivalent expression for the Harer-Zagier formula enumerating unicellular maps.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A001263 A006318 A035309 A132393.)

Received September 13 2016; revised versions received January 18 2017; January 23 2017; January 25 2017. Published in Journal of Integer Sequences, January 26 2017.

Return to Journal of Integer Sequences home page