<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume10 Issue2" %>
Counting Special Families of Labelled Trees
Chunwei Song
School of Mathematical Sciences, Peking University, Beijing 100871, P.R. China
csong@math.pku.edu.cn
Annals of Combinatorics 10 (2) p. 271-283 June, 2006
AMS Subject Classification: 05C30, 05A15, 05C05
Abstract:
A labelled tree rooted at its least labelled vertex is Least-Child-Being-Monk if it has the property that the least labelled child of 0 is a leaf. One of our main results is that the number of Least-Child-Being-Monk trees labelled on {0, 1, 2, бн , n+1} is equal to nn. More generally, let be the set of labelled trees on {0, 1, 2, бн, n+1}, such that the total number of descendants of the least labelled child of 0 is p. We prove that the cardinality of is equal to .
Furthermore, a labelled tree rooted at its least labelled vertex is Hereditarily-Least-Single if it has the property that every least child in this tree is a leaf. Let the number of Hereditarily-Least- Single trees with n vertices be hn. We find a functional equation for the generating function of h(n) and derive a recurrence that will quickly compute h(n).
Keywords: labelled tree, root, least child, generating function, hereditary, descendants

References:

1. N.H. Abel, Beweis eines Ausdrucks von welchem die Binomial-Formel ein einzelner Fall ist, J. Reine Angew. Math. 1 (1826) 159–160.

2. C. Berge, Graphs and hypergraphs, 2nd Ed., North-Holland Publishing Company, New York, 1976.

3. L.E. Clarke, On Cayley's formula for counting trees, J. London Math. Soc. 33 (1958) 471–474.

4. L. Comtet, Advanced Combinatorics, D. Reidel Publishing Company, 1974.

5. J. Haglund and N. Loehr, A conjectured combinatorial formula for the Hilbert series for diagonal harmonics, Discrete Math. 298 (1?3) (2005) 189–204.

6. J.W. Moon, Counting Labelled Trees, Canadian Mathematical Monographs, No. 1, Canadian Mathematical Congress, Montreal, 1970.

7. V. Strehl, Identities of Rothe-Abel-Schläfli-Hurwitz-type, Discrete Math. 99 (1-3) (1992) 321–340.

8. H.S.Wilf, generatingfunctionology, 2nd Ed., Academic Press, Boston, MA, 1994.