Pick two points in a tree
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
In ordered trees, two randomly chosen vertices are said to be dependent if one lies under the other. If not, we say that they are independent. We consider several classes of ordered trees with uniform updegree requirements and find the generating functions for the trees with two marked dependent/independent vertices. As a result, we compute the probability for two vertices being dependent/independent. We also count such trees by the distance between two independent vertices.
Abstract
In ordered trees, two randomly chosen vertices are said to be dependent if one lies under the other. If not, we say that they are independent. We consider several classes of ordered trees with uniform updegree requirements and find the generating functions for the trees with two marked dependent/independent vertices. As a result, we compute the probability for two vertices being dependent/independent. We also count such trees by the distance between two independent vertices.
참고문헌 (10)
- Gi-Sang Cheon, "Profiles of ordered trees with mutation and associated Riordan matrices", Linear Algebra and its Applications, 511, pp.296~317 (2016), Elsevier BV[DOI]
- Gi-Sang Cheon, "Protected points in ordered trees", Applied Mathematics Letters, 21(5), pp.516~520 (2008), Elsevier BV[DOI]
- M. Drmota, "Random Trees" (2009), Springer Verlag
- P. Flajolet, "Analytic Combinatorics" (2009), Cambridge University Press
- R. L. Graham, "Concrete Mathematics, second edition" (1994), Addison-Wesley Publishing Company
- N. C. Jones, "An Introduction to Bioinformatics Algorithms" (2004), MIT Press
- C. Semple, "Phylogenetics" (2003), Oxford University Press
- "The on-line encyclopedia of integer sequences"[URL]
- Richard P. Stanley, "Hipparchus, Plutarch, Schroder, and Hough", The American Mathematical Monthly, 104(4), pp.344~ (1997), JSTOR[DOI]
- R. P. Stanley, "Enumerative Combinatorics. Vol. 2" (1999), Cambridge University Press