Skip to Main Content

Proceedings of the American Mathematical Society

Published by the American Mathematical Society since 1950, Proceedings of the American Mathematical Society is devoted to shorter research articles in all areas of pure and applied mathematics.

ISSN 1088-6826 (online) ISSN 0002-9939 (print)

The 2024 MCQ for Proceedings of the American Mathematical Society is 0.85.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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

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
Similar Articles
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