A partition of the Catalan numbers and enumeration of genealogical trees
Rainer Schimming
Discussiones Mathematicae Graph Theory, Tome 16 (1996), p. 181-195 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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 Cₙ, that means Cn,1+Cn,2+...+Cn,n=Cₙ.

Publié le : 1996-01-01
EUDML-ID : urn:eudml:doc:270346 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1033,
     author = {Rainer Schimming},
     title = {A partition of the Catalan numbers and enumeration of genealogical trees},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {16},
     year = {1996},
     pages = {181-195},
     zbl = {0877.05025},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1033}
}

Rainer Schimming. A partition of the Catalan numbers and enumeration of genealogical trees. Discussiones Mathematicae Graph Theory, Tome 16 (1996) pp. 181-195. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1033/

[000] [1] H. Bickel and E.H.A. Gerbracht, Lösung I zu Problem 73, Math. Semesterber. 42 (1995) 185-187.

[001] [2] H.L. Biggs et al., Graph Theory 1736-1936 (Clarendon Press, Oxford 1976).

[002] [3] A. Cayley, On the theory of the analytical forms called trees I, II, Phil. Mag. 13 (1857) 172-176; 18 (1859) 374-378.

[003] [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. | Zbl 0748.11019

[004] [5] P. Hilton and J. Pedersen, Catalan Numbers, Their Generalizations, and Their Uses, Math. Intelligencer 13 (1991) 64-75, doi: 10.1007/BF03024089. | Zbl 0767.05010

[005] [6] G. Polya, Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen, Acta Math. 68 (1937) 145-254, doi: 10.1007/BF02546665. | Zbl 63.0547.04

[006] [7] W.W. Rouse Ball and H.S.M. Coxeter, Mathematical Recreations and Essays (12th Edition, Univ. of Toronto Press 1974).

[007] [8] R. Schimming, Lösung II zu Problem 73, Math. Semesterber. 42 (1995) 188-189.

[008] [9] P. Schreiber, Problem 73, Anzahl von Termen. Math. Semesterber. 41 (1994) 207.

[009] [10] P. Schreiber, Lösung III zu Problem 73, Math. Semesterber. 42 (1995) 189-190.

[010] [11] Wang Zhenyu, Some properties of ordered trees, Acta Math. Sinica 2 (1982) 81-83.

[011] [12] Wang Zhenyu and Sun Chaoyi, More on additive enumeration problems over trees, Acta Math. Sinica 10 (1990) 396-401. | Zbl 0737.05059