Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

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

 
 

 

A recurrence related to trees


Authors: Donald E. Knuth and Boris Pittel
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
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Gotthold Eisenstein, Entwicklung von $ {\alpha ^{{\alpha ^{{\alpha ^ {\mathinner{\mkern2mu\raise1pt\hbox{.}\mkern2mu \raise4pt\hbox{.}\mkern2mu\raise7pt\hbox{.}\mkern1mu}} }}}}}$, J. Reine Angew. Math. 28 (1844), 49-52.
  • [2] William Feller, An introduction to probability theory and its applications, Vol. 2, Wiley, New York, 1971. MR 0270403 (42:5292)
  • [3] Philippe Flajolet and Andrew Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math. (to appear). MR 1039294 (90m:05012)
  • [4] Philippe Flajolet and Michèle Soria, Gaussian limiting distributions for the number of components in combinatorial structures, J. Combin. Theory Ser. A (to appear). MR 1041444 (91c:05012)
  • [5] Donald E. Knuth, An analysis of optimum caching, J. Algorithms 6 (1985), 181-199. MR 789902 (86j:68027)
  • [6] -, The art of computer programming, Vol. 1 : Fundamental algorithms, Addison-Wesley, Reading, Mass., 1973. MR 0378456 (51:14624)
  • [7] -, The art of computer programming, Vol. 2: Seminumerical algorithms, Addison-Wesley, Reading, Mass., 1981. MR 633878 (83i:68003)
  • [8] -, The art of computer programming, Vol. 3: Sorting and searching, Addison-Wesley, Reading, Mass., 1973. MR 0445948 (56:4281)
  • [9] Donald E. Knuth and Arnold Schönhage, The expected linearity of a simple equivalence algorithm, Theoret. Comput. Sci. 6 (1978), 281-315. MR 494197 (81a:68049)
  • [10] Martin Kruskal, The expected number of components under a random mapping function, Amer. Math. Monthly 61 (1954), 392-397. MR 0062973 (16:52b)
  • [11] Alfred Rényi, Some remarks on the theory of trees, Publ. Math. Inst. Hungar. Acad. Sci. 4 (1959), 73-85. MR 0115938 (22:6735)
  • [12] John Riordan, Combinatorial identities, Wiley, New York, 1968. MR 0231725 (38:53)
  • [13] V. E. Stepanov, Predel'nye raspredelen{\t{\i\/}}\kern.15ema nekotorykh kharakteristik sluchaĭnykh otobrazheniĭ, Teor. Vero{\t{\i\/}}\kern.15ematnost. Primenen. 14 (1969), 639-653; English transl., Limit distributions of certain characteristics of random mappings, Theor. Probab. Appl. 14 (1969), 612-626. MR 0278350 (43:4080)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05A15, 05C30, 11B37, 68R05

Retrieve articles in all journals with MSC: 05A15, 05C30, 11B37, 68R05


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1989-0949878-9
Article copyright: © Copyright 1989 American Mathematical Society

American Mathematical Society