§ 1 D. Eine Anwendung der Kombinatorik. 191 
Für u n + 1 läßt sich leicht eine Rekursionsformel ableiten. Bei 
jeder möglichen Berechnung einer (n -f 1) gliedrigen Summe besteht 
der letzte Schritt notwendig in der Zusammenfassung zweier Summanden, 
von denen der erste durch Addition aus den ersten i 7 der zweite 
durch Addition aus den letzten n + 1 — i Gliedern auf irgend eine 
Weise entstanden ist, wo i einen der Werte 1, 2, 3, ... n hat. 
Da die i gliedrige Summe auf u i} die (n + 1 — i) gliedrige auf 
u n+1 _ i Arten (immer hei unveränderter Reihenfolge der Summanden) 
gebildet werden kann, so ergeben sich für einen bestimmten Wert 
von i gerade u { ■ u n+1 _ i Möglichkeiten der Summenbildung; für alle zu 
lässigen Werte von i beträgt also die Anzahl der Möglichkeiten 
U n +1 = U 1 • U n + U 2 ’ U n-1 + U 3 ' U n-2 ") 1“ U n -1 • U 2 + U n ■ U t‘ 
Offenbar ist 
% = 1, % = 1 , 
also 
u s ~ “k ti'2 = 2, 
= u x u z + w 2 m 2 + %Mj = 2 + 1 + 2 = 5 usw. 
Aus der soeben angegebenen Rekursionsformel läßt sich zwar 
unschwer eine independente Darstellung von u n herleiten. Wir hätten 
dazu aber eine Reihenentwicklung nötig, deren Kenntnis an dieser 
Stelle nicht vorausgesetzt werden kann. Wir wollen deshalb die ein 
fache Methode mitteilen, welche Rodrigues in dem schon zitierten 
Aufsatze zur direkten Bestimmung von v n gegeben hat. 
Auf welche der v n möglichen Arten man auch die Summe von 
n Gliedern bilden möge, so sind stets, wenn immer nur zwei Glieder 
zu Teilsummen zusammengefaßt werden, im ganzen (n — 1) Schritte, 
d. h. solche Zusammenfassungen zweier Glieder zu einer Teilsumme, 
erforderlich. Wenn man zur Berechnung der n gliedrigen Summe 
irgend eine bestimmte Methode gewählt hat, kann ein (n + l) tes Glied 
bei jedem der (n — 1) Schritte hinzugenommen werden, und zwar in 
vierfacher Weise, nämlich als erster oder als zweiter Summand der 
ersten Teilsumme oder als erster oder als zweiter Summand der 
zweiten Teilsumme, im ganzen also auf 4 (w — 1) Arten; endlich kann 
aber auch der (n -f l) te Summand mit der fertigen Summe der n 
ersten Summanden, und zwar auf zwei Arten, zu einer Summe ver 
einigt werden. Jeder bestimmten Art der Bildung einer n gliedrigen 
Summe entsprechen also 
4(w— l) + 2 = 4w — 2 
Möglichkeiten, eine Summe aus (n + 1) Summanden zu bilden; des 
halb ist