آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 126 |
| تعداد مقالات | 1,593 |
| تعداد مشاهده مقاله | 1,807,769 |
| تعداد دریافت فایل اصل مقاله | 1,674,349 |
Path length and Sackin index of random $m$-oriented recursive trees | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 17 شهریور 1405 | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2026.31556.2887 | ||
| نویسندگان | ||
| Ramin Kazemi* ؛ Sedigheh Zamani Mehreyan | ||
| Department of Statistics, Imam Khomeini International University, Qazvin, Iran | ||
| چکیده | ||
| The main purpose of this article is to study of two distance-based quantities, internal path length and Sackin index, in random $m$-oriented recursive trees. Unlike the traditional method, the mean and variance of the internal path length are directl} calculated through a simple recurrence. The complexity of the calculations is due to the dependence of the probability of attracting a new node on the outdegree of the node. We show that there exists a random variable $I$ such that $\frac{I_n -\frac nm \log n}{mn}\to I$ almost surely and in $L^2$, as $n\to\infty$. Then, under two assumptions, some results related to the Sackin index of these tree models are given. Specifically, based on Chebychev’s inequality, we show that $\frac{(m+1)S_n}{n\log n}\to 1$ in probability. | ||
| کلیدواژهها | ||
| Random $m$-oriented recursive tree؛ internal path length؛ Sackin index؛ limiting rule | ||
| مراجع | ||
|
1] T.M. Coronado, A. Mir, F. Rossello, and L. Rotger, On Sackin’s original proposal: the variance of the leaves’ depths as a phylogenetic balance index, BMC Bioinformatics 21 (2020), no. 1, 154. https://doi.org/10.1186/s12859-020-3405-1
[2] R.P. Dobrow and R.T. Smythe, Poisson approximations for functionals of random trees, Random Structures and Algorithms 9 (1996), no. 1-2, 79–92.
[3] P. Hall and C.C. Heyde, Martingale Limit Theory and its Application, Academic Press, New York, 1980.
[4] M. Javanian and M.Q. Vahidi-Asl, External path length of random $m$-oriented recursive trees, J. Natural Sci. Math. 50 (2010), no. 1-2, 11–18.
[5] R. Kazemi, On the multiplicative Zagreb indices of bucket recursive trees, Iranian J. Math. Chem. 8 (2017), no. 1, 37–45. https://doi.org/10.22052/ijmc.2017.15385 [6] R. Kazemi, Total path length and Sackin index of random recursive trees, 14th Iranian Statistics Conference, 2018, pp. 420–425.
[7] R. Kazemi and A. Behtoei, The moments of the Sackin index of random d-ary increasing trees, Mathematicki Vesnik 73 (2021), no. 1, 55–62.
[8] M.C. King and N.A. Rosenberg, A simple derivation of the mean of the Sackin index of tree balance under the uniform model on rooted binary labeled trees, Math. Biosci. 342 (2021), 108688. https://doi.org/10.1016/j.mbs.2021.108688
[9] H.M. Mahmoud, Distances in random plane-oriented recursive trees, J. Comput. Appl. Math. 41 (1992), no. 1-2, 237–245. https://doi.org/10.1016/0377-0427(92)90252-S
[10] A. Mir, F. Rossello, and L. Rotger, A new balance index for phylogenetic trees, Math. Biosci. 241 (2013), no. 1, 125–136. https://doi.org/10.1016/j.mbs.2012.10.005 [11] B. Pittel, Note on the heights of random recursive trees and random m-ary search trees, Random Structures and Algorithms 5 (1994), no. 2, 337–347. https://doi.org/10.1002/rsa.3240050207
[12] M.J. Sackin, Good and bad phenograms, Systematic Biology 21 (1972), no. 2, 225–226. https://doi.org/10.1093/sysbio/21.2.225 | ||
|
آمار تعداد مشاهده مقاله: 1 |
||