Die Mathe-Redaktion - 24.09.2017 08:41 - 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 Apr. 2017

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

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Mathematik: Kombinatorik im Spätsommer: Hamiltonsche Gitterwege
Freigegeben von matroid am Do. 24. August 2017 08:26:14
Verfasst von Triceratops -   307 x gelesen [Gliederung] [Statistik] Druckbare Version Druckerfreundliche Version
Mathematik

Kombinatorik im Spätsommer: Hamiltonsche Gitterwege


In diesem Artikel zählen wir die Wege, die durch ein endliches Gitter von unten links nach oben rechts laufen und sich nicht selbst schneiden. Dabei betrachten wir auch die Option, dass jeder Gitterpunkt genau einmal besucht wird. Solche Gitterwege werden selbstmeidend bzw. Hamiltonsch genannt.
 
<math>\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw [lightgray] (0,0) grid (7,6);
\draw [rounded corners=0.3ex,black!50!blue] (0,0) to (3,0) to (3,3) to (1,3) to (1,2) to (2,2) to (2,1) to (0,1) to (0,4) to (2,4) to (2,5) to (0,5) to (0,6) to (5,6) to (5,5) to (3,5) to (3,4) to (4,4) to (4,2) to (6,2) to (6,1) to (4,1) to (4,0) to (7,0) to (7,3) to (5,3) to (5,4) to (7,4) to (7,5) to (6,5) to (6,6) to (7,6);
\end{tikzpicture}
\hspace{10ex}
\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw [lightgray] (0,0) grid (7,6);
\draw [rounded corners=0.3ex,black!50!blue] (0,0) to (0,4) to (4,4) to (4,3) to (3,3) to (3,2) to (2,2) to (2,3) to (1,3) to (1,0) to (2,0) to (2,1) to (3,1) to (3,0) to (4,0) to (4,2) to (5,2) to (5,5) to (0,5) to (0,6) to (6,6) to (6,1) to (5,1) to (5,0) to (7,0) to (7,6);
\end{tikzpicture}</math>
 
Wir benutzen die Transfer-Matrix-Methode, um die erzeugenden Funktionen der gesuchten Anzahlen effizient zu bestimmen. Ein Programm nimmt uns die Rechnungen ab.


Gitterwege

Seien <math>m,n</math> zwei natürliche Zahlen. Für uns ist ein <math>m {\times} n</math>-Gitterweg ein Weg, der von <math>(0,0)</math> nach <math>(m,n)</math> durch das Gitter <math>\{(x,y) \in \mathds{N} : x \leq m,\, y \leq n\}</math> der Breite <math>m</math> und der Höhe <math>n</math> verläuft, wobei die Kanten von der Form <math>(x,y) \to (x,y \pm 1)</math> und <math>(x,y) \to (x \pm 1,y)</math> sind. Es sind also alle vier Richtungen erlaubt.

Wir nennen einen Gitterweg selbstmeidend, wenn jeder Punkt des Gitters höchstens einmal besucht wird, und wir nennen ihn Hamiltonsch, wenn jeder Punkt des Gitters genau einmal besucht wird. Bei den folgenden Beispielen von <math>3{\times}4</math>-Gitterwegen ist der erste nicht selbstmeidend, der zweite selbstmeidend (aber nicht Hamiltonsch), und der dritte Hamiltonsch (und damit insbesondere selbstmeidend).

<math>\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw [lightgray] (0,0) grid (3,4);
\draw [rounded corners=0.3ex,black!50!blue] (0,0) to (2,0) to (2,3) to (1,3);
\fill [white] (2,2) circle [radius=1ex];
\draw [rounded corners=0.3ex,black!50!blue] (2,3) to (1,3) to (1,4) to (0,4) to (0,1) to (1,1) to (1,2) to (3,2) to (3,4);
\end{tikzpicture}
\hspace{5ex}
\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw [lightgray] (0,0) grid (3,4);
\draw [rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (1,1) to (2,1) to (2,0) to (3,0) to (3,2) to (1,2) to (1,3) to (0,3) to (0,4) to (3,4);
\end{tikzpicture}
\hspace{5ex}
\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw [lightgray] (0,0) grid (3,4);
\draw [rounded corners=0.3ex,black!50!blue] (0,0) to (3,0) to (3,2) to (2,2) to (2,1) to (0,1) to (0,2) to (1,2) to (1,3) to (0,3) to (0,4) to (2,4) to (2,3) to (3,3) to (3,4);
\end{tikzpicture}
</math>
 
Man könnte auch andere Anfangs- und Endpunkte betrachten, oder sogar Anfangs- und Endpunkt zu einem Punkt reduzieren, also Kreiswege betrachten. Wir wollen uns hier aber auf den Startpunkt <math>(0,0)</math> und den Endpunkt <math>(m,n)</math> beschränken. Es gibt abzählbar unendlich viele Gitterwege, aber nur endlich viele selbstmeidende Gitterwege, sodass die Frage nach ihrer genauen Anzahl sinnvoll ist.
 
Man kann sich mit einem typischen Schachbrettargument überlegen, dass es keinen Hamiltonschen Gitterweg gibt, wenn <math>m</math> und <math>n</math> ungerade sind: Färbt man die Gitterpunkte (nicht die Felder) abwechselnd ein, so müsste ein Hamiltonscher Gitterweg <math>(m+1)(n+1)-1</math> mal die Farbe wechseln, was ungerade ist, sodass er von <math>(0,0)</math> beginnend nicht bei <math>(m,n)</math> landen kann, weil diese Punkte dieselbe Farbe haben.
 
<math>\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw [lightgray] (0,0) grid (3,3);
\draw [rounded corners=0.3ex,black!50!blue] (0,0) to (3,0) to (3,2) to (2,2) to (2,1) to (0,1) to (0,3) to (3,3);
\fill [blue!80!black] (0,0) circle [radius=1ex];
\fill [blue!80!black] (2,0) circle [radius=1ex];
\fill [blue!80!black] (2,2) circle [radius=1ex];
\fill [blue!80!black] (0,2) circle [radius=1ex];
\fill [blue!80!black] (1,1) circle [radius=1ex];
\fill [blue!80!black] (3,1) circle [radius=1ex];
\fill [blue!80!black] (3,3) circle [radius=1ex];
\fill [blue!80!black] (1,3) circle [radius=1ex];
\fill [magenta] (1,0) circle [radius=1ex];
\fill [magenta] (3,0) circle [radius=1ex];
\fill [magenta] (3,2) circle [radius=1ex];
\fill [magenta] (1,2) circle [radius=1ex];
\fill [magenta] (2,1) circle [radius=1ex];
\fill [magenta] (0,1) circle [radius=1ex];
\fill [magenta] (0,3) circle [radius=1ex];
\fill [magenta] (2,3) circle [radius=1ex];
\end{tikzpicture}</math>

Die Umkehrung gilt auch, d.h., wenn <math>m</math> oder analog <math>n</math> gerade ist, dann gibt es einen Hamiltonschen Gitterweg, z.B. eine "Schlange".
 
<math>\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw [lightgray] (0,0) grid (4,3);
\draw [rounded corners=0.3ex,black!50!blue] (0,0) to (0,3) to (1,3) to (1,0) to (2,0) to (2,3) to (3,3) to (3,0) to (4,0) to (4,3);
\end{tikzpicture}</math>

Einen selbstmeidenden Gitterweg gibt es hingegen immer. In der englischen Literatur sind selbstmeidende Gitterwege als self-avoiding walks bzw. SAWs, und ebenfalls als rook paths bekannt (engl. rook = Turm im Schach). Diese wurden vor allem unter stochastischen, algorithmischen und asymptotischen Gesichtspunkten untersucht. Mit ihnen lassen sich außerdem Polymere modellieren. Wir untersuchen Gitterwege hier lediglich von einem kombinatorischen Standpunkt aus.
 

Die Transfer-Matrix-Methode

Wie bereits im vorigen Artikel zur Kombinatorik verwenden wir die Transfer-Matrix-Methode, die wir kurz zusammenfassen. Der Unterschied ist, dass wir keine Multigraphen benötigen.
 
Sei <math>\Gamma</math> ein endlicher gerichteter Graph mit den Knoten <math>v_1,\dotsc,v_r</math>. Seine Adjazenzmatrix <math>A \in M_r(\mathds{Z})</math> ist eine <math>\{0,1\}</math>-Matrix definiert durch
 
<math>A_{ij} = \left\{\begin{array}{ll} 1 & \text{es gibt eine Kante } v_i \to v_j, \\ 0 & \text{sonst.}\end{array}\right.</math>
 
Für die Matrixpotenzen <math>A^m</math> mit <math>m \in \mathds{N}</math> gilt: Es ist <math>(A^m)_{ij}</math> die Zahl <math>p_{ij}(m)</math> der Wege von <math>v_i</math> nach <math>v_j</math> der Länge <math>m</math> in <math>\Gamma</math>. Für die erzeugende Funktion gilt daher
 
<math>(1) \quad\displaystyle \sum_{m=0}^{\infty} p_{ij}(m) \cdot z^m = \biggl(\sum_{m=0}^{\infty} A^m \cdot z^m\biggr)_{i,j} =  \bigl((1-zA)^{-1}\bigr)_{i,j} = (-1)^{i+j} \, \frac{\det(1-zA \mid j,i)}{\det(1-zA)}.</math>
 
Das zweite <math>=</math> ist die geometrische Reihe, das dritte <math>=</math> ist die Cramersche Regel. Hierbei bedeutet <math>\mid j,i</math>, dass die <math>j</math>-te Zeile und die <math>i</math>-Spalte gestrichen werden. Sofern die Anzahl der Knoten <math>r</math> klein genug ist, liefert (1) eine praktische Berechnung für die erzeugende Funktion der Folge <math>p_{ij}</math>. Im Nenner steht dabei <math>\det(1-zA) = z^r \det(z^{-1} 1 - A)</math>, also das "umgedrehte" charakteristische Polynom von <math>A</math>. Aus den Koeffizienten lässt sich eine Rekursionsgleichung für die Folge <math>p_{ij}</math> ablesen.
 
Schauen wir uns ein einfaches Beispiel an. Es sei <math>\Gamma</math> der folgende Graph:

<math>\begin{tikzcd}[nodes={inner sep=2pt}] \ar[loop left,distance=3em,out=45,in=135,line width=0.12ex]{} v_1 \ar[line width=0.12ex]{rr} & & v_2 \ar[loop right,distance=3em,out=45,in=135,line width=0.12ex]{} \end{tikzcd}</math>

Die Adjazenzmatrix ist
 
<math>A=\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}.</math>
 
Es folgt für <math>m \in \mathds{N}</math>
 
<math>A^m = \begin{pmatrix} 1 & m \\ 0 & 1 \end{pmatrix},</math>
 
sodass es genau <math>m</math> Wege der Länge <math>m</math> von <math>v_1</math> nach <math>v_2</math> gibt – was man auch direkt erkennen kann. Die erzeugende Funktion lautet gemäß (1)
 
<math>\displaystyle \sum_{m=0}^{\infty} m \, z^m = (-1)^{1+2} \frac{\det(-z)}{\det \begin{pmatrix} 1-z & -z \\ 0 & 1 - z \end{pmatrix}} = \frac{z}{(1-z)^2}.</math>
 

Horizontale und vertikale Stücke

Schauen wir uns einmal einen typischen (Hamiltonschen) <math>7 {\times} 6</math>-Gitterweg an.
 
<math>\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw [lightgray] (0,0) grid (7,6);
\draw[blue] (0,0) to (3,0);
\draw[red] (3,0) to (3,3);
\draw[blue] (3,3) to (1,3);
\draw[red] (1,3) to (1,2);
\draw[blue] (1,2) to (2,2);
\draw[red] (2,2) to (2,1);
\draw[blue] (2,1) to (0,1);
\draw[red] (0,1) to (0,4);
\draw[blue] (0,4) to (2,4);
\draw[red] (2,4) to (2,5);
\draw[blue] (2,5) to (0,5);
\draw[red] (0,5) to (0,6);
\draw[blue] (0,6) to (5,6);
\draw[red] (5,6) to (5,5);
\draw[blue] (5,5) to (3,5);
\draw[red] (3,5) to (3,4);
\draw[blue] (3,4) to (4,4);
\draw[red] (4,4) to (4,2);
\draw[blue] (4,2) to (6,2);
\draw[red] (6,2) to (6,1);
\draw[blue] (6,1) to (4,1);
\draw[red] (4,1) to (4,0);
\draw[blue] (4,0) to (7,0);
\draw[red] (7,0) to (7,3);
\draw[blue] (7,3) to (5,3);
\draw[red] (5,3) to (5,4);
\draw[blue] (5,4) to (7,4);
\draw[red] (7,4) to (7,5);
\draw[blue] (7,5) to (6,5);
\draw[red] (6,5) to (6,6);
\draw[blue] (6,6) to (7,6);
\end{tikzpicture}</math>

Wir haben hier die horizontalen Striche blau und die vertikalen rot eingefärbt. Wenn wir das Gitter von links nach rechts aufbauen, fungiert jeweils eine Konfiguration roter Striche als Verbindung zwischen zwei Konfigurationen blauer Striche. Die ersten drei Verbindungen im obigen Beispiel sind etwa:
 
<math>\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw [lightgray] (-1,0) grid (1,6);
\draw[blue] (-1,0) to (-0.1,0);
\draw[blue] (0.1,0) to (1,0);
\draw[blue] (0.1,1) to (1,1);
\draw[blue] (0.1,4) to (1,4);
\draw[blue] (0.1,5) to (1,5);
\draw[blue] (0.1,6) to (1,6);
\draw[red] (0,1) to (0,4);
\draw[red] (0,5) to (0,6);
\end{tikzpicture}
\hspace{5ex}
\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw [lightgray] (0,0) grid (2,6);
\draw[blue] (0,0) to (0.9,0);
\draw[blue] (0,1) to (0.9,1);
\draw[blue] (0,4) to (0.9,4);
\draw[blue] (0,5) to (0.9,5);
\draw[blue] (0,6) to (0.9,6);
\draw[blue] (1.1,0) to (2,0);
\draw[blue] (1.1,1) to (2,1);
\draw[blue] (1.1,2) to (2,2);
\draw[blue] (1.1,3) to (2,3);
\draw[blue] (1.1,4) to (2,4);
\draw[blue] (1.1,5) to (2,5);
\draw[blue] (1.1,6) to (2,6);
\draw[red] (1,2) to (1,3);
\end{tikzpicture}
\hspace{5ex}
\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw [lightgray] (1,0) grid (3,6);
\draw[blue] (1,0) to (1.9,0);
\draw[blue] (1,1) to (1.9,1);
\draw[blue] (1,2) to (1.9,2);
\draw[blue] (1,3) to (1.9,3);
\draw[blue] (1,4) to (1.9,4);
\draw[blue] (1,5) to (1.9,5);
\draw[blue] (1,6) to (1.9,6);
\draw[blue] (2.1,0) to (3,0);
\draw[blue] (2.1,3) to (3,3);
\draw[blue] (2.1,6) to (3,6);
\draw[red] (2,1) to (2,2);
\draw[red] (2,4) to (2,5);
\end{tikzpicture}
</math>
 
Hamiltonsche Gitterwege können damit mit Wegen in einem gerichteten Graphen identifiziert werden. Genauer gesagt gibt es, für eine feste Höhe <math>n</math>, einen gerichteten Graphen <math>\Gamma_n^h</math>, dessen Knoten die Konfigurationen horizontaler Striche und dessen Kanten die Konfigurationen vertikaler Striche sind (eine präzise Definition folgt im nächsten Abschnitt), sodass Folgendes gilt: für jedes <math>m</math> können die Hamiltonschen <math>m {\times n}</math>-Gitterwege mit Wegen der Länge <math>m+1</math> in <math>\Gamma_n</math> identifiziert werden, die bei der Konfiguration mit einem horizontalen Strich unten starten und bei der Konfiguration mit einem horizontalen Strich oben enden. Selbstmeidende Gitterwege lassen sich ganz ähnlich beschreiben; der zugehörige Graph <math>\Gamma_n^s</math> ist hier nur etwas größer, damit die Kanten flexibler gesetzt und ein paar Gitterpunkte ausgelassen werden können. Dank dieser Beschreibung von Gitterwegen lässt sich die Transfer-Matrix-Methode anwenden.
 
Beim Übergang eines Knotens zu einem neuen Knoten können nur bestimmte vertikale Striche gesetzt werden. Es gibt drei kombinierbare Typen: (1) Wir verlagern einen horizontalen Strich woanders hin, also nach oben oder nach unten, oder behalten ihn einfach auf derselben Höhe bei. (2) Wo keine horizontale Striche sind, dürfen wir mit einem vertikalen Strich zwei neue horizontale Striche erschaffen. (3) Wir verbinden zwei gegebene horizontale Striche miteinander. Generell dürfen vertikale Striche nur an ihren Endpunkten auf horizontale Striche treffen.
 
<math>\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw [lightgray] (-1,0) grid (1,3);
\draw[blue] (-0.1,0) to (-1,0);
\draw[blue] (0.1,3) to (1,3);
\draw[red] (0,0) to (0,3);
\draw node at (0,0) [below] {(1)};
\end{tikzpicture}
\hspace{5ex}
\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw [lightgray] (-1,0) grid (1,3);
\draw[blue] (0.1,0) to (1,0);
\draw[blue] (0.1,3) to (1,3);
\draw[red] (0,0) to (0,3);
\draw node at (0,0) [below] {(2)};
\end{tikzpicture}
\hspace{5ex}
\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw [lightgray] (-1,0) grid (1,3);
\draw[blue] (-1,0) to (-0.1,0);
\draw[blue] (-1,3) to (-0.1,3);
\draw[red] (0,0) to (0,3);
\draw node at (0,0) [below] {(3)};
\end{tikzpicture}
</math>
 
Aber wir müssen beim Typ 3 aufpassen, dass beim Aufbauen des Weges nicht horizontale Striche miteinander verbunden werden, die bereits weiter links miteinander verbunden worden sind, denn das würde zu einem Kreis führen, was den Zusammenhang zerstört. So ist zum Beispiel im <math>7 {\times} 6</math>-Gitterweg oben als zweite Kante
 
<math>\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw [lightgray] (0,0) grid (2,6);
\draw[blue] (0,0) to (0.9,0);
\draw[blue] (0,1) to (0.9,1);
\draw[blue] (0,4) to (0.9,4);
\draw[blue] (0,5) to (0.9,5);
\draw[blue] (0,6) to (0.9,6);
\draw[blue] (1.1,0) to (2,0);
\draw[blue] (1.1,5) to (2,5);
\draw[blue] (1.1,6) to (2,6);
\draw[red] (1,1) to (1,4);
\draw[red,dashed,rounded corners=1ex] (0,1) to (0,4);
\draw[red,dashed,rounded corners=1ex] (0,5) to (0,6);
\end{tikzpicture}</math>
 
nicht erlaubt, weil die beiden horizontalen Striche mit den Höhenkoordinaten <math>1,4</math> bereits, wie mit der gestrichelten Linie angedeutet, in der ersten Kante miteinander verbunden worden sind. Wir müssen uns also nicht nur die Menge horizontaler Striche merken, sondern auch die Äquivalenzrelation, welche angibt, welche Striche bereits vorher verbunden wurden. Im obigen Beispiel stehen also <math>1,4</math> sowie <math>5,6</math> miteinander in Relation, wogegen <math>0</math> nur mit sich selbst in Relation steht.

Es gibt noch eine weitere Feinheit beim Typ 3: Angenommen, wir sind etwa beim folgenden Knoten und verbinden die beiden unteren horizontalen Striche miteinander:
 
<math>\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw [lightgray] (-1,0) grid (1,4);
\draw[blue] (-1,4) to (-0.1,4);
\draw[blue] (-1,0) to (-0.1,0);
\draw[blue] (-1,3) to (-0.1,3);
\draw[blue] (-1,1) to (-0.1,1);
\draw[blue] (-1,2) to (-0.1,2);
\draw[red,dashed,rounded corners=2ex] (-1,0) to (-1.7,0) to (-1.7,3) to (-1,3);
\draw[red,dashed,rounded corners=0.5ex] (-1,1) to (-1,2);
\draw[red] (0,0) to (0,1);
\end{tikzpicture}</math>
 
Dann dürfen wir die beiden oberen horizontalen Striche nicht mehr miteinander verbinden, denn das würde zu einem Kreis führen. Das Setzen von vertikalen Stücken wirkt sich sozusagen temporär auf die Äquivalenzrelation aus.

Kodierung von Knoten und Kanten

Wir kodieren die horizontalen Striche durch ihre Höhenkoordinaten und die Äquivalenzrelation auf ihnen durch eine Partition (nämlich der Äquivalenzklassen). Wir definieren daher (vorläufig) einen Knoten in <math>\Gamma_n^s</math> als eine Menge von nichtleeren paarweise disjunkten Teilmengen von <math>\{0,\dotsc,n\}</math>. Die beiden ausgezeichneten Knoten <math>\{\{0\}\}</math> und <math>\{\{n\}\}</math> wählen wir als Start- bzw. Endknoten für unsere Wege. Für zwei feste Knoten <math>v</math> und <math>w</math> definieren wir eine Kante <math>e : v \to w</math> in <math>\Gamma_n^s</math> als eine Menge von paarweise disjunkten Intervallen <math>\{i,i+1,\dotsc,i+k\} \subseteq \{0,\dotsc,n\}</math> mit <math>k>0</math>, die gewisse Eigenschaften erfüllen sollen (siehe unten). Der <math>7 {\times} 6</math>-Gitterweg oben ist demnach wie folgt kodiert:
 
<math>\{\{0\}\} \xrightarrow[\{5,6\}]{\{1,2,3,4\}} \{\{0\},\{1,4\},\{5,6\}\} \xrightarrow{\{2,3\}} \{\{0\},\{1,4\},\{2,3\},\{5,6\}\} \smallskip\\
~~~~~~~~~\xrightarrow[\{4,5\}]{\{1,2\}} \{\{0\},\{3,6\}\} \xrightarrow[\{4,5\}]{\{0,1,2,3\}} \{\{4,5\},\{6\}\}\smallskip\\
~~~~~~~~~\xrightarrow[\{2,3,4\}]{\{0,1\}} \{\{0,1\},\{2,5\},\{6\}\} \xrightarrow[\{5,6\}]{\{3,4\}} \{\{0,1\},\{2\},\{3,4\}\}\smallskip\\
~~~~~~~~~\xrightarrow[\{5,6\}]{\{1,2\}} \{\{0\},\{3,4\},\{5,6\}\} \xrightarrow[\{4,5\}]{\{0,1,2,3\}} \{\{6\}\}</math>
   
Die Nachfolgerknoten eines Knotens <math>v</math> werden so bestimmt: Man geht von einer Kante <math>e</math> aus, also einer Menge von paarweise disjunkten Intervallen mit jeweils mindestens zwei Elementen. Dabei soll gelten, dass für jedes Intervall <math>b \in e</math> der Durchschnitt <math>b \cap v</math> höchstens aus den Endpunkten <math>b_{\mathrm{min}}</math> und <math>b_{\mathrm{bmax}}</math> von <math>b</math> besteht. Man geht die Intervalle nun nacheinander durch und baut dadurch schrittweise einen neuen Knoten auf. Wenn <math>b \cap v = \{b_{\mathrm{min}}\}</math> gilt, liegt Typ 1 vor, und in der Äquivalenzklasse von <math>v</math>, die <math>b_{\mathrm{min}}</math> enthält, wird <math>b_{\mathrm{min}}</math> gestrichen und durch <math>b_{\mathrm{max}}</math> ersetzt. Analog geht man vor, wenn <math>b \cap v = \{b_{\mathrm{max}}\}</math> gilt. Wenn <math>b \cap v</math> leer ist, liegt Typ 2 vor. Hier wird einfach die neue Äquivalenzklasse <math>\{b_{\mathrm{min}},b_{\mathrm{max}}\}</math> zu <math>v</math> hinzugefügt. Wenn schließlich <math>b \cap v = \{b_{\mathrm{min}},b_{\mathrm{max}}\}</math> gilt, liegt Typ 3 vor. Hier werden die beiden Äquivalenzklassen von <math>v</math>, die <math>b_{\mathrm{min}}</math> bzw. <math>b_{\mathrm{max}}</math> enthalten, miteinander vereinigt, und anschließend <math>b_{\mathrm{min}}</math> und <math>b_{\mathrm{max}}</math> daraus entfernt. Dies geht allerdings nur, wenn <math>b_{\mathrm{min}},b_{\mathrm{max}}</math> nicht bezüglich <math>v</math> bzw. dem temporär erstellten Knoten äquivalent sind. Zum Beispiel wird oben aus dem Knoten <math>v = \{\{0\},\{1,4\},\{2,3\},\{5,6\}\}</math> zunächst mittels <math>b_1=\{1,2\}</math> (Typ 3) temporär der Knoten <math>\{\{0\},\{3,4\},\{5,6\}\}</math> und dann mittels <math>b_2=\{4,5\}</math> (Typ 3) der eigentliche Nachfolger <math>\{\{0\},\{3,6\}\}</math> von <math>v</math> erstellt. Hier wäre <math>b_2=\{3,4\}</math> nicht erlaubt. Man kann sich überlegen, dass es zwischen zwei Knoten höchstens eine Kante gibt.

Wir interessieren uns lediglich für die Knoten, die von <math>\{\{0\}\}</math> aus über Wege erreichbar sind. Man kann sich mit einfachen Skizzen überlegen, dass genau die Mengen sind, die genau eine Menge mit einem Element und ansonsten nur Mengen mit zwei Elementen haben, also von der Form

<math>\{\{a\},\{x_1,y_1\},\{x_2,y_2\},\dotsc\},</math>
 
sind, sodass obendrein gilt: Es gilt niemals <math>x_i<a<y_i</math>, und es gilt niemals <math>x_i<x_j<y_i<y_j</math>. (Es kann durchaus <math>x_i<x_j<y_j<y_i</math> gelten, siehe oben.) Wir werden uns daher auf diese Knoten beschränken. Das macht die Adjazenzmatrix von <math>\Gamma_n^s</math> kleiner, und damit die Berechnung einfacher. Die Anzahl der Knoten in <math>\Gamma^s_n</math> ist die Folge A002026.
 
Der Graph <math>\Gamma_n^h</math> habe dieselben Knoten wie <math>\Gamma_n^s</math>, aber weniger Kanten: Wir müssen nämlich sicherstellen, dass sämtliche Gitterpunkte vertikal erfasst werden. So gibt es etwa in <math>\Gamma_2^h</math> keine Kante <math>\{\{0\}\} \to \{\{1\}\}</math>, in <math>\Gamma_2^s</math> aber schon.
 
<math>\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw [lightgray] (-1,0) grid (1,2);
\draw[blue] (-1,0) to (-0.1,0);
\draw[blue] (0.1,1) to (1,1);
\draw[red] (0,0) to (0,1);
\draw (0,2) circle [radius=1.5ex];
\end{tikzpicture}</math>
 
Formal ist eine Kante <math>e : v \to w</math> in <math>\Gamma_n^s</math> genau dann eine Kante in <math>\Gamma_n^h</math>, wenn <math>\bigcup v \cup \bigcup e = \{0,\dotsc,n\}</math> gilt. Durch diese Restriktion sind noch weniger Knoten vom Startknoten aus erreichbar, aber eine genaue Charakterisierung ist mir nicht bekannt.
 
Indem wir als Endknoten <math>\{\{0\}\}</math> nehmen, könnten wir mit der Transfer-Matrix-Methode ebenfalls die selbstmeidenden oder Hamiltonschen Gitterwege zählen, die unten links anfangen und unten rechts enden.

Berechnungen

Wir wenden jetzt die Transfer-Matrix-Methode auf die Graphen <math>\Gamma_n^s</math> und <math>\Gamma_n^h</math> für kleine Beispiele von <math>n</math> an. Es sei <math>s_{m,n}</math> bzw. <math>h_{m,n}</math> die gesuchte Zahl der selbstmeidenden bzw. Hamiltonschen Gitterwege von <math>(0,0)</math> nach <math>(m,n)</math>. Wir halten <math>n</math> fest und betrachten die erzeugenden Funktionen

<math>\displaystyle S_n(z) := \sum_{m=0}^{\infty} s_{m,n} \, z^m,\medskip\\
H_n(z) := \sum_{m=0}^{\infty} h_{m,n} \, z^m.</math>

Der Fall n = 0

Für <math>n=0</math> gibt es genau einen selbstmeidenden Weg von <math>(0,0)</math> nach <math>(m,0)</math>, für jedes <math>m</math>, und dieser ist auch Hamiltonsch. Es gilt also

<math>(2) \quad\displaystyle S_0(z)=H_0(z) = \sum_{m=0}^{\infty} z^m = \frac{1}{1-z}</math>

bzw.

<math>(2') \quad\displaystyle s_{m,0} = h_{m,0} = 1.</math>
 
Wir können dies auch mit der Transfer-Matrix-Methode zeigen, denn die Adjazenzmatrix ist hier einfach <math>\begin{pmatrix} 1 \end{pmatrix}</math>.

Der Fall n = 1

Für <math>n=1</math> gibt es nur zwei Knoten, nämlich <math>v_1=\{\{0\}\}</math> und <math>v_2=\{\{1\}\}</math>. Der Graph <math>\Gamma_1^s</math> ist vollständig, seine Adjazenzmatrix lautet
 
<math>A=\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}.</math>
 
Die erzeugende Funktion für die Wege der Länge <math>m</math> in <math>\Gamma_1^s</math> ist daher
 
<math>\displaystyle (-1)^{1+2} \frac{\det(1-zA \mid 2,1)}{\det(1-zA)} = - \frac{\det (-z)}{\det \begin{pmatrix} 1-z & -z \\ -z & 1-z \end{pmatrix}} = \frac{z}{1-2z}.</math>
 
Daraus folgt

<math>(3) \quad\displaystyle S_1(z) = \frac{1}{1-2z}</math>
 
bzw. (was man auch per Hand einsehen könnte)

<math>(3')\quad \displaystyle s_{m,1} = 2^m.</math>
 
Für <math>m=4</math> etwa sehen die Gitterwege folgendermaßen aus; nur einer (in grün) ist Hamiltonsch.

<math>\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw[lightgray] (0,0) grid (4,1);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (2,0) to (3,0) to (4,0) to (4,1);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw[lightgray] (0,0) grid (4,1);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (2,0) to (3,0) to (3,1) to (4,1);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw[lightgray] (0,0) grid (4,1);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (2,0) to (2,1) to (3,1) to (3,0) to (4,0) to (4,1);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw[lightgray] (0,0) grid (4,1);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (2,0) to (2,1) to (3,1) to (4,1);
\end{tikzpicture}
\vspace{3ex}

\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw[lightgray] (0,0) grid (4,1);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (1,1) to (2,1) to (2,0) to (3,0) to (4,0) to (4,1);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw[lightgray] (0,0) grid (4,1);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (1,1) to (2,1) to (2,0) to (3,0) to (3,1) to (4,1);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw[lightgray] (0,0) grid (4,1);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (1,1) to (2,1) to (3,1) to (3,0) to (4,0) to (4,1);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw[lightgray] (0,0) grid (4,1);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (1,1) to (2,1) to (3,1) to (4,1);
\end{tikzpicture}
\vspace{3ex}

\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw[lightgray] (0,0) grid (4,1);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (1,1) to (1,0) to (2,0) to (3,0) to (4,0) to (4,1);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw[lightgray] (0,0) grid (4,1);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (1,1) to (1,0) to (2,0) to (3,0) to (3,1) to (4,1);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw[lightgray] (0,0) grid (4,1);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (0,1) to (1,1) to (1,0) to (2,0) to (2,1) to (3,1) to (3,0) to (4,0) to (4,1);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw[lightgray] (0,0) grid (4,1);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (1,1) to (1,0) to (2,0) to (2,1) to (3,1) to (4,1);
\end{tikzpicture}
\vspace{3ex}

\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw[lightgray] (0,0) grid (4,1);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (1,1) to (2,1) to (2,0) to (3,0) to (4,0) to (4,1);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw[lightgray] (0,0) grid (4,1);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (1,1) to (2,1) to (2,0) to (3,0) to (3,1) to (4,1);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw[lightgray] (0,0) grid (4,1);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (1,1) to (2,1) to (3,1) to (3,0) to (4,0) to (4,1);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw[lightgray] (0,0) grid (4,1);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (1,1) to (2,1) to (3,1) to (4,1);
\end{tikzpicture}</math>
 
Im Graphen <math>\Gamma_1^h</math> gibt es keine Kanten <math>\{\{0\}\} \to \{\{0\}\}</math> und <math>\{\{1\}\} \to \{\{1\}\}</math>, weil dabei der obere bzw. untere Gitterpunkt nicht getroffen wird. Die Adjazenzmatrix ist daher

<math>A=\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}.</math>

Die erzeugende Funktion für die Wege der Länge <math>m</math> in <math>\Gamma_1^h</math> ist daher

<math>\displaystyle (-1)^{1+2} \frac{\det(-z)}{\det \begin{pmatrix} 1 & - z \\ -z & 1 \end{pmatrix}} = \frac{z}{1-z^2}.</math>
 
Daraus folgt

<math>\displaystyle (4)\quad H_1(z) = \frac{1}{1-z^2}</math>
 
bzw. (was man auch per Hand einsehen könnte)
 
<math>\displaystyle (4')\quad h_{m,1} = \left\{\begin{array}{ll} 1 & m \text{ gerade,} \\ 0 & m \text{ ungerade.} \end{array}\right.</math>
 

Der Fall n = 2

Kommen wir nun zum Fall <math>n=2</math>, wo die Transfer-Matrix-Methode erstmals ihre Wirkung entfaltet. Es gibt die folgenden Knoten:
 
<math>\begin{array}{ccccc}\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw [lightgray] (0,0) grid (1,2);
\draw[blue] (0,0) to (1,0);
\end{tikzpicture} & \begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw [lightgray] (0,0) grid (1,2);
\draw[blue] (0,1) to (1,1);
\end{tikzpicture}
&
\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw [lightgray] (0,0) grid (1,2);
\draw[blue] (0,2) to (1,2);
\end{tikzpicture}
&
\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw [lightgray] (0,0) grid (1,2);
\draw[blue] (0,0) to (1,0);
\draw[blue] (0,1) to (1,1);
\draw[blue] (0,2) to (1,2);
\draw[red,dashed] (0,0) to (0,1);
\end{tikzpicture}
&
\begin{tikzpicture}[line width=0.2ex,scale=0.6]
\draw [lightgray] (0,0) grid (1,2);
\draw[blue] (0,0) to (1,0);
\draw[blue] (0,1) to (1,1);
\draw[blue] (0,2) to (1,2);
\draw[red,dashed] (0,1) to (0,2);
\end{tikzpicture}
\\[1ex]
~v_1 = \{\{0\}\}}~ & ~v_2 = \{\{1\}\}~ & ~v_3 = \{\{2\}\}~ & ~v_4 = \{\{0,1\},\{2\}\}~ & ~v_5 = \{\{0\},\{1,2\}\}~\end{array}</math>
 
Die Adjazenzmatrix für <math>\Gamma^s_1</math> berechnet sich zu
 
<math>A = \begin{pmatrix}
1 & 1 & 1 & 0 & 1 \\
1 & 1 & 1 & 0 & 0 \\
1 & 1 & 1 & 1 & 0 \\
1 & 0 & 0 & 1 & 0 \\
0 & 0 & 1 & 0 & 1
\end{pmatrix}.</math>
 
Zum Beispiel ist die erste Zeile <math>(1,1,1,0,1)</math>, weil es Kanten <math>v_1 \to v_1</math>, <math>v_1 \to v_2</math>, <math>v_1 \to v_3</math> vom Typ 1 und eine Kante <math>v_1 \to v_5</math> vom Typ 2 gibt, aber es gibt keine Kante <math>v_1 \to v_4</math>:
 
<math>\begin{tikzpicture}[scale=0.6,line width=0.2ex]
\draw [lightgray] (0,0) grid (2,2);
\draw[blue] (0,0) to (0.9,0);
\draw[blue] (1.1,0) to (2,0);
\draw[blue] (1.1,1) to (2,1);
\draw[blue] (1.1,2) to (2,2);
\draw[red,dashed,rounded corners=0.3ex] (1,0) to [out=180,in=-90] (0.5,0.5) to [out=90,in=180](1,1);
\draw node at (0.5,1) [above] {?};
\end{tikzpicture}</math>
 
Die nun folgende Berechnung der Determinanten kann man einem Computeralgebrasystem übergeben:
 
<math>\displaystyle (-1)^{1+3} \frac{\det(1-zA \mid 3,1)}{\det(1-zA)} = \frac{z^3-z}{z^4+2z^3-3z^2+4z-1}</math>
 
Es folgt

<math>(5)\quad\displaystyle S_2(z) = \frac{z^2-1}{z^4+2z^3-3z^2+4z-1}.</math>
 
Daraus folgt wiederum eine lineare Rekursionsgleichung für <math>s_{m,2}</math> vom Grad <math>4</math>, nämlich
 
<math>(5')\quad\displaystyle s_{m,2} =  4 s_{m-1,2} - 3 s_{m-2,2} + 2 s_{m-3,2} + s_{m-4,2}</math>
 
für <math>m \geq 4</math>. Die Anfangswerte lassen sich mit der Formel <math>s_{m,2} = (A^{m+1})_{1,3}</math> bestimmen, sie lauten <math>s_{0,2}=1</math>, <math>s_{1,2}=4</math>, <math>s_{2,2}=12</math>, <math>s_{3,2} = 38</math>. Hier eine Veranschaulichung des letzten Wertes:
 
<math>\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (1,0) to (2,0) to (3,0) to (3,1) to (2,1) to (1,1) to (0,1) to (0,2) to (1,2) to (2,2) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (2,0) to (3,0) to (3,1) to (2,1) to (1,1) to (1,2) to (2,2) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (2,0) to (3,0) to (3,1) to (2,1) to (2,2) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (2,0) to (3,0) to (3,1) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (2,0) to (2,1) to (1,1) to (0,1) to (0,2) to (1,2) to (2,2) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (2,0) to (2,1) to (1,1) to (1,2) to (2,2) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (2,0) to (2,1) to (3,1) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (2,0) to (2,1) to (2,2) to (3,2);
\end{tikzpicture}
\vspace{3ex}

\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (1,0) to (1,1) to (0,1) to (0,2) to (1,2) to (2,2) to (2,1) to (2,0) to (3,0) to (3,1) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (1,1) to (0,1) to (0,2) to (1,2) to (2,2) to (2,1) to (3,1) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (1,1) to (0,1) to (0,2) to (1,2) to (2,2) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (1,1) to (2,1) to (2,0) to (3,0) to (3,1) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (1,1) to (2,1) to (3,1) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (1,1) to (2,1) to (2,2) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (1,1) to (1,2) to (2,2) to (2,1) to (2,0) to (3,0) to (3,1) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (1,1) to (1,2) to (2,2) to (2,1) to (3,1) to (3,2);
\end{tikzpicture}
\vspace{3ex}

\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (1,0) to (1,1) to (1,2) to (2,2) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (1,1) to (1,0) to (2,0) to (3,0) to (3,1) to (2,1) to (2,2) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (1,1) to (1,0) to (2,0) to (3,0) to (3,1) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (1,1) to (1,0) to (2,0) to (2,1) to (3,1) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (1,1) to (1,0) to (2,0) to (2,1) to (2,2) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (1,1) to (2,1) to (2,0) to (3,0) to (3,1) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (1,1) to (2,1) to (3,1) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (1,1) to (2,1) to (2,2) to (3,2);
\end{tikzpicture}
\vspace{3ex}

\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (1,1) to (1,2) to (2,2) to (2,1) to (2,0) to (3,0) to (3,1) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (1,1) to (1,2) to (2,2) to (2,1) to (3,1) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (1,1) to (1,2) to (2,2) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (0,1) to (0,2) to (1,2) to (1,1) to (1,0) to (2,0) to (3,0) to (3,1) to (2,1) to (2,2) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (0,2) to (1,2) to (1,1) to (1,0) to (2,0) to (3,0) to (3,1) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (0,2) to (1,2) to (1,1) to (1,0) to (2,0) to (2,1) to (3,1) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (0,2) to (1,2) to (1,1) to (1,0) to (2,0) to (2,1) to (2,2) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (0,2) to (1,2) to (1,1) to (2,1) to (2,0) to (3,0) to (3,1) to (3,2);
\end{tikzpicture}
\vspace{3ex}

\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (0,2) to (1,2) to (1,1) to (2,1) to (3,1) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (0,2) to (1,2) to (1,1) to (2,1) to (2,2) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (0,1) to (0,2) to (1,2) to (2,2) to (2,1) to (1,1) to (1,0) to (2,0) to (3,0) to (3,1) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (0,2) to (1,2) to (2,2) to (2,1) to (2,0) to (3,0) to (3,1) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (0,2) to (1,2) to (2,2) to (2,1) to (3,1) to (3,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (3,2);
\draw[rounded corners=0.3ex,black!50!blue] (0,0) to (0,1) to (0,2) to (1,2) to (2,2) to (3,2);
\end{tikzpicture}</math>

Die Hamiltonschen Gitterwege sind dabei grün markiert. Im Graphen <math>\Gamma^h_1</math> wird <math>v_2=\{\{1\}\}</math> gar nicht von <math>\{\{0\}\}</math> aus erreicht, sodass wir diesen Knoten streichen dürfen. Die Kanten <math>v_1 \to v_1</math> und <math>v_3 \to v_3</math> sind nicht mehr zulässig. Die Adjazenzmatrix ist daher
 
<math>A = \begin{pmatrix}
0 & 1 & 0 & 1 \\
1 & 0 & 1 & 0 \\
1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1
\end{pmatrix}.</math>
 
Dann ist
 
<math>\displaystyle (-1)^{1+2} \frac{\det(1-zA \mid 2,1)}{\det(1-zA)} =  \frac{z-z^2}{1-2z}.</math>
 
Es folgt

<math>(5)\quad\displaystyle H_2(z) = \frac{1-z}{1-2z} = 1 + \frac{z}{1-2z}</math>
 
bzw. (was sich ebenfalls noch direkt herleiten lässt)

<math>(5')\quad\displaystyle h_{m,2} = \left\{\begin{array}{ll} 1 & m = 0 \\ 2^{m-1} & m > 0 \end{array}\right.</math>
 
Zum Beispiel ist <math>h_{4,2}=8</math>:

<math>\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,2);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (1,0) to (2,0) to (3,0) to (4,0) to (4,1) to (3,1) to (2,1) to (1,1) to (0,1) to (0,2) to (1,2) to (2,2) to (3,2) to (4,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,2);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (1,0) to (2,0) to (2,1) to (1,1) to (0,1) to (0,2) to (1,2) to (2,2) to (3,2) to (3,1) to (3,0) to (4,0) to (4,1) to (4,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,2);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (1,0) to (1,1) to (0,1) to (0,2) to (1,2) to (2,2) to (2,1) to (2,0) to (3,0) to (4,0) to (4,1) to (3,1) to (3,2) to (4,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,2);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (1,0) to (1,1) to (0,1) to (0,2) to (1,2) to (2,2) to (3,2) to (3,1) to (2,1) to (2,0) to (3,0) to (4,0) to (4,1) to (4,2);
\end{tikzpicture}
\vspace{3ex}

\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,2);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (0,1) to (0,2) to (1,2) to (1,1) to (1,0) to (2,0) to (3,0) to (4,0) to (4,1) to (3,1) to (2,1) to (2,2) to (3,2) to (4,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,2);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (0,1) to (0,2) to (1,2) to (1,1) to (1,0) to (2,0) to (2,1) to (2,2) to (3,2) to (3,1) to (3,0) to (4,0) to (4,1) to (4,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,2);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (0,1) to (0,2) to (1,2) to (2,2) to (2,1) to (1,1) to (1,0) to (2,0) to (3,0) to (4,0) to (4,1) to (3,1) to (3,2) to (4,2);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,2);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (0,1) to (0,2) to (1,2) to (2,2) to (3,2) to (3,1) to (2,1) to (1,1) to (1,0) to (2,0) to (3,0) to (4,0) to (4,1) to (4,2);
\end{tikzpicture}</math>
 

Der Fall n = 3

Für <math>n=3</math> wird es schon etwas mühselig, die Rechnungen per Hand zu machen. Wir haben die Knoten
 
<math>v_1=\{\{0\}\},~v_2=\{\{0\},\{1,2\}\}, ~v_3=\{\{0\},\{1,3\}\}, ~v_4 = \{\{0\},\{2,3\}\}, \medskip\\
v_5 = \{\{0,1\},\{2\}\}, ~v_6 = \{\{0,1\},\{3\}\}, ~v_7 = \{\{0,2\},\{3\}\}, ~v_8 = \{\{1\}\},\medskip \\
v_{9} = \{\{1\},\{2,3\}\}, ~v_{10} = \{\{1,2\},\{3\}\}, ~v_{11} = \{\{2\}\}, ~v_{12} = \{\{3\}\}.</math>
 
Die <math>12 {\times} 12</math>-Adjazenzmatrix und dann auch die erzeugende Funktion lassen sich schnell mit einem Programm ausrechnen, das wir weiter unten vorstellen. Die Ergebnisse sind: Die Adjazenzmatrix von <math>\Gamma_3^s</math> ist

<math>{\footnotesize A = \left[\begin{array}{p{0.2ex}p{0.2ex}p{0.2ex}p{0.2ex}p{0.2ex}p{0.2ex}p{0.2ex}p{0.2ex}p{0.2ex}p{0.2ex}p{0.2ex}p{0.2ex}}
 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\[0.2ex]
 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\[0.2ex]
 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\[0.2ex]
 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\[0.2ex]
 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\[0.2ex]
 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\[0.2ex]
 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 \\[0.2ex]
 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\[0.2ex]
 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\[0.2ex]
 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\[0.2ex]
 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 \\[0.2ex]
 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1
\end{array}\right].}</math>

Daraus ergibt sich

<math>(6)\quad\displaystyle {\footnotesize S_3(z) = \frac{z^{10}-15z^8+6z^7+50z^6-26z^5-39z^4+36z^3-4z^2-4z+1}{z^{12}+4z^{11}-12z^{10}-40z^9+69z^8+94z^7-175z^6+16z^5+133z^4-124z^3+54z^2-12z+1}}</math>
 
und zum Beispiel <math>s_{3,3} = (A^4)_{1,12} = 184</math> sowie <math>s_{4,3} = (A^5)_{1,12} = 976</math>. Die <math>3 {\times} 3</math>-Gitterwege kann man sich hier als pdf anschauen; keiner davon ist Hamiltonsch. Die Adjazenzmatrix von <math>\Gamma_3^h</math> lässt sich zwar nicht verkleinern wie zuvor, hat aber noch viel mehr Nullen (u.a. auf der Diagonalen), und es ergibt sich

<math>(7)\quad\displaystyle H_3(z) = \frac{z^4-3z^2+1}{z^8-7z^6+9z^4-7z^2+1}.</math>

Zum Beispiel gilt <math>h_{4,3}=20</math>:
 
<math>\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,3);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (1,0) to (2,0) to (3,0) to (4,0) to (4,1) to (3,1) to (2,1) to (1,1) to (0,1) to (0,2) to (0,3) to (1,3) to (1,2) to (2,2) to (2,3) to (3,3) to (3,2) to (4,2) to (4,3);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,3);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (1,0) to (2,0) to (3,0) to (4,0) to (4,1) to (3,1) to (2,1) to (2,2) to (1,2) to (1,1) to (0,1) to (0,2) to (0,3) to (1,3) to (2,3) to (3,3) to (3,2) to (4,2) to (4,3);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,3);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (1,0) to (2,0) to (3,0) to (4,0) to (4,1) to (4,2) to (3,2) to (3,1) to (2,1) to (1,1) to (0,1) to (0,2) to (0,3) to (1,3) to (1,2) to (2,2) to (2,3) to (3,3) to (4,3);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,3);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (1,0) to (2,0) to (3,0) to (4,0) to (4,1) to (4,2) to (3,2) to (3,1) to (2,1) to (2,2) to (1,2) to (1,1) to (0,1) to (0,2) to (0,3) to (1,3) to (2,3) to (3,3) to (4,3);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,3);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (1,0) to (2,0) to (2,1) to (1,1) to (0,1) to (0,2) to (0,3) to (1,3) to (1,2) to (2,2) to (2,3) to (3,3) to (3,2) to (3,1) to (3,0) to (4,0) to (4,1) to (4,2) to (4,3);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,3);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (1,0) to (2,0) to (2,1) to (3,1) to (3,0) to (4,0) to (4,1) to (4,2) to (3,2) to (2,2) to (1,2) to (1,1) to (0,1) to (0,2) to (0,3) to (1,3) to (2,3) to (3,3) to (4,3);
\end{tikzpicture}
\vspace{3ex}

\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,3);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (1,0) to (2,0) to (2,1) to (2,2) to (1,2) to (1,1) to (0,1) to (0,2) to (0,3) to (1,3) to (2,3) to (3,3) to (3,2) to (3,1) to (3,0) to (4,0) to (4,1) to (4,2) to (4,3);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,3);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (1,0) to (1,1) to (0,1) to (0,2) to (0,3) to (1,3) to (1,2) to (2,2) to (2,3) to (3,3) to (3,2) to (3,1) to (2,1) to (2,0) to (3,0) to (4,0) to (4,1) to (4,2) to (4,3);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,3);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (0,1) to (1,1) to (1,0) to (2,0) to (3,0) to (4,0) to (4,1) to (3,1) to (2,1) to (2,2) to (1,2) to (0,2) to (0,3) to (1,3) to (2,3) to (3,3) to (3,2) to (4,2) to (4,3);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,3);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (0,1) to (1,1) to (1,0) to (2,0) to (3,0) to (4,0) to (4,1) to (4,2) to (3,2) to (3,1) to (2,1) to (2,2) to (1,2) to (0,2) to (0,3) to (1,3) to (2,3) to (3,3) to (4,3);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,3);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (0,1) to (1,1) to (1,0) to (2,0) to (2,1) to (3,1) to (3,0) to (4,0) to (4,1) to (4,2) to (3,2) to (2,2) to (1,2) to (0,2) to (0,3) to (1,3) to (2,3) to (3,3) to (4,3);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,3);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (0,1) to (1,1) to (1,0) to (2,0) to (2,1) to (2,2) to (1,2) to (0,2) to (0,3) to (1,3) to (2,3) to (3,3) to (3,2) to (3,1) to (3,0) to (4,0) to (4,1) to (4,2) to (4,3);
\end{tikzpicture}
\vspace{3ex}

\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,3);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (0,1) to (0,2) to (0,3) to (1,3) to (1,2) to (1,1) to (1,0) to (2,0) to (3,0) to (4,0) to (4,1) to (3,1) to (2,1) to (2,2) to (2,3) to (3,3) to (3,2) to (4,2) to (4,3);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,3);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (0,1) to (0,2) to (0,3) to (1,3) to (1,2) to (1,1) to (1,0) to (2,0) to (3,0) to (4,0) to (4,1) to (4,2) to (3,2) to (3,1) to (2,1) to (2,2) to (2,3) to (3,3) to (4,3);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,3);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (0,1) to (0,2) to (0,3) to (1,3) to (1,2) to (1,1) to (1,0) to (2,0) to (2,1) to (3,1) to (3,0) to (4,0) to (4,1) to (4,2) to (3,2) to (2,2) to (2,3) to (3,3) to (4,3);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,3);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (0,1) to (0,2) to (0,3) to (1,3) to (1,2) to (1,1) to (1,0) to (2,0) to (2,1) to (2,2) to (2,3) to (3,3) to (3,2) to (3,1) to (3,0) to (4,0) to (4,1) to (4,2) to (4,3);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,3);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (0,1) to (0,2) to (0,3) to (1,3) to (1,2) to (2,2) to (2,3) to (3,3) to (3,2) to (3,1) to (2,1) to (1,1) to (1,0) to (2,0) to (3,0) to (4,0) to (4,1) to (4,2) to (4,3);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,3);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (0,1) to (0,2) to (0,3) to (1,3) to (2,3) to (2,2) to (1,2) to (1,1) to (1,0) to (2,0) to (2,1) to (3,1) to (3,0) to (4,0) to (4,1) to (4,2) to (3,2) to (3,3) to (4,3);
\end{tikzpicture}
\vspace{3ex}

\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,3);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (0,1) to (0,2) to (0,3) to (1,3) to (2,3) to (3,3) to (3,2) to (2,2) to (1,2) to (1,1) to (1,0) to (2,0) to (2,1) to (3,1) to (3,0) to (4,0) to (4,1) to (4,2) to (4,3);
\end{tikzpicture}\hspace{3ex}\begin{tikzpicture}[line width=0.2ex,scale=0.4]
\draw[lightgray] (0,0) grid (4,3);
\draw[rounded corners=0.3ex,black!70!green] (0,0) to (0,1) to (0,2) to (0,3) to (1,3) to (2,3) to (3,3) to (3,2) to (3,1) to (2,1) to (2,2) to (1,2) to (1,1) to (1,0) to (2,0) to (3,0) to (4,0) to (4,1) to (4,2) to (4,3);
\end{tikzpicture}</math>

Das Programm funktioniert problemlos auch für größere <math>n</math>, nur werden die erzeugenden Funktionen extrem groß. Zum Beispiel hat <math>S_4(z)</math> Grad <math>27</math> und <math>S_5(z)</math> Grad <math>75</math>. Hingegen hat <math>H_4(z)</math> Grad <math>12</math> und <math>H_5(z)</math> Grad <math>46</math>. Für ungerade <math>n</math> ist allerdings <math>H_n(z)</math> eine rationale Funktion in <math>z^2</math>, weil <math>h_{m,n}=0</math> für ungerade <math>m</math> gilt, und der Grad von <math>H_n(\sqrt{z})</math> ist dann nur halb so groß. Eine Veranschaulichung von <math>h_{4,4}=104</math> gibt es hier als pdf.
 

Übersicht

FolgeAnfangswerteOEIS-Eintrag
<math>s_{-,0}</math><math>1,1,1,\dotsc</math>A000012
<math>s_{-,1}</math><math>1,2,4,8,16,32,\dotsc</math>A000079
<math>s_{-,2}</math><math>1, 4, 12, 38, 125, 414, \dotsc</math>A006192
<math>s_{-,3}</math><math>1, 8, 38, 184, 976, 5382, \dotsc</math>A007786
<math>s_{-,4}</math><math>1, 16, 125, 976, 8512, 79384,  \dotsc</math>A007787
<math>s_{-,5}</math><math>1, 32, 414, 5382, 79384, 1262816, \dotsc</math>A145403
FolgeAnfangswerteOEIS-Eintrag
<math>h_{-,0}</math><math>1,1,1,\dotsc</math>A000012
<math>h_{-,1}</math><math>1,0,1,0,1,0,\dotsc</math>A059841
<math>h_{-,2}</math><math>1, 1, 2, 4, 8, 16, \dotsc</math>A011782
<math>h_{-,3}</math><math>1, 0, 4, 0, 20, 0, 111, \dotsc</math>A014523
<math>h_{-,4}</math><math>1, 1, 8, 20, 104, 378,  \dotsc</math>A014584
<math>h_{-,5}</math><math>  1, 0, 16, 0, 378, 0, 10204, \dotsc</math>

Die Doppelfolge <math>s_{m,n}</math> ist A064298, die Diagonalfolge <math>s_{n,n}</math> ist A007764, und die Diagonalfolge <math>h_{2n+1,2n+1}</math> ist A001184. Die erzeugenden Funktionen stehen hier.

Das Programm

Das folgende Programm ist in GAP geschrieben, lässt sich aber genauso gut in anderen Programmiersprachen umsetzen. Wir verwenden die bereits besprochene Kodierung von Knoten und Kanten. Abgesehen von der schnellen automatisierten Berechnung von Adjazenzmatrizen, erzeugenden Funktionen und konkreten Werten der Folgen, können wir die Funktionen Nodes, Edges, SuccNodes auch als eine Definition der Graphen <math>\Gamma_n^s</math> und <math>\Gamma_n^h</math> ansehen.


 
Zum Beispiel liefern die Eingaben

FirstValues(3,10,"s");
AdjacencyMatrix(2,"h");
GenFunct(4,"h");
PathNumber(7,6);
 
die ersten Werte <math>s_{0,3},s_{1,3},\dotsc,s_{10,3}</math> der Folge <math>s_{-,3}</math>, die Adjazenzmatrix von <math>\Gamma_2^h</math>, die erzeugende Funktion <math>H_4(z)</math>, und den Wert <math>s_{7,6}=16\,230\,458\,696</math>. Übrigens wird <math>s_{m,n}</math> schneller als <math>s_{n,m}</math> berechnet, wenn <math>n<m</math> gilt.
 
Für die Aufzählung und die Erstellung der LaTeX-Codes der Gitterwege im Artikel habe ich ein weiteres, allerdings weitaus weniger effizientes Programm verwendet, welches bei jedem aktuellen Gitterpunkt <math>(x,y)</math> die umgebenden Gitterpunkte besucht und sich dann merkt, dass es bereits bei <math>(x,y)</math> war. Das lässt sich zum Beispiel durch eine Rekursion beschreiben: Ein selbstmeidender Gitterweg von <math>(0,0)</math> nach <math>(m,n)</math> ist ein Spezialfall eines selbstmeidenden Gitterweges von <math>(x,y)</math> nach <math>(m,n)</math> mit einer Menge von verbotenen Gitterpunkten <math>V</math>, nämlich <math>x=y=0</math> und <math>V=\emptyset</math>. Erst die Verallgemeinerung auf beliebige Startpunkte und Verbotsmengen lässt eine Rekursion zu: Einen selbstmeidenden Gitterweg von <math>(x,y)</math> nach <math>(m,n)</math> mit Verbotsmenge <math>V</math> gibt es nicht, wenn einer der Punkte außerhalb des Gitters oder in <math>V</math> liegt. Ansonsten gilt: Wenn <math>(x,y)=(m,n)</math>, dann gibt es genau einen solchen Gitterweg, nämlich <math>((x,y))</math>. Ansonsten haben die Gitterwege die Form einer Verknüpfung <math>((x,y)) * p</math>, wobei <math>p</math> ein selbstmeidender Gitterweg von <math>(u,v)</math> nach <math>(m,n)</math> mit Verbotsmenge <math>V \cup \{(x,y)\}</math> ist und <math>(u,v)</math> die Form <math>(x \pm 1,y)</math> oder <math>(x,y\pm 1)</math> besitzt.

Höhere Dimensionen

Es stellt sich im Anschluss die Frage, wieviele selbstmeidende Gitterwege es in einem dreidimensionalen Gitter <math>[0,m] \times [0,n] \times [0,k]</math> gibt, die von <math>(0,0,0)</math> nach <math>(m,n,k)</math> laufen. Für <math>m=n=k=2</math> gibt es zum Beispiel <math>2\,459\,352</math> Stück. Hier ist einer davon:
 
<math>\usetikzlibrary{calc}\begin{tikzpicture}[scale=1.2,line width=0.2ex]
\def\xdim{1}
\def\ydim{1}
\def\xadd{0.6}
\def\yadd{0.4}
\coordinate (A00) at (0,0);
\coordinate (A10) at (\xdim,0);
\coordinate (A20) at (2*\xdim,0);
\coordinate (A01) at (0,\ydim);
\coordinate (A11) at (\xdim,\ydim);
\coordinate (A21) at (2*\xdim,\ydim);
\coordinate (A02) at (0,2*\ydim);
\coordinate (A12) at (\xdim,2*\ydim);
\coordinate (A22) at (2*\xdim,2*\ydim);
\draw [lightgray] (A00) -- (A10) -- (A20);
\draw [lightgray] (A01) -- (A11) -- (A21);
\draw [lightgray] (A02) -- (A12) -- (A22);
\draw [lightgray] (A00) -- (A01) -- (A02);
\draw [lightgray] (A10) -- (A11) -- (A12);
\draw [lightgray] (A20) -- (A21) -- (A22);
\coordinate (B00) at (\xadd+0,\yadd+0);
\coordinate (B10) at (\xadd+\xdim,\yadd+0);
\coordinate (B20) at (\xadd+2*\xdim,\yadd+0);
\coordinate (B01) at (\xadd+0,\yadd+\ydim);
\coordinate (B11) at (\xadd+\xdim,\yadd+\ydim);
\coordinate (B21) at (\xadd+2*\xdim,\yadd+\ydim);
\coordinate (B02) at (\xadd+0,\yadd+2*\ydim);
\coordinate (B12) at (\xadd+\xdim,\yadd+2*\ydim);
\coordinate (B22) at (\xadd+2*\xdim,\yadd+2*\ydim);
\draw [lightgray] (B00) -- (B10) -- (B20);
\draw [lightgray] (B01) -- (B11) -- (B21);
\draw [lightgray] (B02) -- (B12) -- (B22);
\draw [lightgray] (B00) -- (B01) -- (B02);
\draw [lightgray] (B10) -- (B11) -- (B12);
\draw [lightgray] (B20) -- (B21) -- (B22);
\coordinate (C00) at (2*\xadd+0,2*\yadd+0);
\coordinate (C10) at (2*\xadd+\xdim,2*\yadd+0);
\coordinate (C20) at (2*\xadd+2*\xdim,2*\yadd+0);
\coordinate (C01) at (2*\xadd+0,2*\yadd+\ydim);
\coordinate (C11) at (2*\xadd+\xdim,2*\yadd+\ydim);
\coordinate (C21) at (2*\xadd+2*\xdim,2*\yadd+\ydim);
\coordinate (C02) at (2*\xadd+0,2*\yadd+2*\ydim);
\coordinate (C12) at (2*\xadd+\xdim,2*\yadd+2*\ydim);
\coordinate (C22) at (2*\xadd+2*\xdim,2*\yadd+2*\ydim);
\draw [lightgray] (C00) -- (C10) -- (C20);
\draw [lightgray] (C01) -- (C11) -- (C21);
\draw [lightgray] (C02) -- (C12) -- (C22);
\draw [lightgray] (C00) -- (C01) -- (C02);
\draw [lightgray] (C10) -- (C11) -- (C12);
\draw [lightgray] (C20) -- (C21) -- (C22);
\draw [lightgray] (A00) -- (B00) -- (C00);
\draw [lightgray] (A10) -- (B10) -- (C10);
\draw [lightgray] (A20) -- (B20) -- (C20);
\draw [lightgray] (A01) -- (B01) -- (C01);
\draw [lightgray] (A11) -- (B11) -- (C11);
\draw [lightgray] (A21) -- (B21) -- (C21);
\draw [lightgray] (A02) -- (B02) -- (C02);
\draw [lightgray] (A12) -- (B12) -- (C12);
\draw [lightgray] (A22) -- (B22) -- (C22);
\draw [black!50!blue, rounded corners=0.3ex] (A00) -- (A01) -- (B01) -- (B11) -- ($(B11)!.5!(A11)$);
\draw [white, line width=1ex] ($(A11)!.35!(A12)$) --  ($(A11)!.45!(A12)$);
\draw [black!50!blue, rounded corners=0.3ex] ($(C12)!.5!(C02)$) -- (C02) -- (C01) -- (C11) -- (C10) -- (B10) -- (A10) -- ($(A10)!.5!(A20)$);
\draw [white, line width=1ex] ($(A12)!.15!(A22)$) -- ($(A12)!.25!(A22)$);
\draw [white, line width=1ex] ($(B21)!.55!(A21)$) -- ($(B21)!.8!(A21)$);
\draw [white, line width=1ex] ($(A21)!.25!(A20)$) -- ($(A21)!.4!(A20)$);
\draw [black!50!blue, rounded corners=0.3ex] ($(A10)!.5!(A20)$) -- (A20) -- (A21) -- (B21) -- (B20) -- (C20) -- (C21) -- (C22);
\draw [black!50!blue, rounded corners=0.3ex] ($(B11)!.5!(A11)$) -- (A11) -- (A12) -- (A22) -- (B22) -- (B12) -- (C12) -- ($(C12)!.5!(C02)$);
\end{tikzpicture}</math>
 
Tatsächlich funktioniert hier bei festen <math>m,n</math> die Transfer-Matrix-Methode ebenfalls, nur ist der Graph – hier sogar ein Multigraph – schwieriger zu definieren bzw. programmieren. Die erzeugende Funktion für die Anzahl der selbstmeidenden <math>1 {\times} 1 {\times} k</math>-Gitterwege ist z.B.
 
<math>\displaystyle\frac{4z^7-12z^6+12z^5+12z^4-42z^3+14z^2+6z-2}{-12z^8+24z^7-29z^6-68z^5+89z^4-16z^3-23z^2+12z-1}.</math>


Literatur (Auswahl)
• H. L. Abbott, D. Hanson, A lattice path problem, pdf
• K. L. Collins, L. B. Krompart, The number of Hamiltonian paths in a rectangular grid, pdf
• F. Faase, On the number of specific spanning subgraphs of the graphs <math>G \times P_n</math>, pdf
• F. Faase, Counting Hamiltonian cycles in product graphs, link
• H. Marxen, Self-Avoiding Walks of a Rook on a Chessboard, link
• R. P. Stanley, Enumerative combinatorics. Vol. I, pdf

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 307
 
Aufrufstatistik des Artikels
Insgesamt 4 externe Besuche zwischen 2017.09 und 2017.09 [Anzeigen]
DomainAnzahlProz
http://matheplanet.com4100%100 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 3 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2017.09.20-2017.09.23 (3x)https://www.google.de/

[Seitenanfang]

" Mathematik: Kombinatorik im Spätsommer: Hamiltonsche Gitterwege" | 0 Kommentare
 
Für den Inhalt der Kommentare sind die Verfasser verantwortlich.

 
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]