Record number :
Title of article :
Counting trees using symmetries
Author/Authors :
Bernardi، نويسنده , , Olivier and Morales، نويسنده , , Alejandro H.، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2014
Pages :
From page :
To page :
Abstract :
We prove a new formula for the generating function of multitype Cayley trees counted according to their degree distribution. Using this formula we recover and extend several enumerative results about trees. In particular, we extend some results by Knuth and by Bousquet-Mélou and Chapuy about embedded trees. We also give a new proof of the multivariate Lagrange inversion formula. Our strategy for counting trees is to exploit symmetries of refined enumeration formulas: proving these symmetries is easy, and once the symmetries are proved the formulas follow effortlessly. We also adapt this strategy to recover an enumeration formula of Goulden and Jackson for cacti counted according to their degree distribution.
Keywords :
Cayley trees , Vertical profile of trees , Lagrange inversion , Plane trees , Plane cacti
Journal title :
Journal of Combinatorial Theory Series A
Serial Year :
Link To Document :