The Abstract

	Annals of Combinatorics 10 (2006) 271-283 Counting Special Families of Labelled Trees Chunwei Song School of Mathematical Sciences, Peking University, Beijing 100871, P.R. China csong@math.pku.edu.cn Received November 13, 2004 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 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). 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. Get the DVI \| PS \| PDF file of this abstract. back

Annals of Combinatorics 10 (2006) 271-283

Counting Special Families of Labelled Trees

Chunwei Song

School of Mathematical Sciences, Peking University, Beijing 100871, P.R. China
csong@math.pku.edu.cn

Received November 13, 2004

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

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.

Get the DVI | PS | PDF file of this abstract.

back