DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 16(2) (1996) 181-195
DOI: 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.