Combinatorial Interpretation of Raney Numbers and Tree Enumerations

Chin Hee Pah^1*, Mohamed Ridza Wahiddin²

¹Department of Computational and Theoretical Sciences, Faculty of Science, International Islamic University Malaysia, Kuantan, Malaysia.
²Department of Computer Science, Faculty of ICT, International Islamic University Malaysia, Kuala Lumpur, Malaysia.

DOI: 10.4236/ojdm.2015.51001                

Abstract

A new combinatorial interpretation of Raney numbers is proposed. We apply this combinatorial interpretation to solve several tree enumeration counting problems. Further a generalized Catalan triangle is introduced and some of its properties are proved.

Keywords

Raney Numbers, Fuss-Catalan Numbers, Tree Enumeration, Network

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Penson, K.A. and Zyczkowski, K. (2011) Product of Ginibre Matrices: Fuss-Catalan and Raney Distributions. Physical Review E, 83, Article ID: 061118. http://dx.doi.org/10.1103/PhysRevE.83.061118
[2]	Mlotkowski, W., Penson, K.A. and Zyczkowski, K. (2013) Densities of the Raney Distributions. Documenta Mathematica, 18, 1573-1596.
[3]	Jeurissen, R.H. (2008) Raney and Catalan. Discrete Mathematics, 308, 6298-6307. http://dx.doi.org/10.1016/j.disc.2007.11.068
[4]	Dziemiaczuk, M. (2014) Enumerations of Plane Trees with Multiple Edges and Raney Lattice Paths. Discrete Mathematics, 337, 9-24. http://dx.doi.org/10.1016/j.disc.2014.07.024
[5]	Gould, H.W. (1972) Combinatorial Identities: A Standardized Set of Tables Listing 500 Binomial Coefficient Summations. Morgantown.
[6]	(2011) The On-Line Encyclopedia of Integer Sequences. Sequence A196678. http://oeis.org
[7]	Graham, R.L., Knuth, D.E. and Patashnik, O. (1994) Concrete Mathematics. Addison-Wesley, Boston.
[8]	Hilton, P. and Pedersen, J. (1991) Catalan Numbers, Their Generalization, and Their Uses. Mathematical Intelligencer, 13, 64-75. http://dx.doi.org/10.1007/BF03024089
[9]	Koshy, T. (2008) Catalan Numbers with Applications. Oxford University Press, USA. http://dx.doi.org/10.1093/acprof:oso/9780195334548.001.0001
[10]	Stanley, R.P. (2013) Catalan Addendum to Enumerative Combinatorics. Vol. 2.
[11]	Stanley, R.P. (1999) Enumerative Combinatorics. Vol. 2, Cambridge University Press, Cambridge. http://dx.doi.org/10.1017/CBO9780511609589
[12]	Baxter, R.J. (1982) Exactly Solved Models in Statistical Mechanics. Academic Press, London.
[13]	Goltsev, A.V., Dorogovtsev, S.N. and Mendes, J.F.F. (2008) Critical Phenomena in Complex Networks. Reviews of Modern Physics, 80, 1275. http://dx.doi.org/10.1103/RevModPhys.80.1275
[14]	Tamm, U. (2001) Some Aspects of Hankel Matrices in Coding Theory and Combinatorics. The Electronic Journal of Combinatorics, 8, 1-31.
[15]	Lee, K., Jung, W.S., Park, J.S. and Choi, M.Y. (2000) Statistical Analysis of the Metropolitan Seoul Subway System: Network Structure and Passenger Flows. Physica A, 387, 6231-6234. http://dx.doi.org/10.1016/j.physa.2008.06.035
[16]	Aval, J.C. (2008) Multivariate Fuss-Catalan Numbers. Discrete Mathematics, 308, 4660-4669. http://dx.doi.org/10.1016/j.disc.2007.08.100
[17]	Shapiro, L.W. (1976) A Catalan Triangle. Discrete Mathematics, 14, 83-90. http://dx.doi.org/10.1016/0012-365X(76)90009-1
[18]	Merlini, D., Sprugnoli, R. and Verri, M.C. (2006) Lagrange Inversion: When and How. Acta Applicandae Mathematica, 94, 233-249. http://dx.doi.org/10.1007/s10440-006-9077-7
[19]	Pah, C.H. (2008) An Application of Catalan Number on Cayley Tree of Order 2: Single Polygon Counting. Bulletin of the Malaysian Mathematical Sciences Society, 31, 175-183.
[20]	Pah, C.H. (2010) Single Polygon Counting on Cayley Tree of Order 3. Journal of Statistical Physics, 140, 198-207. http://dx.doi.org/10.1007/s10955-010-9989-5
[21]	Sasvari, Z. (1999) Inequalities for Binomial Coefficients. Journal of Mathematical Analysis and Applications, 236, 223-226. http://dx.doi.org/10.1006/jmaa.1999.6420
[22]	Mukhomedov, F., Pah, C.H. and Saburov, M. (2010) Single Polygon Counting for m Fixed Nodes in Cayley Tree: Two Extremal Cases. Preprint. http://arxiv.org/abs/1004.2305