×

The uplift principle for ordered trees. (English) Zbl 1241.05019

Summary: We describe the uplift principle for ordered trees which lets us solve a variety of combinatorial problems in two simple steps. The first step is to find the appropriate generating function at the root of the tree, the second is to lift the result to an arbitrary vertex by multiplying by the leaf generating function. This paper, though self contained, is a companion piece to G.-S. Cheon and L. W. Shapiro [Appl. Math. Lett. 21, No. 5, 516–520 (2008; Zbl 1138.05308)] though with many more possible applications. It also may be viewed as an invitation, via the symbolic method, to the authoritative 800 page book of P. Flajolet and R. Sedgewick [Analytic combinatorics (2009; Zbl 1165.05001)]. Our examples, with one exception, are different from those in this excellent reference.

MSC:

05C05 Trees

Software:

OEIS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Sloane, N. J.A., The on-line encyclopedia of integer sequences · Zbl 1274.11001
[2] Cheon, G.-S.; Shapiro, L. W., Protected points in ordered trees, Appl. Math. Lett., 21, 516-520 (2008) · Zbl 1138.05308
[3] Harary, F.; Read, R. C., The enumeration of tree-like polyhexes, Proc. Edinb. Math. Soc. (2), 17, 1-13 (1970) · Zbl 0201.26104
[4] Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete Mathematics (1994), Addison-Wesley Publishing Company, p. 201 · Zbl 0836.00001
[5] Riordan, J., Combinatorial Identities (1968), Wiley, pp. 153-154 (problem 2)
[6] Wilf, H. S., Generatingfunctionology (1990), Academic Press, Harcourt Brace Jovanovich · Zbl 0689.05001
[7] Stanley, R. P., Enumerative Combinatorics, vol. 2 (1999), Cambridge Univ. Press · Zbl 0928.05001
[8] Flajolet, P.; Sedgewick, R., Analytic Combinatorics (2009), Cambridge University Press · Zbl 1165.05001
[9] Shapiro, L. W.; Getu, S.; Woan, W.-J.; Woodson, L., The Riordan group, Discrete Appl. Math., 34, 229-239 (1991) · Zbl 0754.05010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.