Counting trees using symmetries. (English) Zbl 1281.05079
Summary: 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 D. E. Knuth [Can. J. Math. 20, 1077–1086 (1968; Zbl 0175.21001)] and by M. Bousquet-Mélou and G. Chapuy [Electron. J. Comb. 19, No. 3, Research Paper P46, 61 p. (2012; Zbl 1253.05081)] 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.
MSC:
| 05C30 | Enumeration in graph theory |
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
| 05C05 | Trees |
| 05C15 | Coloring of graphs and hypergraphs |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
References:
| [1] | Bender, E. A.; Richmond, L. B., A multivariate Lagrange inversion formula for asymptotic calculations, Electron. J. Combin., 5, R33 (1998) · Zbl 0901.05005 |
| [2] | Bóna, M.; Bousquet, G.; Labelle, M.; Leroux, P., Enumeration of m-ary cacti, Adv. in Appl. Math., 24, 1, 22-56 (2000) · Zbl 0957.05056 |
| [3] | Bousquet, M.; Chauve, C.; Labelle, G.; Leroux, P., Two bijective proofs for the arborescent form of the Good-Lagrange formula and some applications to colored rooted trees and cacti, Theoret. Comput. Sci., 307, 2, 277-303 (2003) · Zbl 1048.05025 |
| [4] | Bousquet-Mélou, M.; Chapuy, G., The vertical profile of embedded trees, Electron. J. Combin., 19, P46 (2012) · Zbl 1253.05081 |
| [5] | Ehrenborg, R.; Méndez, M., A bijective proof of infinite variated Goodʼs inversion, Adv. Math., 103, 2, 221-259 (1994) · Zbl 0810.05070 |
| [6] | Flajolet, P.; Sedgewick, R., Analytic Combinatorics (2009), Cambridge University Press · Zbl 1165.05001 |
| [7] | Gessel, I. M., A combinatorial proof of the multivariable Lagrange inversion formula, J. Combin. Theory Ser. A, 45, 2 (1987) · Zbl 0651.05009 |
| [8] | Good, I. J., Generalizations to several variables of Lagrangeʼs expansion, with applications to stochastic processes, Proc. Cambridge Philos. Soc., 56, 367-380 (1960) · Zbl 0135.18802 |
| [9] | Goulden, I. P.; Jackson, D. M., The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group, European J. Combin., 13, 5, 357-365 (1992) · Zbl 0804.05023 |
| [10] | Goulden, I. P.; Kulkarni, D. M., Multivariable Lagrange inversion, Gessel-Viennot cancellation, and the matrix tree theorem, J. Combin. Theory Ser. A, 80, 2, 295-308 (1997) · Zbl 0887.05005 |
| [11] | Jackson, D. M., Some combinatorial problems associated with products of conjugacy classes of the symmetric group, J. Combin. Theory Ser. A, 49, 2 (1988) · Zbl 0682.20002 |
| [12] | Joyal, A., Une théorie combinatoire des séries formelles, Adv. Math., 42, 1-82 (1981) · Zbl 0491.05007 |
| [13] | Knuth, D. E., Another enumeration of trees, Canad. J. Math., 20, 1077-1086 (1968) · Zbl 0175.21001 |
| [14] | Lando, S. K.; Zvonkin, A. K., Graphs on Surfaces and Their Applications (2004), Springer-Verlag · Zbl 1040.05001 |
| [15] | Moon, J. W., Counting Labelled Trees, Canad. Math. Monogr. (1970) · Zbl 0214.23204 |
| [16] | Pitman, J., Coalescent random forests, J. Combin. Theory Ser. A, 85, 2, 165-193 (1999) · Zbl 0918.05042 |
| [17] | Prüfer, H., Neuer Beweis eines Satzes über Permutationen, Arch. Math. Phys., 27, 742-744 (1918) · JFM 46.0106.04 |
| [18] | Stanley, R. P., Enumerative Combinatorics, vol. 2 (1999), Cambridge University Press · Zbl 0928.05001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
