Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken
Von: Triceratops
Datum: So. 30. Juli 2017 21:09:52
Thema: Mathematik


Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken

Auf wieviele verschiedene Weisen lässt sich ein <math>3 {\times} 4</math>-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 <math>3164</math> solcher Pflasterungen. Um solche Anzahlen rekursiv zu bestimmen, betrachten wir allgemeiner die Zahl der Pflasterungen eines <math>n {\times m}</math>-Gitters durch Rechtecke. In diesem Artikel schauen wir uns besonders die Fälle <math>n=1,2,3</math> an. Dabei lernen wir verschiedene Methoden kennen, insbesondere die Transfer-Matrix-Methode, die sogar für jedes feste <math>n</math> funktioniert. Wir bekommen sowohl erzeugende Funktionen als auch Rekursionsgleichungen für die gesuchten Anzahlen.

Erste Beobachtungen

Wir möchten die Anzahl der Pflasterungen eines Gitters der Höhe <math>n</math> und der Breite <math>m</math> durch Rechtecke bestimmen, deren Eckpunkte ganzzahlige Koordinaten haben. Es sei <math>P_{n,m}</math> die Zahl solcher Pflasterungen. Das ist die OEIS-Doppelfolge A116694. Es gilt offensichtlich
 
<math>(1)\quad P_{0,m} =1,\medskip\\
(2) \quad P_{n,m} =P_{m,n}.</math>
 
Wir starten nun mit dem Fall <math>n=1</math>. Es gilt
 
<math>(3)\quad P_{1,m} = \left\{\begin{array}{ll} 1 & m=0 \\ 2^{m-1} & m \geq 1.\end{array}</math>
 
Denn um ein <math>1 {\times} m</math>-Gitter, also ein Streifen der Länge <math>m</math> zu pflastern, muss an jeder der Positionen <math>1,\dotsc,m-1</math> entschieden werden, ob eine vertikale Linie gezogen wird.

<math>\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (6,1);
\draw (0,0) to (6,0) to (6,1) to (0,1) -- cycle;
\draw (2,0) to (2,1);
\draw (3,0) to (3,1);
\draw node at (0,0) [below] {\footnotesize$0$};
\draw node at (1,0) [below] {\footnotesize$1$};
\draw node at (2,0) [below] {\footnotesize$2$};
\draw node at (3,0) [below] {\footnotesize$3$};
\draw node at (4,0) [below] {\footnotesize$4$};
\draw node at (5,0) [below] {\footnotesize$5$};
\draw node at (6,0) [below] {\footnotesize$6$};
\end{tikzpicture}</math>

Irreduzible Pflasterungen

Wir können dieses Ergebnis auch über ein anderes Verfahren herleiten, das auch für <math>n=2</math> und bei anderen kombinatorischen Problemen funktioniert: Wir nennen eine Pflasterung eines <math>n {\times} m</math>-Gitters (horizontal) irreduzibel, wenn <math>m>0</math> gilt und die Pflasterung keine vertikale Trennlinie besitzt; ansonsten heißt sie reduzibel. Zum Beispiel ist bei den drei abgebildeten <math>3 {\times} 3</math>-Pflasterungen die erste reduzibel; die anderen beiden sind irreduzibel, weil sie keine vertikale Trennlinie haben.

<math>\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (3,3);
\draw (0,0) to (3,0) to (3,3) to (0,3) -- cycle;
\draw (1,0) to (1,1) to (0,1);
\draw (0,2) to (2,2) to (2,3);
\draw (2,2) to (3,2);
\draw (1,1) to (1,2);
\draw (2,0) to (2,2);
\end{tikzpicture}
\hspace{1cm}
\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (3,3);
\draw (0,0) to (3,0) to (3,3) to (0,3) -- cycle;
\draw (2,0) to (2,1) to (0,1);
\draw (1,1) to (1,3);
\draw (2,1) to (3,1);
\end{tikzpicture}
\hspace{1cm}
\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (3,3);
\draw (0,0) to (3,0) to (3,3) to (0,3) -- cycle;
\draw (0,1) to (2,1);
\draw (2,0) to (2,2);
\draw (3,2) to (1,2);
\draw (1,3) to (1,1);
\end{tikzpicture}</math>

Jede Pflasterung zerlegt sich eindeutig horizontal in eine Folge von irreduziblen Pflasterungen. Wenn also <math>I_{n,k}</math> die Zahl der irreduziblen Pflasterungen eines <math>n {\times} k</math>-Gitters bezeichnet, so gilt die Rekursionsformel
 
<math>(4)\quad\displaystyle\forall m > 0: \quad P_{n,m} = \sum_{k=1}^{m} I_{n,k} \cdot P_{n,m-k}</math>
 
mit dem Rekursionsanfang <math>P_{n,0}=1</math>. Es gilt nun offensichtlich <math>I_{1,k} = 1</math> für <math>k>0</math>, daher <math>P_{1,m} = \sum_{k=1}^{m} P_{1,m-k}</math>, und es folgt induktiv (3).

Erzeugende Funktionen

Noch praktischer ist es, mit erzeugenden Funktionen zu arbeiten. Wir betrachten die formalen Potenzreihen

<math>(5) \quad \displaystyle f_n(z) := \sum_{m=0}^{\infty} P_{n,m} \cdot z^m,\medskip\\
(6) \quad g_n(z) :=  \sum_{m=1}^{\infty} I_{n,m} \cdot z^m.</math>
 
Aus (4) folgt <math>f_n(z) = 1 + g_n(z) \cdot f_n(z)</math>, also
 
<math>(7) \quad \displaystyle f_n(z) = \frac{1}{1- g_n(z)}.</math>
 
Für <math>n=1</math> erhalten wir zum Beispiel

<math>\displaystyle g_1(z)=\sum_{m=1}^{\infty} z^m =\frac{z}{1-z},</math>

also
 
<math>\displaystyle f_1(z)=\frac{1}{1-\frac{z}{1-z}} = \frac{1-z}{1-2z} = 1+\frac{z}{1-2z} = 1 + \sum_{m=1}^{\infty} 2^{m-1} z^m.</math>
 
Damit folgt erneut (3).

Der Fall n = 2

Kommen wir nun zum Fall <math>n=2</math>. Es gibt zunächst einmal die triviale irreduzible <math>2 {\times} m</math>-Pflasterung für <math>m > 0</math>, die nur aus einem Rechteck besteht. Dann gibt es noch diejenigen irreduziblen <math>2 {\times} m</math>-Pflasterungen mit einer durchgezogenen horizontalen Trennlinie. Diese entsprechen den Paaren von disjunkten Teilmengen von <math>\{1,\dotsc,m-1\}</math>.
 
<math>\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (6,2);
\draw (0,0) to (6,0) to (6,2) to (0,2) -- cycle;
\draw (0,1) to (6,1);
\draw (2,0) to (2,1);
\draw (3,0) to (3,1);
\draw (1,1) to (1,2);
\draw [thick] (5,1) to (5,2);
\draw node at (0,0) [below] {\footnotesize$0$};
\draw node at (1,0) [below] {\footnotesize$1$};
\draw node at (2,0) [below] {\footnotesize$2$};
\draw node at (3,0) [below] {\footnotesize$3$};
\draw node at (4,0) [below] {\footnotesize$4$};
\draw node at (5,0) [below] {\footnotesize$5$};
\draw node at (6,0) [below] {\footnotesize$6$};
\draw node at (7,0.5) [right] {\footnotesize$\{2,3\}$};
\draw node at (7,1.5) [right] {\footnotesize$\{1,5\}$};
\end{tikzpicture}</math>
 
Die Paare von disjunkten Teilmengen von <math>\{1,\dotsc,m-1\}</math> stehen in Bijektion zu den Abbildungen <math>\{1,\dotsc,m-1\} \to \{0,1,2\}</math>; man betrachte nämlich die Urbildmengen von <math>\{1\}</math> und <math>\{2\}</math>. Davon gibt es <math>3^{m-1}</math> Stück. Weitere irreduzible Pflasterungen gibt es nicht. Es folgt

<math>(8) \quad \forall m > 0: \quad I_{2,m} = 1+3^{m-1}</math>

und daher

<math>\displaystyle g_2(z) = \sum_{m=1}^{\infty} (1 + 3^{m-1}) z^m = \frac{z}{1-z} + \frac{z}{1-3z} = \frac{z(1-3z)+z(1-z)}{(1-z)(1-3z)} = \frac{2z(1-2z)}{1-4z+3z^2}.</math>
 
Mit (7) folgt also
 
<math>(9) \quad\displaystyle f_2(z) = \frac{1}{1-\frac{2z(1-2z)}{1-4z+3z^2}} = \frac{1-4z+3z^2}{1-4z+3z^2-2z(1-2z)} = \frac{1-4z+3z^2}{1-6z+7z^2}.</math>
 
Daraus folgt die Rekursionsformel

<math>(10) \quad \forall m > 2: \quad P_{2,m} = 6 \cdot P_{2,m-1} - 7 \cdot P_{2,m-2},</math>
 
welche für <math>m=2</math> wohlgemerkt nicht gilt. Die drei Anfangswerte bestimmen wir besser direkt mittels (4) und (8); es ergibt sich

<math>(11) \quad P_{2,0} = 1, \quad P_{2,1} = 2, \quad P_{2,2} = 8.</math>
 
Es handelt sich hierbei um die OEIS-Folge A034999. Zum Beispiel folgt aus den Gleichungen <math>P_{2,3}=34</math>, und die zugehörigen Pflasterungen sind:
 
<math>\begin{center}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (1,0) to (1,2);
\draw (2,0) to (2,2);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (1,0) to (1,2);
\draw (2,0) to (2,2);
\draw (2,1) to (3,1);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (1,0) to (1,2);
\draw (2,0) to (2,2);
\draw (1,1) to (2,1);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (1,0) to (1,2);
\draw (1,1) to (3,1);
\draw (2,0) to (2,2);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (1,0) to (1,2);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (1,0) to (1,2);
\draw (1,1) to (3,1);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (1,0) to (1,2);
\draw (1,1) to (3,1);
\draw (2,1) to (2,2);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (1,0) to (1,2);
\draw (1,1) to (3,1);
\draw (2,1) to (2,0);
\end{tikzpicture}\bigskip\\\begin{tikzpicture}[scale=0.4,line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (0,1) to (1,1);
\draw (1,0) to (1,2);
\draw (2,0) to (2,2);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (0,1) to (1,1);
\draw (1,0) to (1,2);
\draw (2,0) to (2,2);
\draw (2,1) to (3,1);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (0,1) to (1,1);
\draw (1,0) to (1,2);
\draw (2,0) to (2,2);
\draw (1,1) to (2,1);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (0,1) to (1,1);
\draw (1,0) to (1,2);
\draw (1,1) to (3,1);
\draw (2,0) to (2,2);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (0,1) to (1,1);
\draw (1,0) to (1,2);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (0,1) to (1,1);
\draw (1,0) to (1,2);
\draw (1,1) to (3,1);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (0,1) to (1,1);
\draw (1,0) to (1,2);
\draw (1,1) to (3,1);
\draw (2,1) to (2,2);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (0,1) to (1,1);
\draw (1,0) to (1,2);
\draw (1,1) to (3,1);
\draw (2,1) to (2,0);
\end{tikzpicture}\bigskip\\\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (2,0) to (2,2);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (2,0) to (2,2);
\draw (2,1) to (3,1);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (0,1) to (2,1);
\draw (2,0) to (2,2);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (0,1) to (2,1);
\draw (2,0) to (2,2);
\draw (2,1) to (3,1);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (0,1) to (2,1);
\draw (2,0) to (2,2);
\draw (1,1) to (1,2);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (0,1) to (2,1);
\draw (2,0) to (2,2);
\draw (1,1) to (1,2);
\draw (2,1) to (3,1);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (0,1) to (2,1);
\draw (2,0) to (2,2);
\draw (1,1) to (1,0);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (0,1) to (2,1);
\draw (2,0) to (2,2);
\draw (1,1) to (1,0);
\draw (2,1) to (3,1);
\end{tikzpicture}\bigskip\\\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (0,1) to (3,1);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (0,1) to (3,1);
\draw (1,1) to (1,2);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (0,1) to (3,1);
\draw (2,1) to (2,2);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (0,1) to (3,1);
\draw (1,1) to (1,2);
\draw (2,1) to (2,2);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (0,1) to (3,1);
\draw (1,0) to (1,1);
\end{tikzpicture}\bigskip\\
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (0,1) to (3,1);
\draw (1,0) to (1,1);
\draw (2,1) to (2,2);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (0,1) to (3,1);
\draw (2,0) to (2,1);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (0,1) to (3,1);
\draw (2,0) to (2,1);
\draw (1,1) to (1,2);
\end{tikzpicture}
\hspace{1.2ex}
\begin{tikzpicture}[scale=0.4, line width=0.15ex]
\draw (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\draw (0,1) to (3,1);
\draw (1,0) to (1,1);
\draw (2,0) to (2,1);
\end{tikzpicture}
\end{center}</math>

Die Transfer-Matrix-Methode

Um die Fälle <math>n \geq 3</math> zu behandeln, beobachten wir zunächst, dass sich Pflasterungen als Wege in einem gerichteten Multigraphen verstehen lassen. Die Knoten des Graphen sind die Konfigurationen von horizontalen Strichen, wogegen die Kanten die zulässigen Konfigurationen von vertikalen Strichen sind. Zum Beispiel ist die Pflasterung (wir lassen den Außenrahmen nun weg)

<math>\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (4,3);
\draw (0,1) to (2,1);
\draw (2,0) to (2,2);
\draw (1,2) to (4,2);
\draw (1,3) to (1,1);
\draw (3,2) to (3,3);
\end{tikzpicture}</math>

der folgende Weg <math>v_1 \xrightarrow{e_{2,3}} v_{1,2} \xrightarrow{e_{1,2}} v_2 \xrightarrow{~e_3~} v_2</math>:

<math>\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (1,3);
\draw (0,1) to (1,1);
\draw node at (0.5,0) [below] {\scriptsize$v_1$};
\end{tikzpicture}
\hspace{1ex}
\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (0,3);
\draw (0,1) to (0,3);
\draw node at (0,0) [below] {\scriptsize$e_{2,3}$};
\end{tikzpicture}
\hspace{1ex}
\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (1,3);
\draw (0,1) to (1,1);
\draw (0,2) to (1,2);
\draw node at (0.5,0) [below] {\scriptsize$v_{1,2}$};
\end{tikzpicture}
\hspace{1ex}
\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (0,3);
\draw (0,0) to (0,2);
\draw node at (0,0) [below] {\scriptsize$e_{1,2}$};
\end{tikzpicture}
\hspace{1ex}
\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (1,3);
\draw (0,2) to (1,2);
\draw node at (0.5,0) [below] {\scriptsize$v_2$};
\end{tikzpicture}
\hspace{1ex}
\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (0,3);
\draw (0,2) to (0,3);
\draw node at (0,0) [below] {\scriptsize$e_3}$};
\end{tikzpicture}
\hspace{1ex}
\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (1,3);
\draw (0,2) to (1,2);
\draw node at (0.5,0) [below] {\scriptsize$v_2$};
\end{tikzpicture}</math>
 
Formal definieren wir einen gerichteten Multigraphen <math>\Gamma_n</math> wie folgt: Die Knoten <math>v_S</math> sind gegeben durch die <math>2^{n-1}</math> Teilmengen <math>S \subseteq \{1,\dotsc,n-1\}</math>, die wir uns als Konfigurationen von horizontalen Strichen vorstellen. Eine Kante <math>e_R : v_S \to v_T</math> sei gegeben durch eine Teilmenge <math>R \subseteq \{1,\dotsc,n\}</math>, die wir uns als eine Konfiguration von vertikalen Strichen vorstellen. Dabei sind nur solche erlaubt, die rechteckige Pflaster sicherstellen. Zum Beispiel ist also die Kante

<math>\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (1,3);
\draw (0,1) to (1,1);
\draw node at (0.5,0) [below] {\scriptsize$v_1$};
\end{tikzpicture}
\hspace{1ex}
\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (0,3);
\draw (0,1) to (0,2);
\draw node at (0,0) [below] {\scriptsize$e_2$};
\end{tikzpicture}
\hspace{1ex}
\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (1,3);
\draw (0,1) to (1,1);
\draw (0,2) to (1,2);
\draw node at (0.5,0) [below] {\scriptsize$v_{1,2}$};
\end{tikzpicture}</math>

nicht erlaubt, denn ansonsten hätten wir die Pflasterung

<math>\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (2,3);
\draw (0,1) to (2,1);
\draw (1,2) to (2,2);
\draw (1,1) to (1,2);
\end{tikzpicture}</math>

erzeugt. Wir beobachten: Ein Weg der Länge <math>m</math> in <math>\Gamma_n</math> (also mit <math>m</math> Kanten) ist dasselbe wie eine <math>n {\times} (m{+}1)</math>-Pflasterung.

Es gibt nun eine allgemeine Methode zur Bestimmung der (erzeugenden Funktion der) Anzahl der Wege in einem gerichteten Multigraphen, die sogenannte Transfer-Matrix-Methode. Sei dazu <math>\Gamma</math> irgendein endlicher gerichteter Multigraph mit den Knoten <math>v_1,\dotsc,v_r</math>. Die sogenannte Adjazenzmatrix <math>A \in M_r(\mathds{Z})</math> von <math>\Gamma</math> ist definiert durch

<math>(12)\quad\displaystyle A_{i,j} = \# \{\text{Kanten } v_i \to v_j \text{ in } \Gamma\}.</math>

Für die Matrixpotenz <math>A^m \in M_r(\mathds{Z})</math> gilt nun, dass <math>(A^m)_{ij}</math> die Zahl der Wege <math>v_i \to v_j</math> der Länge <math>m</math> in <math>\Gamma</math> angibt, denn es gilt

<math>(13)\quad\displaystyle (A^m)_{i,j} = \sum_{i_1,\dotsc,i_{m-1}} A_{i,i_1}  \cdots  A_{i_{m-1},j}.</math>
 
Die Zahl aller Wege der Länge <math>m</math> in <math>\Gamma</math> ist daher die Summe der Einträge von <math>A^m</math>.

Die erzeugende Funktion <math>\sum_{m=0}^{\infty} (A^m)_{i,j} z^m</math> der Wege <math>v_i \to v_j</math> ist der Eintrag <math>(i,j)</math> der Matrix

<math>(14) \quad\displaystyle \sum_{m=0}^{\infty} (zA)^m = \frac{1}{1-zA} \in M_r\bigl(\mathds{Q}(z)\bigr),</math>
 
wobei <math>\mathds{Q}(z)</math> der Körper der rationalen Funktionen in <math>z</math> ist. Diese inverse Matrix lässt sich entweder mit einem Computer oder für kleine <math>r</math> per Hand mit der Cramer'schen Regel berechnen. Um die erzeugende Funktion aller Wege der Länge <math>m</math> zu bestimmen, müssen wir noch über alle <math>i,j \in \{1,\dotsc,r\}</math> summieren.

Der Fall n = 3

Wenden wir dieses Verfahren auf <math>n=3</math> und den Graphen <math>\Gamma_3</math> an: Es gibt hier <math>4</math> Knoten, nämlich:
 
<math>\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (1,3);
\draw node at (0.5,0) [below] {\scriptsize$v_{\emptyset}$};
\end{tikzpicture}
\hspace{4ex}
\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (1,3);
\draw (0,1) to (1,1);
\draw node at (0.5,0) [below] {\scriptsize$v_1$};
\end{tikzpicture}
\hspace{4ex}
\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (1,3);
\draw (0,2) to (1,2);
\draw node at (0.5,0) [below] {\scriptsize$v_2$};
\end{tikzpicture}
\hspace{4ex}
\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (1,3);
\draw (0,1) to (1,1);
\draw (0,2) to (1,2);
\draw node at (0.5,0) [below] {\scriptsize$v_{1,2}$};
\end{tikzpicture}</math>
 
Wir legen fest, dass die Knoten in dieser Reihenfolge in der Adjazenzmatrix erscheinen. Bestimmen wir die Kanten: Der Graph ist symmetrisch, d.h. die Kanten <math>v_S \to v_T</math> entsprechen den Kanten <math>v_T \to v_S</math>. Es gibt zwei Kanten <math>v_{\emptyset} \to v_{\emptyset}</math>, nämlich <math>e_{\emptyset}</math> und <math>e_{1,2,3}</math>. Es gibt genau eine Kante <math>v_{\emptyset} \to v_{1}</math>, nämlich <math>e_{1,2,3}</math>. Analoges gilt für <math>v_{\emptyset} \to v_2</math>, und auch für <math>v_{\emptyset} \to v_{1,2}</math>. Es gibt vier Kanten <math>v_1 \to v_1</math>, nämlich <math>e_{\emptyset},e_{1},e_{2,3},e_{1,2,3}</math>.
 
<math>\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (2,3);
\draw (0,1) to (2,1);
\draw [dashed] (1,0) to (1,3);
\end{tikzpicture}</math>
 
Es gibt genau eine Kante <math>v_1 \to v_2</math>, nämlich <math>e_{1,2,3}</math>. Es gibt genau zwei Kanten <math>v_1 \to v_{1,2}</math>, nämlich <math>e_{2,3}</math> und <math>e_{1,2,3}</math>.
 
<math>\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (2,3);
\draw (0,1) to (2,1);
\draw (1,2) to (2,2);
\draw (1,1) to (1,3);
\draw [dashed] (1,0) to (1,1);
\end{tikzpicture}</math>
 
Die von <math>v_2</math> ausgehenden Kanten lassen sich analog zu <math>v_1</math> bestimmen. Und schließlich gibt es genau acht Kanten <math>v_{1,2} \to v_{1,2}</math>; hier sind alle Konfigurationen gültig.
 
<math>\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (2,3);
\draw (0,1) to (2,1);
\draw (0,2) to (2,2);
\draw [dashed] (1,0) to (1,3);
\end{tikzpicture}</math>
 
Die Adjazenzmatrix ist daher gegeben durch:

<math>\displaystyle A = \begin{pmatrix}%
2 & 1 & 1 & 1 \\
1 & 4 & 1 & 2 \\
1 & 1 & 4 & 2 \\
1 & 2 & 2 & 8
\end{pmatrix}.</math>
 
Die Berechnung von
 
<math>\displaystyle (1-zA)^{-1} = \begin{pmatrix}%
1-2z & -z & -z & -z \\
-z & 1-4z & -z & -2z \\
-z & -z & 1-4z & -2z \\
-z & -2z & -2z & 1-8z
\end{pmatrix}^{-1}</math>
 
kann man einem Computeralgebrasystem übergeben. Zum Beispiel liefert die Eingabe

Inverse(IdentityMatrix(4)-z*[[2,1,1,1],[1,4,1,2],[1,1,4,2],[1,2,2,8]])
 
bei wolframalpha:
 
<math>\displaystyle\frac{\begin{pmatrix}
1 {-} 16z {+} 71z^2 {-} 96z^3 & z {-} 9z^2 {+} 18z^3 & z {-} 9z^2 {+} 18z^3 & z {-} 4z^2 {+} 3z^3 \\
z {-} 9z^2 {+} 18z^3 & 1 {-} 14z {+} 50z^2 {-} 48z^3 & z {-} 5z^2 {+} 3z^3 & 2z {-} 9z^2 {+} 9z^3 \\
z {-} 9z^2 {+} 18z^3 & z {-} 5z^2 {+} 3z^3 & 1 {-} 14z {+} 50z^2 {-} 48z^3 & 2z {-} 9z^2 {+} 9z^3 \\
z {-} 4z^2 {+} 3z^3 & 2z {-} 9z^2 {+} 9z^3 &  2z {-} 9z^2 {+} 9z^3 & 1 {-} 10z {+} 29z^2 {-} 24z^3
\end{pmatrix}}{1 {-} 18z {+} 100z^2 {-} 216z^3 {+} 153z^4}.</math>
 
Die Summe der Einträge lautet:
 
<math>\displaystyle \frac{4-38z+110z^2-96z^3}{1 - 18z + 100z^2 - 216z^3 + 153z^4} = \frac{4-26 z+32 z^2}{1-15z+55 z^2-51 z^3}.</math>

Das ist nun die erzeugende Funktion <math>\sum_{m=0}^{\infty} P_{3,m+1} z^m</math>. Es folgt daher

<math>(15) \quad\displaystyle f_3(z) = 1 + z \frac{4-26 z+32 z^2}{1-15z+55 z^2-51 z^3} = \frac{1-11z+29 z^2-19z^3}{1-15z+55 z^2-51 z^3}.</math>
 
Es folgt insbesondere die Rekursionsgleichung

<math>(16) \quad \displaystyle \forall m > 3: \quad P_{3,m} = 15 \, P_{3,m-1} - 55 \, P_{3,m-2} + 51 \, P_{3,m-3}.</math>
 
Die vier Anfangswerte lassen sich zum Beispiel so bestimmen: Aus den vorherigen Ergebnissen folgt <math>P_{3,0}=1</math>, <math>P_{3,1} = P_{1,3} = 2^2 = 4</math> und <math>P_{3,2} = P_{2,3} = 34</math>. Es ist <math>P_{3,3}</math> die Summe der Einträge von

<math>\displaystyle A^2 = \begin{pmatrix} 7 & 9 & 9 & 14 \\ 9  & 22  & 13  & 27 \\ 9  & 13  & 22  & 27 \\ 14 & 27  & 27  & 73 \end{pmatrix},</math>
 
also <math>P_{3,3}=322</math>. Die <math>3 {\times} 3</math>-Pflasterungen kann man sich hier anschauen. Allgemein ist <math>P_{3,m}=\Sigma(A^{m-1})</math>, wenn <math>\Sigma</math> die Summe der Matrixeinträge bezeichnet. Es handelt sich um die OEIS-Folge A208215.

Der Fall n = 4

Für größere <math>n</math> funktioniert die Transfer-Matrix-Methode genauso, nur dass die Matrizen und damit auch die Rekursionsgleichungen sehr groß werden. Wir stellen kurz die Ergebnisse für <math>n=4</math> zusammen: Mit der Reihenfolge <math>v_{\emptyset},v_1,v_2,v_3,v_{1,2},v_{1,3},v_{2,3},v_{1,2,3}</math> der Kanten ist die Adjazenzmatrix gegeben durch

<math>\displaystyle A = \begin{pmatrix}
2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 4 & 1 & 1 & 2 & 2 & 1 & 2 \\
1 & 1 & 4 & 1 & 2 & 1 & 2 & 1 \\
1 & 1 & 1 & 4 & 1 & 2 & 2 & 2 \\
1 & 2 & 2 & 1 & 8 & 2 & 1 & 4 \\
1 & 2 & 1 & 2 & 2 & 8 & 2 & 4 \\
1 & 1 & 2 & 2 & 1 & 2 & 8 & 4 \\
1 & 2 & 1 & 2 & 4 & 4 & 4 & 16
\end{pmatrix}.</math>
 
Damit berechnet man

<math>(17)\quad \displaystyle f_4(z) = \frac{1-36 z+441 z^2-2468 z^3+6722 z^4-8492 z^5+3832 z^6}{1-44 z+645 z^2-4280 z^3+13840 z^4-20980 z^5+11680 z^6}.</math>
 
Die Anfangswerte von <math>P_{4,m}=\Sigma(A^{m-1})</math> für <math>m=1,\dotsc,6</math> sind gegeben durch

<math>8, 148, 3164, 70878, 1613060, 36911922.</math>
 
Für <math>m > 6</math> greift die Rekursionsformel

<math>(18)\quad P_{4,m} = & + 44 \, P_{4,m-1} - 645 \, P_{4,m-2} + 4280 \, P_{4,m-3} - 13840 \, P_{4,m-4}\\\phantom{(18)\quad P_{4,m}=} + 20980 \, P_{4,m-5} - 11680 \, P_{4,m-6}.</math>

Es handelt sich um die OEIS-Folge A220297.

Die allgemeine Adjazenzmatrix

Unter A116694 ist eine allgemeine rekursive Beschreibung bzw. ein Programmcode der Adjazenzmatrix von <math>\Gamma_n</math> angegeben. Wir geben hier eine nichtrekursive Darstellung an. Wir beschreiben dafür die Kanten <math>v_S \to v_T</math> für zwei Teilmengen <math>S,T \subseteq \{1,\dotsc,n-1\}</math> wie folgt: Ein Match zwischen <math>S</math> und <math>T</math> sei ein <math>i \in \{1,\dotsc,n-1\}</math> mit <math>i \in S \cap T</math>. Das bedeutet, dass sich bei <math>i</math> zwei horizontale Striche treffen. Wir erklären daher auch <math>0</math> und <math>n</math> zu Matches. Wenn hingegen <math>i \notin S</math> und <math>i \notin  T</math> gilt, also bei <math>i</math> gar keine horizontalen Striche eintreffen, nennen wir <math>i</math> einen Antimatch. Ein Matching-Abschnitt sei ein Intervall <math>\{i,i+1,\dotsc,i+k\} \subseteq \{0,\dotsc,n\}</math> mit <math>k>0</math>, dessen Endpunkte <math>i,i+k</math> Matches sind und dessen innere Punkte <math>i+1,\dotsc,i+k-1</math> Antimatches sind. Eine Kante <math>v_S \to v_T</math>, also eine erlaubte Konfiguration vertikaler Striche, ist nun dadurch gegeben, dass für jeden Matching-Abschnitt entschieden wird, ob er vertikal durchgezogen wird oder nicht. Die restlichen Abschnitte müssen durchgezogen werden. In den beiden Beispielen unten für <math>n=6</math> sind die Matching-Abschnitte <math>\{0,1,2\},\{5,6\}</math> bzw. <math>\{0,1\},\{1,2,3,4\}</math>.

<math>\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (2,6);
\draw (0,5) to (2,5);
\draw (0,4) to (1,4);
\draw (1,3) to (2,3);
\draw (0,2) to (2,2);
\draw [dashed] (1,5) to (1,6);
\draw [dashed] (1,0) to (1,2);
\draw (1,2)  to (1,5);
\end{tikzpicture}
\hspace{4ex}
\begin{tikzpicture}[line width=0.18ex,scale=0.8]
\draw [thin,lightgray,step=1] (0,0) grid (2,6);
\draw (0,5) to (1,5);
\draw (0,4) to (2,4);
\draw (0,1) to (2,1);
\draw [dashed] (1,0) to (1,4);
\draw (1,4) to (1,6);
\end{tikzpicture}</math>
 
Die Zahl der Kanten <math>v_S \to v_T</math> ist daher <math>2^t</math>, wenn <math>t</math> die Zahl der Matching-Abschnitte ist. Das führt zu folgendem GAP-Programm für die Adjazenzmatrix von <math>\Gamma_n</math> und damit für die gesuchte Folge <math>P_{n,m}</math>.
 
EdgeNumber := function(S,T,n)
local t,i,started;
t := 0;
started := true;
for i in [1..n] do
  if ((i in S and i in T) or i = n) then
    if started = true then t := t+1;
    else started := true;
    fi;
  elif (i in S) <> (i in T) then
    started := false;
  fi;
od;
return 2^t;
end;

AdjacencyMatrix := function(n)
local V,i,j,r;
V := Combinations([1..n-1]);
r := 2^(n-1);
return List([1..r],i->List([1..r],j->EdgeNumber(V[i],V[j],n)));
end;

P := function(n,m)
local A;
if m = 0 then return 1;
else
  A := AdjacencyMatrix(n);
  return Sum(Flat(A^(m-1)));
fi;
end;

Quellen
• OEIS: A116694, A034999, A208215, A220297
MO/229952: Number of ways of tiling a <math>2 \times n</math> rectangle using rectangles with integer sides
SE/2287784: In how many different ways can a 9-panel comic grid be used?
• R.P. Stanley, Enumerative combinatorics. Vol. I, Wadsworth and Brooks/Cole, Monterey, 1986 [insbesondere Abschnitt 4.7]
• J. Smith, H. Verrill, On dividing rectangles into rectangles [nicht aufzufinden]


Dieser Artikel kommt von Matroids Matheplanet
http://matheplanet.com

Die Url für diesen Artikel ist:
http://matheplanet.com/default3.html?article=1801