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

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 n^{n}.
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).

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).

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.