On an identity for the cycle indices of rooted tree automorphism groups

MaRDI QIDQ870039zbMATH OpenFDO

Authors Stephan Wagner

Publication date 12 March 2007

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/127476, http://www.emis.de/journals/EJC/Volume_13/Abstracts/v13i1n14.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

enumeration

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19) Enumeration in graph theory (05C30)

Review text

Summary: This note deals with a formula due to G. Labelle for the summed cycle indices of all rooted trees, which resembles the well-known formula for the cycle index of the symmetric group in some way. An elementary proof is provided as well as some immediate corollaries and applications, in particular a new application to the enumeration of \(k\)-decomposable trees. A tree is called \(k\)-decomposable in this context if it has a spanning forest whose components are all of size \(k\).

Recommendations

• On the number of decomposable trees
• scientific article; zbMATH DE number 94858
• Labeled trees, functions, and an algebraic identity
• A remark on the enumeration of rooted labeled trees
• Computation of the expected number of leaves in a tree having a given automorphism, and related topics

Cited in

(4)

• Cyclic renormalization and automorphism groups of rooted trees
• Decomposition of triply rooted trees
• Counting tanglegrams with species
• The cycle index of the automorphism group of Zn

This page was built for publication: On an identity for the cycle indices of rooted tree automorphism groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q870039)