MP Startseite (Matroids Matheplanet)

Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken

Auf wieviele verschiedene Weisen lässt sich ein $3 {\times} 4$-Gitter mit Rechtecken pflastern? Hier ein paar Beispiele dafür:

$<math>\begin{tikzpicture}[line width=0.18ex,scale=0.5] \draw [thin,lightgray,step=1] (0,0) grid (4,3); \draw (0,0) to (4,0) to (4,3) to (0,3) -- cycle; \draw (0,1) to (2,1) to (2,0); \draw (2,1) to (2,2) to (4,2); \draw (2,2) to (1,2); \draw (1,1) to (1,3); \end{tikzpicture} \hspace{7mm} \begin{tikzpicture}[line width=0.18ex,scale=0.5] \draw [thin,lightgray,step=1] (0,0) grid (4,3); \draw (0,0) to (4,0) to (4,3) to (0,3) -- cycle; \draw (0,1) to (4,1); \draw (3,0) to (3,1); \draw (2,1) to (2,2) to (4,2); \draw (2,3) to (2,2); \draw (1,1) to (1,3); \end{tikzpicture} \hspace{7mm} \begin{tikzpicture}[line width=0.18ex,scale=0.5] \draw [thin,lightgray,step=1] (0,0) grid (4,3); \draw (0,0) to (4,0) to (4,3) to (0,3) -- cycle; \draw (2,0) to (2,2) to (0,2); \draw (2,2) to (2,3); \draw (2,1) to (3,1); \draw (3,2) to (4,2); \draw (3,0) to (3,3); \end{tikzpicture} \hspace{7mm} \begin{tikzpicture}[line width=0.18ex,scale=0.5] \draw [thin,lightgray,step=1] (0,0) grid (4,3); \draw (0,0) to (4,0) to (4,3) to (0,3) -- cycle; \draw (1,0) to (1,1) to (0,1); \draw (0,2) to (3,2) to (3,1) to (1,1); \draw (2,2) to (2,3); \draw (3,2) to (3,3); \draw (3,1) to (4,1); \end{tikzpicture}</math>$
Tatsächlich gibt es $3164$ solcher Pflasterungen. Um solche Anzahlen rekursiv zu bestimmen, betrachten wir allgemeiner die Zahl der Pflasterungen eines $n {\times m}$-Gitters durch Rechtecke. In diesem Artikel schauen wir uns besonders die Fälle $n=1,2,3$ an. Dabei lernen wir verschiedene Methoden kennen, insbesondere die Transfer-Matrix-Methode, die sogar für jedes feste $n$ funktioniert. Wir bekommen sowohl erzeugende Funktionen als auch Rekursionsgleichungen für die gesuchten Anzahlen.

Vollständige Indoktrination

Die vollständige Induktion steht im ersten Semester auf dem Lehrplan und wird mit vielen einfachen Aufgaben eingeübt. Das hat oftmals zur Folge, dass Studienanfänger alles, wo eine natürliche Zahl vorkommt, mittels vollständiger Induktion beweisen möchten, oder sogar beweisen sollen.

Was diese Einschränkung für Auswirkungen auf die mathematische Kreativität hat, und dass andere Beweismethoden oftmals viel erhellender und eleganter sind, darum wird es in diesem Artikel gehen. Dazu werden viele Beispiele herangezogen. Es werden auch genügend Beispiele dafür besprochen, wo eine vollständige Induktion sinnvoll oder sogar notwendig ist.

Dieser Artikel richtet sich v.a. an fortgeschrittene Schüler und Studienanfänger.

Grenzwertbetrachtungen mit der Zahl e

Heutiges Ziel

Was ist eine erzeugende Funktion?

Über das Biegen von Papier und Textilien

Wie man einfache Beweise ohne Mühe finden kann

Kombinatorik im Spätsommer: Hamiltonsche Gitterwege

Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken

Eine Methode zur Berechnung von Galoisgruppen

Überschallmusik

Vollständige Indoktrination