Benutzer:MiaFr/Dominoparkettierung

Dieser Artikel ist im Entstehen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Solltest du über eine Suchmaschine darauf gestoßen sein, bedenke, dass der Text noch unvollständig sein und Fehler oder ungeprüfte Aussagen enthalten kann. Wenn du Fragen zum Thema hast, nimm Kontakt mit dem Autor MiaFr auf.

Eine Dominoparkettierung ist in der Mathematik die Parkettierung einer Fläche mit Dominos, wobei ein $1\times 2$-Rechteck als Domino bezeichnet wird. Dominoparkettierungen sind von hohem Interesse für die Wissenschaft, da sie mathematisch besonders gut zu handhaben sind und vielseitig verwendet werden können, in erster Linie zur Modellierung. Typische Anwendungsgebiete sind dabei Spannbäume und die k-Färbbarkeit von Graphen in der Graphentheorie, Irrfahrten in der Wahrscheinlichkeitstheorie und elektrische Schaltungen. Bei der Untersuchung von Dominoparkettierungen werden sehr häufig Schröder-Pfade verwendet.

Mathematische Herangehensweise

Schröder-Pfade

Es existiert eine Bijektion zwischen Dominoparkettierungen und Schröder-Pfaden. Diese Beziehung wird in vielen Beweisen verwendet.

Schröder-Pfade der Länge 1 und 2.

Definition

Ein großer Schröder-Pfad der Länge $n$ ist ein Pfad in $\mathbb {Z} \times \mathbb {Z}$, der zwischen $(0,0)$ und $(2n,0)$ unter Verwendung von up steps $(1,1)$, down steps $(-1,1)$ und level steps $(2,0)$ ohne die $x$-Achse zu unterschreiten aufgespannt wird. Wenn ein großer Schröder-Pfad keine level steps auf der $x$-Achse besitzt, dann wird er als kleiner Schröder-Pfad bezeichnet.

Parkettierte Fläche

Rechteck

Datei:Dominoparkettierung eines Quadrats.gif

Dominoparkettierung eines Quadrats

Es gibt ein Applet, das die Eins-zu-eins-Beziehung zwischen Dominoparkettierungen und Schröder-Pfaden visualisiert.

Existenz

Die Existenz einer Dominoparkettierung kann mit Hilfe des Färbearguments gezeigt werden. Dabei wird häufig das Schachbrettmuster verwendet.

Anzahl

Es seien $m$ und $n$ natürliche Zahlen und ${\mathcal {R\in \mathbb {N} }}^{2}$ ein $2m\times 2n$-Rechteck. Die Anzahl aller Dominoparkettierungen von ${\mathcal {R}}$ kann durch die Formel

$4^{nm}\prod _{j=1}^{m}\prod _{k=1}^{n}\left(\cos ^{2}{\frac {j\pi }{2m+1}}+\cos ^{2}{\frac {k\pi }{2n+1}}\right)$

berechnet werden.(vgl. dazu )

Aztekischer Diamant

Aztekische Diamanten der Ordnung 1, 2 und 3.

Definition

Ein Aztekischer Diamant der Ordnung $n\in \mathbb {N}$, bezeichnet mit $AD_{n}$, ist die Vereinigung aller Einheitsquadrate, deren Eckpunkte in der Menge

${\overline {AD}}_{n}=\left\{(l,m)\in \mathbb {Z} ^{2}:\vert l\vert +\vert m\vert \leq n+1\right\}$

liegen.

Satz vom Aztekischen Diamant

Sei $n>1$ eine natürliche Zahl. Für die Anzahl $AD\left(n\right)$ der Dominoparkettierungen vom Aztekischen Diamanten der Ordnung $n$ gilt

$AD\left(n\right)=2^{n\left(n+1\right)/2}.$

Beweis

Es wurde ein Beweis mittels Schröder-Pfaden, Schröder-Zahlen und Determinanten von Hankel-Matrizen geführt., , Dominoparkettierungen von Aztekischen Diamanten können zum Beispiel mit Hilfe des Shuffling-Algorithmus erzeugt werden. Ein weiterer Beweis basiert auf Schröder-Pfaden.

Satz vom Arktischen Kreis

Dominoparkettierungen von Aztekischen Diamanten der Ordnung 10, 50 und 250.

Bei Aztekischen Diamanten genügend großer Ordnung haben alle Dominoparkettierungen eine Unterteilung in 5 Bereiche. In der Mitte entsteht ein kreisförmiger Bereich von „ungeordneten” Dominos und in den Ecken bilden sich Bereiche von blockweise angeordneten Dominos. (vgl. [Cohn1996])