Hans Walser, [20150826]
TreppenflŠche mit Rechtecken optimal ausschšpfen
Auf wie viele Arten kann eine TreppenflŠche mit n Stufen optimal durch Rechtecke ausgeschšpft werden? Optimal hei§t hier, dass man mit einem Minimum an Rechtecken auskommt.
Die Abbildung 1 zeigt zwei Mšglichkeiten, wie eine TreppenflŠche mit vier Stufen durch vier Rechtecke ausgeschšpft werden kann.
Abb. 1: TreppenflŠche mit vier Stufen
Bei einer TreppenflŠche mit n Stufen ist die minimale Anzahl mindestens n. BegrŸndung: Die TreppenflŠche hat n Treppenecken. Jede Treppen-Ecke muss Ecke eines Rechtecks werden. Ein Rechteck kann aber hšchstens eine Ecke in einer Treppenecke haben.
Andererseits gibt es eine einfache Zerlegung mit n horizontalen Rechtecken (Abb. 2).
Abb. 2: Einfachste Zerlegung
Die minimale Anzahl der benštigten Rechtecke ist also gleich der Stufenzahl n. Jedes der n Rechtecke hat genau eine Ecke in einer der n Treppenecken.
Wir
bezeichnen die gesuchte Anzahl optimaler Zerlegungen mit .
Wir
denken uns nun eine Treppe mit n
Treppenecken und fixieren die Treppenecke mit der Nummer k (von unten her gezŠhlt). Die Abbildung 3 zeigt die Situation fŸr und
.
Abb. 3: †berlegungsfigur
Zu dieser fixierten Treppenecke zeichnen wir das grš§tmšgliche Rechteck (rot).
Dann
bleibt unten rechts eine TreppenflŠche mit Stufen
Ÿbrig, die sich auf
Arten
ausschšpfen lŠsst, und oben eine TreppenflŠche mit
Stufen,
die sich ihrerseits auf
Arten
ausschšpfen lŠsst. Weil wir jede Ausschšpfung unten rechts mit jeder
Ausschšpfung oben kombinieren kšnnen, gibt es
Ausschšpfungsarten mit dem gro§en roten
Rechteck. Da k von 1 bis n variieren kann, sind die beiden Zahlen
und
beide
kleiner als n.
Jetzt orgeln wir durch und erhalten die Rekursionsformel:
(1)
Nun
stellt sich noch die Frage des Startwertes. Wir setzen denn eine
TreppenflŠche mit 0 Stufen kann nur auf eine Art ausgeschšpft werden, nŠmlich
gar nicht. Es gibt viele Arten des Redens, aber nur eine Art des Schweigens.
Mit dem
Startwert und der
Rekursion (1) ergeben sich die Werte der Tabelle 1.
Die Zahlen wachsen recht rasch.
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: Anzahl optimaler Ausschšpfungen
Das geht nur auf eine Art.
Abb. 4: Eine Stufe
Es gibt zwei Mšglichkeiten.
Abb. 5: Zwei Stufen
Da gibt es fŸnf Arten.
Abb. 6: Drei Stufen
Bereits 14 Arten der Ausschšpfung.
Abb. 7: Vier Stufen
Nun haben wir 42 Arten der Ausschšpfung.
Abb. 8: FŸnf Stufen
Unsere
Zahlen sind die so genannten Catalan-Zahlen,
welche Ÿblicherweise mit bezeichnet
werden. Es gilt die Formel:
(2)