Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-08T09:35:30.991Z Has data issue: false hasContentIssue false
  • English
  • Français

The Distribution of Patterns in Random Trees

Published online by Cambridge University Press:  01 January 2008

FRÉDÉRIC CHYZAK ,
MICHAEL DRMOTA ,
THOMAS KLAUSNER  and
GERARD KOK
FRÉDÉRIC CHYZAK
Affiliation:
INRIA-Rocquencourt, F-78153 Le Chesnay cedex, France (e-mail: frederic.chyzak@inria.fr)
MICHAEL DRMOTA
Affiliation:
Institut für Diskrete Mathematik und Geometrie, Technische Universität Wien, Wiedner Hauptstraße 8-10/113, A-1040 Wien, Austria (e-mail: michael.drmota@tuwien.ac.at, klausner@dmg.tuwien.ac.at)
THOMAS KLAUSNER
Affiliation:
Institut für Diskrete Mathematik und Geometrie, Technische Universität Wien, Wiedner Hauptstraße 8-10/113, A-1040 Wien, Austria (e-mail: michael.drmota@tuwien.ac.at, klausner@dmg.tuwien.ac.at)
GERARD KOK
Affiliation:
Delft Institute of Applied Mathematics, Delft University of Technology, Mekelweg 4, NL-2628 CD Delft, The Netherlands (e-mail: gkok@fsmat.at)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let $\Tn{}$ denote the set of unrooted labelled trees of size n and let ℳ be a particular (finite, unlabelled) tree. Assuming that every tree of $\Tn{}$ is equally likely, it is shown that the limiting distribution as n goes to infinity of the number of occurrences of ℳ is asymptotically normal with mean value and variance asymptotically equivalent to μn and σ2n, respectively, where the constants μ>0 and σ≥0 are computable.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 1 , January 2008 , pp. 21 - 59
Copyright
Copyright © Cambridge University Press 2007

References

[1]Aho, A. V., Sethi, R. and Ullman, J. D. (1986) Compilers: Principles, Techniques, and Tools, Addison-Wesley.Google Scholar
[2]Bender, E. A. and Richmond, L. B. (1983) Central and local limit theorems applied to asymptotic enumeration II: Multivariate generating functions. J. Combin. Theory Ser. A 34 255–265.CrossRefGoogle Scholar
[3]Drmota, M. (1994) Asymptotic distributions and a multivariate Darboux method in enumeration problems. J. Combin. Theory Ser. A 67 169–184.CrossRefGoogle Scholar
[4]Drmota, M. (1997) Systems of functional equations. Random Struct. Alg. 10 103–124.3.0.CO;2-Z>CrossRefGoogle Scholar
[5]Drmota, M. and Gittenberger, B. (1999) The distribution of nodes of given degree in random trees. J. Graph Theory 31 227–253.3.0.CO;2-6>CrossRefGoogle Scholar
[6]Dershowitz, N. and Zaks, S. (1989) Patterns in trees. Discrete Appl. Math. 25 241–255.CrossRefGoogle Scholar
[7]Flajolet, P., Gourdon, X. and Martínez, C. (1997) Patterns in random binary search trees. Random Struct. Alg. 11 223–244.3.0.CO;2-2>CrossRefGoogle Scholar
[8]Flajolet, P. and Sedgewick, R. (2006) Analytic Combinatorics. http://algo.inria.fr/flajolet/Publications/books.htmlGoogle Scholar
[9]Flajolet, P. and Steyaert, J.-M. (1980) On the analysis of tree-matching algorithms. In Automata, Languages and Programming: Proc. Seventh Internat. Colloq., Noordwijkerhout, 1980 (Bhattacharjee, G. P., ed.), Vol. 85 of Lecture Notes in Computer Science, Springer, Berlin, pp. 208–219.Google Scholar
[10]Flajolet, P. and Steyaert, J.-M. (1980) On the analysis of tree-matching algorithms. In Trees in Algebra and Programming: Proc. 5th Lille Colloq., Lille, 1980, University of Lille I, pp. 22–40.Google Scholar
[11]Kok, G. (2005) Pattern distribution in various types of random trees. In 2005 International Conference on Analysis of Algorithms, pp. 223–230.CrossRefGoogle Scholar
[12]Kok, G. J. P. (2005) The distribution of patterns in random trees. Thesis, Institut für Diskrete Mathematik und Geometrie, TU Wien, Austria.Google Scholar
[13]Lalley, S. Random walks on infinite free products and infinite algebraic systems of generating functions. http://www.stat.uchicago.edu/~lalley/Papers.Google Scholar
[14]Meir, A. and Moon, J. W. (1978) On the altitude of nodes in random trees. Canad. J. Math. 30 997–1015.CrossRefGoogle Scholar
[15]Otter, R. (1948) The number of trees. Ann. of Math. (2) 49 583–599.CrossRefGoogle Scholar
[16]Robinson, R. W. and Schwenk, A. J. (1975) The distribution of degrees in a large random tree. Discrete Math. 12 359–372.CrossRefGoogle Scholar
[17]Ruciński, A. (1988) When are small subgraphs of a random graph normally distributed? Probab. Theory Rel. Fields 78 1–10.CrossRefGoogle Scholar
[18]Steyaert, J.-M. and Flajolet, P. (1983) Patterns and pattern-matching in trees: An analysis. Inform. Control 58 19–58.CrossRefGoogle Scholar