Counting formulas for weakly labelled plane tree-like structures

Document Type : Full Length Article

Authors

Department of Pure and Applied Mathematics, Maseno University, Maseno, Kenya

Abstract

Block graphs have been enumerated by various authors. In this paper, plane tree-like structures in which the blocks are labelled with integers in the set {1,2,...,k} such that the labels of the blocks are non-decreasing from left to right are introduced. These tree-like structures are called weakly labelled k-plane tree-like structures herein. Using symbolic method, generating functions and application of Lagrange-B\"{u}rmann inversion, the structures are counted by number of vertices, blocks, occurrences of labels, root degree and label of the eldest/youngest block child of the root, number of leaves, forests and outdegree sequence.

Graphical Abstract

Counting formulas for weakly labelled plane tree-like structures

Keywords

Main Subjects


[1] S. A. Abayo, I. O. Okoth, D. M. Kasyoki, Generalization of plane tree-like structures, Preprint
(2025).
[2] M. Bona, M. Bousquet, G. Labelle, F. Leroux, Enumeration of ´ m-ary cacti, Adv. in Appl. Math. 24(1)
(2000) 22-56. https://doi.org/10.48550/arXiv.math/9804119
[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] N. S. S. Gu, H. Prodinger, S. Wagner, Bijections for a class of labelled plane trees, Europ. J. Combin.
31(3) (2010) 720–732. https://doi.org/10.1016/J.EJC.2009.10.007
[5] F. Harary, G. E. Uhblenbeck, On the number of Husimi trees, Proc. Nat. Aca. Sci. 39(4) (1953) 315–322. https://doi.org/10.1073/pnas.39.4.315
[6] K. Husimi, Note on Mayer’s theory of cluster integrals, J. Chem. Phys. 18 (1950) 682–684.
https://doi.org/10.1063/1.1747725
[7] Y. W. Kariuki, I. O. Okoth, Bijections of Plane Husimi graphs and certain combinatorial structures,
Eur. J. Math. Appl. 3 (2023) 21. https://doi.org/10.28919/ejma.2023.3.21
[8] Y. W. Kariuki, I. O. Okoth, Enumeration and bijections of a class of labelled plane trees and related
structures, Preprint (2024).
[9] I. Kucukoglu, Y. Simsek, Combinatorial identities associated with new families of the numbers and polynomials and their approximation values, arXiv preprint arXiv:1711.00850 (2017).
https://doi.org/10.48550/arXiv.1711.00850
[10] P. Leroux, Enumerative problems inspired by Mayer’s theory of cluster integrals, Electron. J. Combin. 11(1) (2004) #R32. https://doi.org/10.37236/1785
[11] J. E. Mayer, Equilibrium Statistical Mechanics: The International Encyclopedia of Physical Chemistry and Chemical Physics, Pergamon Press, Oxford, 1968. https:// api.pageplace.de/ preview/
DT0400.9781483224763 A23864914.pdf
[12] M. Noy, Enumeration of noncrossing trees on a circle, Disc. Math. 180 (1998) 301–313.
https://doi.org/10.1016/S0012-365X(97)00121
[13] A. P. O. Nyariaro, I. O. Okoth, Bijections for classes of labelled trees, Trans. Combin. 13 (2024)
197–211. https://doi.org/10.22108/toc.2023.132794.1965
[14] A. O. Nyariaro, I. O. Okoth, Enumeration of k-plane trees and forests, Commun. Cryptogr. & Computer Sci. 2 (2024) 152–168. http://cccs.sgh.ac.ir/Articles/2024/issue 2/2-4
[15] A. O. Odwali, I. O. Okoth, D. M. Kasyoki, Forests of tree-like structures, Preprint (2025).
[16] I. O. Okoth, Bijections of k-plane trees, Open J. Discret. Appl. Math. 5(1) (2022) 29–35.
https://doi.org/10.30538/psrp-odam2022.0068
[17] 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-bd6ad3b7f89c0df5
[18] I. O. Okoth, On noncrossing and plane tree-like structures, Commun. Adv. Math. Sc. 4 (2021) 89–99. https://doi.org/10.33434/cams.803065
[19] I. O. Okoth, S. Wagner, Refined enumeration of k-plane trees and k-noncrossing trees, Ann. Combin. (2024) 1–33. https://doi.org/10.48550/arXiv.2205.01002
[20] C. A. Onyango, I. O. Okoth, D. M. Kasyoki, Enumeration of plane and d-ary tree-like structures, Ann. Math. Comp. Sci. 17 (2023) 10–25. https://annalsmcs.org/ index.php/amcs/ article/view/190/113
[21] C. Springer, Factorizations, Tree and Cacti, Proceedings of the Eight International Conference on Formal power Series and Algebraic Combinatorics (FPSAC), University of Minnesota (1996) 427–438.
[22] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge, 1999.
https://doi.org/10.1017/CBO9780511609589
[23] H. S. Wilf, Generating functionology, A. K. Peters Ltd., Natick, MA, USA, 2006. https://www2.math.upenn.edu/ wilf/ gfology2.pdf
Volume 10, Issue 3
September 2025
Pages 243-261
  • Receive Date: 16 March 2025
  • Revise Date: 10 April 2025
  • Accept Date: 21 April 2025
  • First Publish Date: 15 July 2025
  • Publish Date: 01 September 2025