# A partition of the Catalan numbers and enumeration of genealogical trees

Discussiones Mathematicae Graph Theory (1996)

- Volume: 16, Issue: 2, page 181-195
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topRainer Schimming. "A partition of the Catalan numbers and enumeration of genealogical trees." Discussiones Mathematicae Graph Theory 16.2 (1996): 181-195. <http://eudml.org/doc/270346>.

@article{RainerSchimming1996,

abstract = {A special relational structure, called genealogical tree, is introduced; its social interpretation and geometrical realizations are discussed. The numbers $C_\{n,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 $C_\{n,k\}$ form a partition of the n-th Catalan numer Cₙ, that means $C_\{n,1\}+C_\{n,2\}+ ...+C_\{n,n\} = Cₙ$.},

author = {Rainer Schimming},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {genealogical tree; Catalan number; generating function; enumeration; code words; partition},

language = {eng},

number = {2},

pages = {181-195},

title = {A partition of the Catalan numbers and enumeration of genealogical trees},

url = {http://eudml.org/doc/270346},

volume = {16},

year = {1996},

}

TY - JOUR

AU - Rainer Schimming

TI - A partition of the Catalan numbers and enumeration of genealogical trees

JO - Discussiones Mathematicae Graph Theory

PY - 1996

VL - 16

IS - 2

SP - 181

EP - 195

AB - A special relational structure, called genealogical tree, is introduced; its social interpretation and geometrical realizations are discussed. The numbers $C_{n,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 $C_{n,k}$ form a partition of the n-th Catalan numer Cₙ, that means $C_{n,1}+C_{n,2}+ ...+C_{n,n} = Cₙ$.

LA - eng

KW - genealogical tree; Catalan number; generating function; enumeration; code words; partition

UR - http://eudml.org/doc/270346

ER -

## References

top- [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. Zbl0748.11019
- [5] P. Hilton and J. Pedersen, Catalan Numbers, Their Generalizations, and Their Uses, Math. Intelligencer 13 (1991) 64-75, doi: 10.1007/BF03024089. Zbl0767.05010
- [6] G. Polya, Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen, Acta Math. 68 (1937) 145-254, doi: 10.1007/BF02546665. Zbl63.0547.04
- [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. Zbl0737.05059

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.