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.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.