PDF
Discussiones Mathematicae Graph Theory 16(2) (1996)
181-195
DOI: https://doi.org/10.7151/dmgt.1033
A PARTITION OF THE CATALAN NUMBERS AND ENUMERATION OF GENEALOGICAL TREES
Rainer Schimming
Institut für Mathematik und Informatik
Ernst-Moritz-Arndt-Universität
D-17487 Greifswald, Germany
Abstract
A special relational structure, called genealogical tree, is introduced; its social interpretation and geometrical realizations are discussed. The numbers Cn,k of all abstract genealogical trees with exactly n+1 nodes and k leaves is found by means of enumeration of code words. For each n, the Cn,k form a partition of the n-th Catalan numer Cn, that means Cn,1+Cn,2+ …+Cn,n = Cn.
Keywords: genealogical tree, Catalan number, generating function.
1991 Mathematics Subject Classification: 05C30, 05A15.
References
| [1] | H. Bickel and E.H.A. Gerbracht, Lösung I zu Problem 73, Math. Semesterber. 42 (1995) 185-187. |
| [2] | H.L. Biggs et al., Graph Theory 1736-1936 (Clarendon Press, Oxford 1976). |
| [3] | A. Cayley, On the theory of the analytical forms called trees I, II, Phil. Mag. 13 (1857) 172-176; 18 (1859) 374-378. |
| [4] | R.B. Eggleton and R.K. Guy, Catalan Strikes Again! How Likely Is a Function to Be Convex?, Math. Magazine 61 (1988) 211-219, doi: 10.2307/2689355. |
| [5] | P. Hilton and J. Pedersen, Catalan Numbers, Their Generalizations, and Their Uses, Math. Intelligencer 13 (1991) 64-75, doi: 10.1007/BF03024089. |
| [6] | G. Polya, Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen, Acta Math. 68 (1937) 145-254, doi: 10.1007/BF02546665. |
| [7] | W.W. Rouse Ball and H.S.M. Coxeter, Mathematical Recreations and Essays (12th Edition, Univ. of Toronto Press 1974). |
| [8] | R. Schimming, Lösung II zu Problem 73, Math. Semesterber. 42 (1995) 188-189. |
| [9] | P. Schreiber, Problem 73, Anzahl von Termen. Math. Semesterber. 41 (1994) 207. |
| [10] | P. Schreiber, Lösung III zu Problem 73, Math. Semesterber. 42 (1995) 189-190. |
| [11] | Wang Zhenyu, Some properties of ordered trees, Acta Math. Sinica 2 (1982) 81-83. |
| [12] | Wang Zhenyu and Sun Chaoyi, More on additive enumeration problems over trees, Acta Math. Sinica 10 (1990) 396-401. |
Close