Balanced ordered trees. (English) Zbl 0808.05036
The paper gives various interesting exact and asymptotic results on the distribution of certain parameters of balanced ordered trees, such as the height, the number of leaves, the external path length and the degree of the root. A main tool to derive the asymptotics is the Mellin transform (attributed as the gamma-function method according to Knuth in this paper).
Reviewer: P.Kirschenhofer (Wien)
Online Encyclopedia of Integer Sequences:
Number of balanced ordered trees with n nodes.Number of compositions of the integer n in which the first part is >= the other parts.
Array F(k, n) read by descending antidiagonals: k-generalized Fibonacci numbers in row k >= 1, starting (0, 1, 1, ...), for column n >= 0.
References:
| [1] | Bender, J. Combinat Theory, Ser. A 15 pp 91– (1973) |
| [2] | Cella, Aequa. Math. 43 pp 94– (1992) |
| [3] | Advanced Combinatorics, Reidel, Dordrecht, 1974. · doi:10.1007/978-94-010-2196-8 |
| [4] | Handbook of Algorithms and Data Structures, Addison-Wesley, Reading, MA, 1984. · Zbl 0665.68001 |
| [5] | Fundamentals of the Average Case Analysis of Particular Algorithms, Wiley-Teubner, Chichester-Stuttgart, 1984. · Zbl 0638.68026 · doi:10.1007/978-3-663-12191-6 |
| [6] | The Art of Computer Programming: Sorting and Searching, Vol. 3, Addison-Wesley, Reading, MA, 1973. · Zbl 0302.68010 |
| [7] | Data Structures and Algorithms 1: Sorting and Searching, Springer-Verlag, Berlin/Heidelberg, 1984. |
| [8] | Meir, Can. J. Math 30 pp 997– (1978) · Zbl 0394.05015 · doi:10.4153/CJM-1978-085-0 |
| [9] | Odlyzko, Adv. Math. 44 pp 180– (1982) |
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.
