Counting trees using symmetries |
| |
Authors: | Olivier Bernardi Alejandro H Morales |
| |
Institution: | Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA |
| |
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 |
本文献已被 ScienceDirect 等数据库收录! |