A recursive algorithm for trees and forests

Preprint English OPEN
Guo, Song; Guo, Victor J. W.;
(2017)

Trees or rooted trees have been generously studied in the literature. A forest is a set of trees or rooted trees. Here we give recurrence relations between the number of some kind of rooted forest with $k$ roots and that with $k+1$ roots on $\{1,2,\ldots,n\}$. Classical... View more
  • References (15)
    15 references, page 1 of 2

    [1] M. Aigner and G.M. Ziegler, Proofs from The Book, Fourth Ed., SpringerVerlag, Berlin, 2010.

    [2] T.L. Austin, The enumeration of point labelled chromatic graphs and trees, Canad. J. Math. 12 (1960), 535-545.

    [3] A. Cayley, A theorem on trees, Quart. J. Math. 23 (1889), 376-378.

    [4] W.Y.C. Chen, A general bijective algorithm for trees, Proc. Natl. Acad. Sci. USA 87 (1990), 9635-9639.

    [5] W.Y.C. Chen and V.J.W. Guo, Bijections behind the Ramanujan polynomials, Adv. Appl. Math. (2001), 336-356.

    [6] W.Y.C. Chen and J.F.F Peng, Disposition polynomials and plane trees, European J. Combin. 36 (2014), 122-129.

    [7] L.E. Clarke, On Cayley's formula for counting trees, J. London Math. Soc. 33 (1958), 26-28.

    [8] R.R.X. Du and J. Yin, Counting labelled trees with given indegree sequence, J. Combin. Theory Ser. A 117 (2010), 345-353.

    [9] O. Egˇecioˇglu and J.B. Remmel, Bijections for Cayley trees, spanning trees, and their q-analogues, J. Combin. Theory Ser. A 42 (1986), 15-30.

    [10] O. Egˇecioˇglu and J.B. Remmel, A bijection for spanning trees of complete multipartite graphs, Congr. Numer. 100 (1994), 225-243.

  • Metrics
Share - Bookmark