A partition of the Catalan numbers and enumeration of genealogical trees

Rainer Schimming

Discussiones Mathematicae Graph Theory (1996)

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

Abstract

top
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 ₙ .

How to cite

top

Rainer 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. [1] H. Bickel and E.H.A. Gerbracht, Lösung I zu Problem 73, Math. Semesterber. 42 (1995) 185-187. 
  2. [2] H.L. Biggs et al., Graph Theory 1736-1936 (Clarendon Press, Oxford 1976). 
  3. [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. [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. [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. [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. [7] W.W. Rouse Ball and H.S.M. Coxeter, Mathematical Recreations and Essays (12th Edition, Univ. of Toronto Press 1974). 
  8. [8] R. Schimming, Lösung II zu Problem 73, Math. Semesterber. 42 (1995) 188-189. 
  9. [9] P. Schreiber, Problem 73, Anzahl von Termen. Math. Semesterber. 41 (1994) 207. 
  10. [10] P. Schreiber, Lösung III zu Problem 73, Math. Semesterber. 42 (1995) 189-190. 
  11. [11] Wang Zhenyu, Some properties of ordered trees, Acta Math. Sinica 2 (1982) 81-83. 
  12. [12] Wang Zhenyu and Sun Chaoyi, More on additive enumeration problems over trees, Acta Math. Sinica 10 (1990) 396-401. Zbl0737.05059

NotesEmbed ?

top

You must be logged in to post comments.