1 Frage

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

2 Optimale Anzahl der benötigten Rechtecke

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.

3 Rekursives Vorgehen

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.