On sequential growth of trees subject to various labeling constraints: from enumeration to probability theory

Document Type : Original Article

Author

• Thierry Huillet

Laboratoire de Physique Théorique et Modélisation. CY Cergy Paris University, France

10.22067/smps.2024.45214

Abstract

Trees, as loop-free graphs, are fundamental hierarchical structures of Nature. Depending on the way their constitutive atoms are labeled, their growth obeys different sequential dynamics when a new atom is being appended to a current tree, possibly forming a new tree. Randomized versions of the underlying counting problems are shown to lead, in general, to Markovian triangular sequences.

Keywords

• Combinatorial probability
• Distinguishability
• Forests
• Markovian‎ ‎triangular sequences
• Randomization
• Simply generated and increasing trees

---

References

1.  Mahmoud, H., Smythe, R. T. and Szymanski, J. (1993). On the structure of random planeoriented recursive trees and their branches. Random Structures and Algorithms, 4, 151–176.
2. Meir, A. and Moon, J. W. (1978). On the altitude of nodes in random trees. Canadian Journal of Mathematics, 30, 997–1015.
3. Neveu, J. (1986) Arbres et processus de Galton-Watson. Annales Institue Henri Poincaré Probabilités et Statistiques 22, 199–207.
4. Pitman, J. (1998). Enumerations of trees and forests related to branching processes and random walks. In: Microsurveys in Discrete Probability Edited by: D Aldous, J Propp. 163–180. Providence RI: American Mathematical Society.
5. Pittel, B. (1994). Note on the heights of random recursive trees and random m-array search trees. Random Structures and Algorithms, 5, 337–347.
6. Rényi, A. (1959). Some remarks on the theory of trees. Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei, 4, 73–85.
7. Rényi, A. and Szekeres, G. (1967). On the height of trees. Australian Journal of Mathematics, 1, 497–507.
8. Steele, J. M. (1987). Gibbs’measures on combinatorial objects and the central limit theorem for an exponential family. Probability in the Engineering and Informational Sciences, 1, 47–59.
9. Surya, E. and Warnke, L. (2023). Lagrange inversion formula by induction. The American Mathematical Monthly, 130, 944–948.
10. Takács, L. (1990). On Cayley’s formula for counting forests. Journal of Combinatorial Theory, Series A, 53, 321–323.
11. Panholzer, A. and Prodinger, H. (2007). Level of nodes in increasing trees revisited. Random Structures and Algorithms, 31, 203–226.
12. Wolfram: https://mathworld.wolfram.com/Tree.html