Die Mathe-Redaktion - 23.11.2017 01:08 - Registrieren/Login
Auswahl
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 416 Gäste und 14 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Mathematik: Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken
Freigegeben von matroid am So. 30. Juli 2017 21:09:52
Verfasst von Triceratops -   846 x gelesen [Gliederung] [Statistik] Druckbare Version Druckerfreundliche Version
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]

Link auf diesen Artikel Link auf diesen Artikel  Druckbare Version Druckerfreundliche Version  Einen Freund auf diesen Artikel aufmerksam machen Weitersagen Kommentare zeigen Kommentare  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist nicht im Verzeichnis der Arbeitsgruppe Alexandria eingetragen.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
Verwandte Links
 
Besucherzähler 846


[Seitenanfang]

" Mathematik: Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken" | 19 Kommentare
 
Für den Inhalt der Kommentare sind die Verfasser verantwortlich.

Re: Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken
von PhysikRabe am Mo. 31. Juli 2017 09:15:04


Vielen Dank für diesen interessanten Artikel! Ich kenne mich mit Kombinatorik (leider) überhaupt nicht aus, aber dein Aufschrieb war trotzdem gut verständlich für mich. Man darf hoffen, dass "Kombinatorik in der Sommerpause" der Beginn einer ganzen Artikelreihe ist?  wink

 [Bearbeiten]

Re: Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken
von Anonymous am Mi. 02. August 2017 02:36:03


Super! Das Erinnert mich ein wenig an den Beweis des 4-Farben Problems.

 [Bearbeiten]

Re: Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken
von nosapa am Do. 03. August 2017 22:40:43


Hallo, eine interessante Aufgabe!
Mir fällt nur eine Lösung ein. Ich würde alle Summen errechnen die 12 ergibt.
Also z.B. 7+3+1+1, oder 4+3+2+1+2.
Alle offensichtliche verwerfen z.B mit 7 kann man kein Rechteck bauen. Zu bearbeiten sind nur die 4 und 3. Mit 4 oder drei rechteckige Fliesen kann ein Rechteck bauen aber auch eine ungültige Fläche 3 in einer Linie und eine Fliese im die Ecke. Diese müsste man alle Zahlen und verwerfen. Da verbirgt sich ein interessanter Algorithmus.
Viel Erfolg an den Planeten.
Gruss nosapa

 [Bearbeiten]

Re: Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken
von Triceratops am Fr. 04. August 2017 00:50:43


@PhysikRabe: Vielen Dank für das Feedback.

@nosapa: Ich gehe davon aus, dass du dich auf die <math>3 \times 4</math>-Pflasterungen beziehst. Wenn die Summanden die Flächeninhalte der Rechtecke angeben sollen, dann kommen nicht nur <math>3</math> und <math>4</math> vor, sondern: <math>1,2,3,4,6,8,9,12</math>. Aber die Flächeninhalte legen die Pflasterung gar nicht eindeutig fest. Der Ansatz ist sehr aufwändig, wenn er denn überhaupt funktioniert. Im Artikel wird eine allgemeine Lösung vorgestellt. Die Eingangsfrage sollte nur das kombinatorische Problem anhand eines Beispiels schildern. Aus Gleichung (16) und den dort berechneten Anfangswerten von <math>P_{3,m}</math> folgt <math>P_{3,4} = 15 \cdot P_{3,3} - 55 \cdot P_{3,2} + 51 \cdot P_{3,1} = 15 \cdot 322 - 55 \cdot 34 + 51 \cdot 4 = 3164</math>.

Man kann die <math>3 {\times} 4</math>-Pflasterungen hier anschauen.

 [Bearbeiten]

Re: Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken
von nosapa am Sa. 05. August 2017 12:27:46


Bei reduzible Pflasterung, definierst du die erste reduzibel, die 2. Und 3.nicht. Ich kann verstehen, das die dritte irreduzible ist warum die zweite? Stelle mir eine rechteckige Glasscheibe, die man mit einem Diamanten trennt, es gibt eine Ritze, dort trennt man die Scheibe in 2 rechteckige Scheiben.
Kannst du mir die Formel für P3,3 = 34 bitte aufschreiben. Die P3,4 ist mir zu groß, weiß nicht ob ich es verstehen werde. Man braucht viele Vorkenntnisse, das Thema ist aber interessant. Im Planeten beschäftigt man sich mit Graphen, ein ähnliches Thema.

 [Bearbeiten]

Re: Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken
von Triceratops am Sa. 05. August 2017 13:48:56


1) Ich habe nur "horizontal irreduzibel" definiert und zu "irreduzibel" abgekürzt. Es soll dabei keine vertikalen Trennlinien geben. Bei der 2. Pflasterung gibt es zwar eine horizontale Trennlinie (das hast du richtig beobachtet), aber keine vertikale Trennlinie. Sie ist also "horizontal irreduzibel", aber "vertikal reduzibel".

2) Die Bestimmung von <math>P_{3,3}=322</math> findet sich im Artikel. Man schaut sich im Prinzip an, wieviele Möglichkeiten es gibt, zwei gegebene Konfigurationen <math>v,w</math> von horizontalen Strichen ("Knoten") mit einer Konfiguration <math>e</math> von vertikalen Strichen ("Kanten") zu verbinden. Die Anzahl ist <math>2^{m(v,w)}</math>, wenn <math>m(v,w)</math> die Zahl der Matching-Abschnitte zwischen <math>v</math> und <math>w</math> ist. Bei einer <math>3 {\times} 3</math>-Pflasterung hat man zwei solche Verbindungen, sodass

<math>\displaystyle P_{3,3} = \sum_{u,v,w} 2^{m(u,v)} \cdot 2^{m(v,w)},</math>
 
wobei sich die Summe über alle <math>3</math>-Tupel von Knoten erstreckt. Es gibt insgesamt <math>4</math> Knoten, also <math>4^3=64</math> solche <math>3</math>-Tupel (wobei man sich einige wegen der Symmetrie <math>m(u,v)=m(v,u)</math> schenken kann). Ich würde diese Summe daher nicht per Hand ausrechnen, sondern einmal die Adjazenzmatrix <math>A=(2^{m(u,v)})_{u,v}</math> (per Hand) berechnen und dann die Summe der Einträge ihres Quadrates <math>A^2</math> von einem Computer berechnen lassen, denn das ist gerade die obige Summe.

Oder meintest du <math>P_{2,3}=34</math>? Was ist an dem Vorgehen im Artikel unklar?

 [Bearbeiten]

Re: Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken
von nosapa am So. 06. August 2017 07:13:29


Ja ich meine P 2,3
Ich finde deine Aufgabenstellung sehr interessant. Ich bin auf deinen Beitrag aufmerksam geworden, wie im ersten Kommentar gesagt und deine Matrix(4). Die Elemente bestehen aus Formeln. Ich arbeite auch oft mit solchen Matrixen (Determinanten) dritten und vierten Grades. Ich möchte nicht wissen wieviel Arbeit in deinem Beitrag steckt. Was ich verstanden habe, (ich bin Amateurmathematiker) möchte ich zeigen. n ist die Höhe, Vertikale und m ist die Breite, die Horizontale des Gitters. 1,1 Gitter ist der unteilbare Plasterstein ( meinetwegen aus 10cm x 10cm) . Ein 1,6 Gitter ist ein Streifen aus 6 Steine. Was  reduziebel und irreduzibel ist hast du auch präzise definiert.  Die Formel bis 3,3 Gitter würde ich gerne verstehen, was meinst du mit p und den Formeln 1 bis 3. Mit OEIS Doppelfolge kenne ich mich nicht aus. P kommt von posibilitis?
Gruß nosapa

 [Bearbeiten]

Re: Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken
von digerdiga am Mo. 07. August 2017 19:50:40


Warum ist P_{n,0)=1 ?
Ich seh da keine Pflasterung.
Und warum nennst du (4) Rekursionsformel?
Da I_{n,m} darin auftaucht kann man ja kaum von Rekursion sprechen, oder?

 [Bearbeiten]

Re: Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken
von Triceratops am Mo. 07. August 2017 20:12:59


@digerdiga: Zur ersten Frage: Das <math>n {\times} 0</math>-Gitter besitzt die leere Pflasterung (die also kein Rechteck enthält), und sonst keine Pflasterung. Dass das tatsächlich eine Pflasterung ist, "erkennt" man, und wenn nicht, muss man eine präzise Definition von Pflasterungen und Rechtecken geben, woraus sich das dann ableiten lässt. Man kann alternativ (als Notlösung) auch <math>P_{n,0}=1</math> als Konvention sehen. Beachte, dass nur damit (4) richtig wird. Es gibt auch die Variante, dass man sich im vornherein nur auf positive natürlichen Zahlen beschränkt. Dann hat (4) nicht mehr diese einfache Form. Allerdings werden dann tatsächlich die erzeugenden Funktionen einfacher, z.B. ist das Zählerpolynom dann immer einen Grad niedriger als das Nennerpolynom, und bei der Transfer-Matrix-Methode müsste man die im Artikel erklärte Verschiebung nicht mehr vornehmen.
 
Zur zweiten Frage: Das ist eine Rekursionsformel für die Folge <math>P_{n,-}</math>, sobald man die Koeffizienten <math>I_{n,-}</math> bestimmt hat. Man kann sie zum Beispiel in den Fällen <math>n=1</math> und <math>n=2</math> nutzen, wie im Artikel erklärt. Dass die Koeffizienten von <math>n</math> abhängen und erst einmal bestimmt werden müssen, ist ganz normal. Die Folge <math>I_{3,-}</math> habe ich bisher nicht bestimmt.

 [Bearbeiten]

Re: Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken
von digerdiga am Mo. 07. August 2017 21:31:39


1. Irgendwie steh ich gerade auf dem Schlauch. Welche Verschiebung meinst du genau bei der Matrix Transfer Methode? Welcher Abschnitt nach oder welche Formel?
Ist P_{n,0) in Analogie zur leeren Pflasterung einer n x m (m,n>0) Pflasterung zu sehen?

"Es gibt auch die Variante, dass man sich im vornherein nur auf positive natürlichen Zahlen beschränkt."
Ist dann die Anfangsbedingung P_{n,1}=2^{n-1} ??
Apropos: Was meinst du mit dieser Bijektion beim Fall n=2:
{1,2,3,...,m-1} -> {0,1,2}
z.B. Position 1 wird abgebildet auf 1 bedeutet Strich und auf 0 bedeutet kein Strich? Und auf 2 ??
Warum sind das genau 3^{m-1} (ohne die triviale Pflasterung?)
Es gibt die Möglichkeit n=1 zu benutzen und dann
<math>\sum_{k=0}^{m-1} \left(\begin{array}{c} m-1 \\ k \end{array}\right) 2^{m-1-k} = (2+1)^{m-1} </math>.
Ich meine aber es gibt auch ein ganz einfaches Argument dafür. Vielleicht meinst du das mit der Bijektion damit?

2. Ich meinte damit nur, dass es ja genau so schwierig ist I_{n,m} zu bestimmen wie P_{n,m} also hat man durch diese "Rekursion" ja nicht wirklich viel gewonnen? Die anderen Rekursionen weiter unten bei den Beispielen greifen wirklich nur auf die Fälle <m zurück!

3. Analog zu 1. fällt mir gerade auf, dass A^0=I ja ein nx1 Gitter dartellt. Für n=3 gab es ja 4 Knoten. Warum ist die Anzahl der Wege insgesamt 4? Eigentlich ist die Definition von A ja die Anzahl der Kanten von v_i nach v_j.
Man hätte also eine Kante von
leer -> leer
1 -> 1
2 -> 2
3 -> 3
Anschaulich ist das auch nicht, da nx1 eigentlich gar keine Kanten enthält!?!
Du wirst jetzt sagen die haben jeweils die "leere" Kante, aber wie stell ich mir das vor?
Schließlich gibt es gar keine Möglichkeit überhaupt eine Kante zu platzieren!?!

 [Bearbeiten]

Re: Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken
von Bernhard am Mo. 07. August 2017 23:08:28


Hallo Triceratops!

Wiedermal ein sehr interessantes Problem aus einer einfachen Fragestellung heraus.
Vielen Dank für den Artikel!
Mir ist auch gleich aufgefallen, daß die 2. Pflasterung nur teilweise reduzibel ist und ich habe mich dann ebenfalls gefragt, wie Du das verstanden hast. Danke für die Erklärung an Nosapa und damit auch an mich.
Das wirft bei mir allerdings die Frage auf, wieviele unterschiedliche, vollständig irreduzible Pflasterungen dann noch übrigbleiben. Und wenn man dann auch noch Spiegelungen und Drehungen herausnimmt, dürften nicht mehr viel übrigbleiben, oder?

Viele Grüße, Bernhard

 [Bearbeiten]

Re: Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken
von Triceratops am Mo. 07. August 2017 23:27:17


@digerdiga: Zu deinen Fragen:
1) Die Wege der Länge <math>m</math> in <math>\Gamma_n</math> entsprechen den <math>n {\times} (m{+}1)</math>-Pflasterungen, nicht den <math>n {\times m}</math>-Pflasterungen. Diese "Verschiebung" wird dann z.B. bei (15) benötigt.
2) Die Frage "Ist P_{n,0) in Analogie zur leeren Pflasterung einer n x m (m,n>0) Pflasterung zu sehen?" verstehe ich leider nicht.
3) Die Variante wäre entweder, <math>P_{n,m}</math> nur für <math>n,m \geq 1</math> zu definieren, und dann so wie im Artikel, oder aber <math>P_{n,m}</math> als die Zahl der <math>n {\times} (m{+}1)</math>-Pflasterungen zu definieren, also als die Zahl der Wege der Länge <math>m</math> in <math>\Gamma_n</math>. Dann würde <math>P_{1,m} = 2^m</math> für alle <math>m \geq 0</math> ohne spezielle Anfangsbedingung gelten, und die erzeugende Funktion <math>f_1</math> wäre ganz einfach <math>\frac{1}{1-2z}</math>. Aber diese Varianten stellen nur eine Spielerei dar und bringen keine inhaltliche Einsicht; ich hoffe ich habe dich damit nicht unnötig verwirrt.
4) Wenn <math>X,Y</math> endliche Mengen sind, dann gilt bekanntlich <math>\# \mathrm{Abb}(X,Y) = {\# Y}^{\# X}</math>. Das verwende ich für <math>X=\{1,\dotsc,m-1\}</math> und <math>Y=\{0,1,2\}</math>. Die Korrespondenz zwischen disjunkten Teilmengen <math>A,B \subseteq X</math> und den Abbildungen <math>f_{A,B} : X \to \{0,1,2\}</math> geht so: <math>f_{A,B}</math> ist konstant <math>1</math> auf <math>A</math>, konstant <math>2</math> auf <math>B</math>, und <math>0</math> überall sonst.
5) Deinen Satz "Es gibt die Möglichkeit n=1 zu benutzen" verstehe ich nicht, die Rechnung danach aber schon: Man schaut sich erst an, was <math>A</math> sein kann, etwa eine <math>k</math>-elementige Teilmenge von <math>X</math>, und dann muss <math>B</math> eine beliebige Teilmenge von <math>X \setminus A</math> sein. Das ist auch ein guter Beweis.
6) Für <math>n=1</math> und <math>n=2</math> ist <math>I_{n,m}</math> einfacher zu bestimmen als <math>P_{n,m}</math>, oder? Für <math>n \geq 3</math> gebe ich dir aber recht. Übrigens kann (4) auch als Rekursionsformel für <math>I_{n,-}</math> gesehen werden, sobald man <math>P_{n,-}</math> bestimmt hat, und das ist im Artikel gemacht worden. Man kann die Gleichung also als eine "gekoppelte" Rekursion sehen. Und mit (7) kann man dann die erzeugende Funktion der irreduziblen Pflasterungen ausrechnen: <math>g_n(z) = 1 - 1/f_n(z).</math>
7) Bei dem letzten Absatz steige ich leider gar nicht durch. Kannst du bitte präzise Sätze formulieren? Dann werde ich dir gerne weiterhelfen. Mit der Frage "Warum ist die Anzahl der Wege insgesamt 4?" kann ich nichts anfangen, weil ich nirgendwo behauptet habe, dass es 4 Wege gibt; es gibt unendlich viele Wege, wenn man keine Bedingungen stellt.

 [Bearbeiten]

Re: Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken
von Bernhard am Di. 08. August 2017 00:12:57


Hallo Triceratops!

Mir fällt gerade auf, daß es ja erst ab 5 Teilrechtecken eine vollständig irreduzible Pflasterung geben kann. Eine kleinere Anzahl kann man gar nicht zusammensetzen, ohne daß sie wegen durchgezogenen Schnitten quasi gleich wieder auseinander fallen. Also kann das mit den vollständig irreduziblen Pflasterungen erst ab dem Fall 2x3 losgehen.
Kannst Du mir übrigens mal erklären, warum Du Dich immer nur auf horizontal irreduzible und nicht, wie ich oben, auf vollständig irreduzible Fälle beziehst?
Weil dann so viele wegfallen würden?

Viele Grüße, Bernhard

 [Bearbeiten]

Re: Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken
von digerdiga am Di. 08. August 2017 00:56:45


1) ok
2) das nx0 Gitter hat eine Pflasterung. Per Definition?
Ich sagte dann, dass auch z.B. das Gitter 2x3 genau eine leere Pflasterung hat bei der keine Striche im Rechteck sind. Diese Pflasterung habe ich dann als genau die gleiche (bzw. äquivalente) interpretiert wie jene im nx0 Gitter.
3) ok
4) Deine Formulierung versteh ich nicht: Ich stell mir das so vor. Den dicken horizontalen Strich brauch ich, wegen der Irreduzibilität. Ich habe dann für m=2 z.b. genau die Möglichkeiten 0,1,2 also 3. Für m=3 hätte ich an der Position 1 wieder genau die 3 Möglichkeiten und an der Position 2 ebenfalls. Alle möglichen Kombinationen davon ergeben die Anzahl dieser irreduziblen Pflasterungen. D.h. 3^2. Usw für allgemeines m. Korrekt?
Wie übertrage ich das nun in deine Sprache? Also konkret der Satz:
"<math>f_{A,B}</math> ist konstant <math>1</math> auf <math>A</math>, konstant <math>2</math> auf <math>B</math>, und <math>0</math> überall sonst." soll was ausdrücken?
5) Meine Rechnung ist einfach nur zählen:
Ich habe die Möglichkeit unten keinen Strich zu machen. Dafür hab ich dann oben die Möglichkeit 2^{m-1} Pflasterungen zu realisieren.
Nun habe ich m-1=binomial(m-1,1) Möglichkeiten genau einen Strich unten zu machen. Zu jeder dieser Realisierungen habe ich 2^{m-2} Pflasterungen. Für 2 Striche unten gibt es genau binomial(m-1,2) Möglichkeiten und jede liefert 2^{m-3} Pflasterungen. Usw bis ich unten alle Striche voll habe.
Aufsummiert ergibt sich die Formel oben.
6)"Und dast ist im Artikel gemacht worden": Wo? Formel (7)?
7) Außer vielleicht Rechtschreibfehler erkenn ich aber keine Grammatikfehler in dem Satz. Zeig mir bitte einen.
Was ich sagen/fragen wollte: Der Weg der Länge m=0 hat wieviele Wege nach deiner obigen Definition über die Anzahl der Kanten? Das versuch ich mir einfach nur anschaulich vorzustellen. Es ist klar, dass es zu m=0 P_{3,1}=4 Pflasterungen gibt, entsprechend der 4 Knoten!
Und jetzt zu dem Beispiel.
Wieso ist bei z.b.
1 -> 1 nur die leere Kante erlaubt?

@Bernhard: Ist vielleicht keine Antwort für dich. Aber dennoch will ich lediglich sagen, dass für die Formel (4) und alles was in dem nächsten Abschnitt kommt, doch nur horizontale Ireduzibilität benötigt wird? Wie würdest du die "Rekursion" (4) mittels vollständig irreduziblen Pflasterungen definieren?

 [Bearbeiten]

Re: Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken
von Triceratops am Di. 08. August 2017 00:57:52


@Bernhard: Du hast Recht, dass sich die Zahl der Pflasterungen drastisch reduziert, wenn man Spiegelungen und Drehungen (um <math>180^{\circ}</math> bzw. <math>90^{\circ}</math> für <math>n=m</math>) herausteilt und sich auch nur auf vollständig irreduzible Pflasterungen beschränkt. Ich habe mir dazu noch keine näheren Gedanken gemacht, könnte aber ein Programm schreiben, was diese Zahl für gegebene <math>n,m</math> berechnet. Oder interessiert dich diese Zahl nur für <math>n=m=3</math>?
Was den Fall <math>n=2</math> betrifft, habe ich mich auf horizontal irreduzible Pflasterungen beschränkt, weil sich damit die Rekursion in <math>m</math> (nicht <math>n</math>) gut aufstellen lässt. Man baut die Pflasterungen also nur in eine (nämlich die horizontale) Richtung auf. Eine Rekursion in <math>n</math> ist für <math>n=2</math> auch nicht nötig.
Ich hatte in der ersten Version des Artikels tatsächlich explizit "horizontal irreduzibel" und "vertikal irreduzibel" definiert, dann aber festgestellt, dass ich lediglich die horizontale Variante brauche, also habe ich das Wort "horizontal" ganz weggelassen. Ich habe aber einen Änderungsvorschlag eingereicht [ist jetzt integriert], der das hoffentlich ein wenig klarer macht. Andererseits habe ich im Artikel geschrieben, dass es keine vertikale Trennlinie geben soll, sodass ich die Verwirrung um eine horizontale Trennlinie nicht ganz nachvollziehen kann.

Nachtrag: Für <math>n \geq 1</math> gibt es genau eine vollständig irreduzible <math>2 \times n</math>-Pflasterung, nämlich die mit nur einem Rechteck. Es gibt nur drei vollständig irreduzible <math>3 {\times} 3</math>-Pflasterungen:

<math>\begin{tikzpicture}[line width=0.18ex,scale=0.5]
\draw (0,0) to (3,0) to (3,3) to (0,3) -- cycle;
\end{tikzpicture}
\hspace{3ex}
\begin{tikzpicture}[line width=0.18ex,scale=0.5]
\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}
\hspace{3ex}
\begin{tikzpicture}[line width=0.18ex,scale=0.5]
\draw (0,0) to (3,0) to (3,3) to (0,3) -- cycle;
\draw (0,2) to (2,2);
\draw (2,3) to (2,1);
\draw (3,1) to (1,1);
\draw (1,0) to (1,2);
\end{tikzpicture}</math>

Dabei ist die dritte eine Spiegelung der zweiten.

Es gibt <math>31</math> vollständig irreduzible <math>3 {\times} 4</math>-Pflasterungen (von insgesamt <math>3164</math> Pflasterungen), aber nur <math>10</math> bis auf Spiegelungen:

<math>\begin{tikzpicture}[line width=0.18ex,scale=0.4]
\draw (0,0) to (4,0) to (4,3) to (0,3) -- cycle;
\end{tikzpicture}
\hspace{2ex}
\begin{tikzpicture}[line width=0.18ex,scale=0.4]
\draw (0,0) to (4,0) to (4,3) to (0,3) -- cycle;
\draw (2,0) to (2,1) to (0,1);
\draw (2,1) to (2,2) to (3,2) to (4,2);
\draw (3,2) to (3,0);
\draw (2,2) to (1,2);
\draw (1,1) to (1,3);
\end{tikzpicture}
\hspace{2ex}
\begin{tikzpicture}[line width=0.18ex,scale=0.4]
\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{2ex}
\begin{tikzpicture}[line width=0.18ex,scale=0.4]
\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 (3,2) to (3,3);
\draw (2,2) to (1,2);
\draw (1,1) to (1,3);
\end{tikzpicture}
\hspace{2ex}
\begin{tikzpicture}[line width=0.18ex,scale=0.4]
\draw (0,0) to (4,0) to (4,3) to (0,3) -- cycle;
\draw (0,1) to (3,1) to (3,0);
\draw (0,2) to (1,2) to (1,1);
\draw (1,2) to (1,3);
\draw (2,2) to (4,2);
\draw (2,1) to (2,3);
\draw (3,2) to (3,1);
\end{tikzpicture}\vspace{2ex}\\
\begin{tikzpicture}[line width=0.18ex,scale=0.4]
\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 (3,1) to (3,0);
\draw (3,1) to (3,2) to (4,2);
\draw (1,1) to (1,3);
\draw (1,2) to (3,2);
\draw (2,2) to (2,1);
\end{tikzpicture}
\hspace{2ex}
\begin{tikzpicture}[line width=0.18ex,scale=0.4]
\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 (3,1) to (3,0);
\draw (3,1) to (3,2);
\draw (1,1) to (1,3);
\draw (1,2) to (4,2);
\end{tikzpicture}
\hspace{2ex}
\begin{tikzpicture}[line width=0.18ex,scale=0.4]
\draw (0,0) to (4,0) to (4,3) to (0,3) -- cycle;
\draw (0,1) to (3,1) to (3,0);
\draw (3,1) to (3,2);
\draw (1,1) to (1,3);
\draw (1,2) to (4,2);
\end{tikzpicture}
\hspace{2ex}
\begin{tikzpicture}[line width=0.18ex,scale=0.4]
\draw (0,0) to (4,0) to (4,3) to (0,3) -- cycle;
\draw (0,1) to (3,1) to (3,0);
\draw (3,1) to (3,2);
\draw (1,1) to (1,3);
\draw (1,2) to (4,2);
\draw (2,1) to (2,2);
\end{tikzpicture}
\hspace{2ex}
\begin{tikzpicture}[line width=0.18ex,scale=0.4]
\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 (3,1) to (3,0);
\draw (3,1) to (3,2);
\draw (1,1) to (1,3);
\draw (1,2) to (4,2);
\draw (2,2) to (2,3);
\end{tikzpicture}</math>

 [Bearbeiten]

Re: Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken
von Triceratops am Di. 08. August 2017 10:02:39


@digerdiga:
2) Das <math>2 {\times} 3</math>-Gitter hat keine leere Pflasterung. Du meinst die Pflasterung, die aus genau einem Rechteck besteht (welches das gesamte Gitter ausfüllt). Eine Pflasterung heißt leer, wenn sie gar kein Rechteck beinhaltet. Das ist nur bei <math>n=0</math> oder <math>m=0</math> möglich. Wenn wir definieren, dass bei einer Pflasterung die Rechtecke lediglich das Innere des Gitters ausfüllen sollen (und bis auf die Ränder disjunkt sind), dann hat das <math>n {\times} 0</math>-Gitter eine leere Pflasterung, weil sein Inneres leer ist. Für <math>n,m>0</math> hingegen ist das Innere nichtleer und daher gibt es hier keine leere Pflasterung.
4) + 5): Unsere Beweise sind mehr oder weniger identisch. Die Abbildung <math>f_{A,B}</math> kodiert die vertikale Strichverteilung. Hierbei steht <math>A</math> für die Striche in der ersten Zeile, <math>B</math> für diejenigen in der zweiten Zeile. Es gilt also <math>f_{A,B}(a)=1</math> für <math>a \in A</math>, <math>f_{A,B}(b)=2</math> für <math>b \in B</math>, und <math>f_{A,B}(c)=0</math> für alle anderen <math>c</math>. Ich habe hier lediglich die Kodierung durch Abbildungen vorgenommen, weil ich die Formel für die Anzahl der Abbildungen als wohlbekannt angenommen habe und es recht effizient ist, sie zu nutzen.
6) Ich wollte nur sagen: Im Artikel ist <math>P_{n,m}</math> bestimmt worden. Mit (4), oder auch (7), kann man dann <math>I_{n,m}</math> bestimmen (was im Artikel für <math>n \geq 3</math> nicht explizit gemacht worden ist).
7) Es ist verwirrend, wenn du <math>m=0</math> schreibst, wenn du eigentlich den Fall <math>m=1</math> meinst (weil du ja z.B. <math>P_{3,1}=4</math> schreibst). Der Fall <math>m=1</math> bedeutet, dass man sich Wege der Länge <math>0</math> in <math>\Gamma_n</math> anschaut. Ein Weg der Länge <math>0</math> in einem Graphen ist per Definition dasselbe wie ein Knoten (und ein Weg der Länge <math>1</math> in einem Graphen ist dasselbe wie eine Kante). Was meinst du mit Kanten <math>1 \to 1</math>? Es gibt im Artikel keinen Knoten, der mit <math>1</math> bezeichnet worden ist. Jedenfalls kannst du <math>v_1</math> nicht meinen, denn es gibt vier Kanten <math>v_1 \to v_1</math>. Oder verwechselt du gerade Wege der Länge <math>0</math> mit Wegen der Länge <math>1</math>?

 [Bearbeiten]

Re: Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken
von digerdiga am Di. 08. August 2017 12:41:59


2) In dem Fall n=2 gibt (gab es oben) es doch genau eine triviale Pflasterung, die nur aus dem Rechteck besteht. (Das Gitter ist gar nicht ausgefüllt mmn, oder was meinst du damit zu sagen: "das gesamte Gitter ausfüllt"). Wenn du so willst wollte ich diese triviale Pflasterung in Korrespondenz setzen zu der einen Pflasterung die es im Fall m=0 bzw. n=0 gibt. Der Begriff "leere" Pflasterung so wie du ihn verwendest find ich irgendwie komisch. Schließlich ist auch ein 2x3 Gitter "leer" wenn ich keine Striche darin unterbringe. Warum sollte ich dann hier (in deiner Termini: triviale Pflasterung) nicht von leerer Pflasterung sprechen können?!? Nach deiner Definition, bei der "bei einer Pflasterung die Rechtecke lediglich das Innere des Gitters ausfüllen sollen" ist das doch genau im Falle 2x3 nicht der Fall, weil nunmal hier keine Striche im Inneren sind. Das verwirrt mich...
7) Ich meinte den Weg der Länge m=0. In Sprache der Pflasterung ist das dann eine nx1 Pflasterung, ja.
1 -> 1 steht für v_1 -> v_1 als Beispiel um dann zu schauen wieviele Kanten sind in diesem Fall legitim. Dies soll also nur eine legitime Kante sein? Schließlich steht in der Matrix nur jeweils eine 1 auf der Diagonalen.
Wenn ich so drüber nachdenke, dann ist das vielleicht doch einsichtig, weil es gibt ja bei Wegen der Länge 0 nur genau jene 2^{n-1} die es auch Knoten gibt.
Wenn ich aber versuche deine Definition zu benutzen:
<math>(12)\quad\displaystyle A_{i,j} = \# \{\text{Kanten } v_i \to v_j \text{ in } \Gamma\}.</math>
Dann klappt das mit hoch m>0 nehmen für Wege der Länge m wunderbar. Ich fand es nur zunächst verwunderlich, dass der Fall m=0 auch darin enthalten ist. Denn nach dieser Definition müsste ich auch bei m=0 schauen wo könnte ich legitime Kanten e_S hinzufügen. Das geht aber anschaulich im Falle m=0 nicht.

 [Bearbeiten]

Re: Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken
von Triceratops am Di. 08. August 2017 13:28:04


@digerdiga:
2) Vielleicht helfen dir Farben. Das Gitter ist zunächst weiß. Jedes Rechteck, inklusive seinem Inneren, bekommt eine individuelle Farbe. Eine Pflasterung ist nur dann vollständig, wenn alles bunt ist. Bei der Pflasterung mit nur einem Rechteck ist das gesamte Gitter ebenfalls bunt.

<math>\begin{tikzpicture}[scale=0.5]
\draw [fill=green!40] (0,0) to (2,0) to (2,1) to (0,1) -- cycle;
\draw [fill=red!40] (2,0) to (3,0) to (3,2) to (2,2) -- cycle;
\draw [fill=blue!40] (2,1) to (2,2) to (0,2) to (0,1) -- cycle;
\end{tikzpicture}
\hspace{3ex}
\begin{tikzpicture}[scale=0.5]
\draw [fill=green!40] (0,0) to (3,0) to (3,2) to (0,2) -- cycle;
\end{tikzpicture}</math>

Diese Pflasterung ist also definitiv nicht leer. Die Leerheit wird nicht daran bemessen, ob Striche gezeichnet werden, sondern ob es rechteckige Flächen gibt. Was den Fall der leeren Pflasterung im Fall <math>n=0</math> oder <math>m=0</math> angeht, habe ich bereits alles gesagt, was ich dazu sagen könnte, ohne in mengentheoretische Formalismen zu verfallen. Schau dir ggf. noch einmal die Definition der leeren Menge an. Ich werde dazu nichts mehr schreiben, und vielleicht können es andere besser als ich erklären.

7) Wenn du dir Kanten <math>v_1 \to v_1</math> anschaust, sind das wie gesagt Wege der Länge <math>1</math> (die also den <math>n {\times} 2</math>-Pflasterungen entsprechen), und nicht Wege der Länge <math>0</math>. Es gibt wie gesagt genau <math>4</math> Kanten <math>v_1 \to v_1</math> (man muss sich entscheiden, ob oben und/oder unten vertikale Striche entstehen). In der Adjazenzmatrix steht keine <math>1</math> auf der Diagonalen. Es gibt aber nur einen Weg der Länge <math>0</math> von <math>v_1</math> nach <math>v_1</math>. Wie du korrekt erkannt hast, passt das gut mit dem Potenzieren der Adjazenzmatrix zusammen. Man kann das entweder als Konvention ansehen, nämlich als den Anfang der rekursiven Definition von Wegen der Länge <math>m</math> für <math>m \geq 0</math>. Oder man definiert Wege der Länge <math>m</math> in einem Graphen <math>\Gamma</math> direkt (also ohne Rekursion) als Morphismen von Graphen <math>f : \mathrm{Path}_m \to \Gamma</math>, wobei <math>\mathrm{Path}_n</math> der Graph mit der Knotenmenge <math>\{i \in \mathds{N} : i \leq m\}</math> und den Kanten <math>i \to i+1</math> für <math>0 \leq i < m</math> ist; Anfangs- und Endknoten sind dann <math>f(0)</math> und <math>f(m)</math>.

<math>\begin{tikzcd}[nodes={inner sep=2pt}]
0 \ar{r} & 1 \ar{r} & \cdots \ar{r} & m
\end{tikzcd}</math>

Für <math>m=0</math> hat <math>\mathrm{Path}_0</math> genau einen Knoten und keine Kante. Ein Weg der Länge <math>0</math> in <math>\Gamma</math> ist also dasselbe wie ein Knoten in <math>\Gamma</math>, welcher nämlich Anfangs- und Endknoten zugleich ist. Dass die Zahl der Wege der Länge <math>m</math> von <math>v_i</math> nach <math>v_j</math> gleich <math>(A^m)_{ij}</math> ist, gilt dann für alle <math>m \geq 0</math> und kann sogar – mit obiger Definition – ohne Fallunterscheidung mittels Gleichung (13) bewiesen werden.

Die ganze Diskussion ist ein Beispiel für MO/45951.

 [Bearbeiten]

Re: Kombinatorik in der Sommerpause: Pflasterungen mit Rechtecken
von digerdiga am Di. 08. August 2017 15:28:37


Für einen Weg der länge m, soll dann {0,1,2,....,m} was darstellen?
Path_m ist dann einfach die Knotenmenge ohne die Kanten?
Und f(k)= ? soll was explizit z.b. darstellen: i -> i+1 ?
Wofür steht i hier? Für die Position an der ich eine Kante einfüge?
Hast du vielleicht ein konkretes Beispiel ?

 [Bearbeiten]

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]