Pick two points in a tree
J. Korean Math. Soc. 2019 Vol. 56, No. 5, 1247-1263
https://doi.org/10.4134/JKMS.j180503
Published online September 1, 2019
Hana Kim, Louis W. Shapiro
Sungkyunkwan University; Howard University
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.
Keywords : ordered trees, probability, dependent vertices, independent vertices, Riordan matrices
MSC numbers : 05A15, 05A19, 60C05
Full-Text :

   

Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd