Hans Walser, [20150829]
Catalan-Zahlen
Es sollen n Elemente auf n linear angeordnete Felder verteilt werden wie folgt. Das erste Element hat freie Platzwahl. Das zweite Element hat freie Platzwahl im ersten noch freien Intervall. Das dritte und die weiteren Elemente nacheinander freie Platzwahl im jeweils ersten freien Intervall.
Bemerkung: Ohne die EinschrŠnkung auf das erste freie Intervall ergŠben sich die n! Permutationen.
Wir codieren die Reihenfolge gemŠ§ Abbildung 1.
Abb. 1: Reihenfolge
Gibt nur eine Mšglichkeit.
Nun gibt es fŸr das erste Element zwei Mšglichkeiten. Das zweite Element hat keine Wahl mehr.
Abb. 2: Zwei Elemente
In Zahlen: [1,2] und [2,1].
Wir haben fŸnf Mšglichkeiten.
Abb. 3: Drei Elemente
In Zahlen: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,2,1]. Hier unterscheiden sich die Anordnungsmšglichkeiten von den Permutationen. Bei den Permutationen hŠtten wir noch zusŠtzlich [3,1,2]. Das ist in unserem Fall ausgeschlossen, weil die 2 im Intervall vor der 1 stehen muss.
Es gibt 14 Mšglichkeiten.
Abb. 4: Vier Elemente
Es ist 14 < 4! = 24.
Es gibt 42 Mšglichkeiten.
Abb. 5: FŸnf Elemente
Wir
bezeichnen mit die Anzahl
der Anordnungen von n Elementen gemŠ§
unseren Restriktionen.
Wir
setzen , da man nur auf eine Art gar nichts tun kann.
Nun
nehmen wir an, das erste Element setze sich auf die Position k. Dann mŸssen die nachfolgenden Elemente
zwingend auf die
PlŠtze vor
dem ersten Element kommen. Dazu gibt es
Mšglichkeiten. Die restlichen
Elemente
kommen auf die
Positionen
hinter dem ersten Element. Dazu gibt es
Mšglichkeiten. Wenn das erste Element
also die Position k wŠhlt, gibt es
insgesamt
Mšglichkeiten.
Somit ergibt sich die Rekursion:
(1)
Zusammen mit dem Startwert erhalten wir:
n |
|
|
|
n |
|
0 |
1 |
|
|
|
|
1 |
1 |
|
|
11 |
58786 |
2 |
2 |
|
|
12 |
208012 |
3 |
5 |
|
|
13 |
742900 |
4 |
14 |
|
|
14 |
2674440 |
5 |
42 |
|
|
15 |
9694845 |
6 |
132 |
|
|
16 |
35357670 |
7 |
429 |
|
|
17 |
129644790 |
8 |
1430 |
|
|
18 |
477638700 |
9 |
4862 |
|
|
19 |
1767263190 |
10 |
16796 |
|
|
20 |
6564120420 |
Tab. 1: Catalan-Zahlen
Diese Zahlen sind die Catalan-Zahlen, benannt nach Eugne Charles Catalan (1814-1894). Die Catalan-Zahlen lassen sich auch berechnen mit:
(2)