×

Computation of the expected number of leaves in a tree having a given automorphism, and related topics. (English) Zbl 0763.05022

Summary: We derive explicit formulas for the expected number of leaves in a random rooted tree that is fixed by a given permutation of the nodes, and similarly for (unrooted) trees and endofunctions. The main tool is the cycle index series of a species. The cases of asymmetric rooted trees and \(\mathbb{R}\)-enriched trees and rooted trees are also discussed.

MSC:

05C05 Trees
05A19 Combinatorial identities, bijective combinatorics
05C80 Random graphs (graph-theoretic aspects)

Software:

Maple
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bender, E. A.; Goldman, J. R.: Enumerative uses of generating functions. Indiana univ. Math. J. 20, 753-765 (1971) · Zbl 0217.01803
[2] Bergeron, F.; Cartier, G.: Darwin: computer algebra and enumerative combinatorics. Lecture notes in computer science 294, 393-394 (1988)
[3] Bergeron, F.; Labelle, G.; Leroux, P.: Functional equations for data structures. Lecture notes in computer science 294, 73-80 (1988)
[4] Char, B. W.; Geddes, K. O.: Maple reference manual. Symbolic computation group (1988) · Zbl 0758.68038
[5] Constantineau, I.; Labelle, J.: On combinatorial structures kept fixed by the action of a given permutation. Stud. appl. Math. 84, 105-118 (1991) · Zbl 0749.05003
[6] Décoste, H.: Séries indicatrices d’espèces pondérées et q-analogues. Ph.d. thesis (1989)
[7] Doubilet, P.; Rota, G. -C.; Stanley, R. P.: The idea of generating function. Finite operator calculus, 83-134 (1975)
[8] Foata, D.; Schützenberger, M. -P.: Théorie géométrique des polynômes eulériens. Lecture notes in mathematics 138 (1970) · Zbl 0214.26202
[9] Goulden, I. P.; Jackson, D. M.: Combinatorial enumeration. (1983) · Zbl 0519.05001
[10] Joyal, A.: Une théorie combinatoire des séries formelles. Adv. math. 42, 1-82 (1981) · Zbl 0491.05007
[11] Joyal, A.: Foncteurs analytiques et espèces de structures. Lecture notes in mathematics 1234, 126-159 (1986)
[12] Labelle, G.: Une nouvelle démonstration combinatoire des formules d’inversion de Lagrange. Adv. math. 42, 217-247 (1981) · Zbl 0477.05007
[13] Labelle, G.: Some new computational methods in the theory of species. Lecture notes in mathematics 1234, 192-209 (1986)
[14] G. Labelle, On asymmetric structures, Discrete Math., to appear.
[15] Labelle, J.; Yeh, Y. N.: Combinatorial species of several variables. Rap. de rech. 61 (1988)
[16] Leroux, P.: Methoden der anzahlbestimmung für einige klassen von graphen. Bayreuth. math. Schr. 26, 1-36 (1988) · Zbl 0672.05043
[17] Meir, A.; Moon, J. W.; Mycielski, J.: Hereditarily finite sets and identity trees. J. combin. Theory ser. B 35, 142-155 (1983) · Zbl 0507.05025
[18] Moon, J. W.: Counting labelled trees. Canadian mathematical monographs 1 (1970) · Zbl 0214.23204
[19] Pólya, G.; Read, R. C.: Combinatorial enumeration of groups. Graphs and chemical compounds (1987)
[20] Robinson, R. W.: Enumeration of non-separable graphs. J. combin. Theory 9, 327-356 (1970) · Zbl 0217.02501
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.