A recurrence related to trees
HTML articles powered by AMS MathViewer
- by Donald E. Knuth and Boris Pittel
- Proc. Amer. Math. Soc. 105 (1989), 335-349
- DOI: https://doi.org/10.1090/S0002-9939-1989-0949878-9
- PDF | Request permission
Abstract:
The asymptotic behavior of the solutions to an interesting class of recurrence relations, which arise in the study of trees and random graphs, is derived by making uniform estimates on the elements of a basis of the solution space. We also investigate a family of polynomials with integer coefficients, which may be called the "tree polynomials."References
- Gotthold Eisenstein, Entwicklung von $\alpha ^{\alpha ^{\alpha ^\vdots }}$, J. Reine Angew. Math. 28 (1844), 49-52.
- William Feller, An introduction to probability theory and its applications. Vol. II. , 2nd ed., John Wiley & Sons, Inc., New York-London-Sydney, 1971. MR 0270403
- Philippe Flajolet and Andrew Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math. 3 (1990), no. 2, 216–240. MR 1039294, DOI 10.1137/0403019
- Philippe Flajolet and Michèle Soria, Gaussian limiting distributions for the number of components in combinatorial structures, J. Combin. Theory Ser. A 53 (1990), no. 2, 165–182. MR 1041444, DOI 10.1016/0097-3165(90)90056-3
- Donald E. Knuth, An analysis of optimum caching, J. Algorithms 6 (1985), no. 2, 181–199. MR 789902, DOI 10.1016/0196-6774(85)90037-9
- Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms. MR 0378456
- Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
- Donald E. Knuth, The art of computer programming. Volume 3, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching. MR 0445948
- Donald E. Knuth and Arnold Schönhage, The expected linearity of a simple equivalence algorithm, Theoret. Comput. Sci. 6 (1978), no. 3, 281–315. MR 494197, DOI 10.1016/0304-3975(78)90009-9
- Martin D. Kruskal, The expected number of components under a random mapping function, Amer. Math. Monthly 61 (1954), 392–397. MR 62973, DOI 10.2307/2307900
- Alfréd Rényi, Some remarks on the theory of trees, Magyar Tud. Akad. Mat. Kutató Int. Közl. 4 (1959), 73–85 (English, with Russian and Hungarian summaries). MR 115938
- John Riordan, Combinatorial identities, John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR 0231725
- V. E. Stepanov, Limit distributions of certain characteristics of random mappings, Teor. Verojatnost. i Primenen. 14 (1969), 639–653 (Russian, with English summary). MR 0278350
Bibliographic Information
- © Copyright 1989 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 105 (1989), 335-349
- MSC: Primary 05A15; Secondary 05C30, 11B37, 68R05
- DOI: https://doi.org/10.1090/S0002-9939-1989-0949878-9
- MathSciNet review: 949878