پیوندهای مفید
آمار
| تعداد نشریات | 15 |
| تعداد شماره‌ها | 246 |
| تعداد مقالات | 2,509 |
| تعداد مشاهده مقاله | 4,499,825 |
| تعداد دریافت فایل اصل مقاله | 3,316,687 |
Counting vertices among all higher-dimensional plane trees | ||
| Journal of Discrete Mathematics and Its Applications | ||
| دوره 11، شماره 1، خرداد 2026، صفحه 59-80 اصل مقاله (329.92 K) | ||
| نوع مقاله: Full Length Article | ||
| شناسه دیجیتال (DOI): 10.22061/jdma.2025.12275.1146 | ||
| نویسندگان | ||
| Fidel Ochieng Oduol1؛ Isaac Owino Okoth* 2؛ Christopher Munyiwa Kaneba1 | ||
| 1Department of Mathematics, Physics and Computing, Moi University, Eldoret, Kenya. | ||
| 2Department of Pure and Applied Mathematics, School of Mathematics, Statistics and Actuarial Science, Maseno University, Maseno, Kenya | ||
| تاریخ دریافت: 28 تیر 1404، تاریخ بازنگری: 24 شهریور 1404، تاریخ پذیرش: 20 آبان 1404 | ||
| چکیده | ||
| In this paper, we study the enumeration of vertices in d-dimensional plane trees with respect to their levels and degrees. This class of trees generalizes both ordinary plane trees and noncrossing trees. Our approach builds upon a decomposition framework that extends the butterfly decomposition of plane trees introduced by Chen, Li and Shapiro, as well as that of noncrossing trees studied by Oduol and Okoth. We derive both explicit and asymptotic formulas for the enumeration of vertices, eldest children, first children, non-first children and non-leaves at specified levels and degrees. The results are obtained through a combination of generating function techniques, refined butterfly decompositions and bijective methods. This work extends previous enumeration results on ordinary plane trees and noncrossing trees and provides new insights into the combinatorial structure of their higher-dimensional analogues. | ||
| کلیدواژه‌ها | ||
| level؛ degree؛ eldest child؛ first child؛ leaf | ||
| مراجع | ||
|
[1] S. A. Abayo, I. O. Okoth, D. M. Kasyoki, Reachability in complete t-ary trees, Ann. Math. Comput. Sci. 18 (2023) 67–89. https://doi.org/10.56947/amcs.v18.191 [2] W. Y. C. Chen, N. Y. Li, L. W. Shapiro, The butterfly decomposition of plane trees, Discrete Appl. Math. 155(17) (2007) 2187–2201. https://doi.org/10.1016/j.dam.2007.04.020 [3] N. Dershowitz, S.Zaks, Enumerations of ordered trees, Discrete Math. 31(1) (1980) 9–28. https://doi.org/10.1016/0012-365X(80)90168-5 [4] S-P. Eu, S. Seo, H. Shin, Enumerations of vertices among all rooted ordered trees with levels and degrees, Discrete Math. 340(9) (2017) 2123–2129. https://doi.org/10.48550/arXiv.1605.00715 [5] N. S. S. Gu, H. Prodinger, S. Wagner, Bijections for a class of labeled plane trees, Europ. J. Combin. 31(3) (2010) 720–732. https://doi.org/10.1016/j.ejc.2009.10.007 [6] P. Flajolet, M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math. 204(1-3) (1999) 203–229. https://doi.org/https://doi.org/10.1016/S0012-365X(98)00372-0 [7] M. Noy, Enumeration of noncrossing trees on a circle, Discrete Math., 180(1-3) (1998) 301–313. https://doi.org/10.1016/S0012-365X(97)00121-0 [8] A. O. Nyariaro, I. O. Okoth, Reachability results in plane trees, Commun. Adv. Math. Sci. 4(2) (2021) 75–88. https://doi.org/10.33434/cams.936558 [9] A. O. Nyariaro, I. O. Okoth, F. O. Nyamwala, Generalized k-plane trees, J. Disc. Math. Appl. 10(2) (2025) 161–182. https://doi.org/10.22061/jdma.2025.11859.1122 [10] F. O. Oduol, I. O. Okoth, Counting vertices among all noncrossing trees by levels and degrees, Commun. Cryptogr. & Computer Sci. 2024(2) (2024) 193–212. https://doi.org/http://cccs.sgh.ac.ir/ Articles/2024/ issue2/2-7 [11] I. O. Okoth, Combinatorics of Oriented Trees and Tree-Like Structures, PhD Thesis, Stellenbosch University, 2015. https://scholar.sun.ac.za/server/api/core/bitstreams/345540f5-7912- 44dc-bd6a-d3b7f89c0df5/content [12] I. O. Okoth, D. M. Kasyoki, Generalized plane trees, (2024) Preprint. [13] I. O. Okoth, A. O. Nyariaro, Reachability results in labelled t-ary trees, Open J. Math. Sc. 5(1)(2021) 360–370. https://doi.org/10.30538/oms2021.0171 [14] S. X. M. Pang, L. Lv, K-noncrossing trees and K-proper trees, 2010 2nd International Conference on Information Engineering and Computer Science, Wuhan, (2010) 1–3. https://doi.org/10.1109/ICIECS.2010.5677757 [15] A. Panholzer, H. Prodinger, Bijection for ternary trees and non-crossing trees, Discret. Math. 250(1- 3) (2002) 115–125. https://doi.org/10.1016/S0012-365X(01)00282-5 [16] S. Seo, H. Shin, A refined enumeration of p-ary labeled trees, Korean J. Math. 21(4) (2013) 495–502. https://doi.org/10.11568/kjm.2013.21.4.495 [17] S. Seunghyun, H. Shin, A refinement for ordered labeled trees, Korean J. Math. 20(2) (2012) 225– 261. https://doi.org/10.11568/kjm.2012.20.2.255 [18] R. P. Stanley, Enumerative Combinatorics, Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 1999. https:// doi.org/10.1017/ CBO9780511609589 | ||
|
آمار تعداد مشاهده مقاله: 303 تعداد دریافت فایل اصل مقاله: 154 |
||