Benutzer:MiaFr/Dominoparkettierung
Eine Dominoparkettierung ist in der Mathematik die Parkettierung einer Fläche mit Dominos, wobei ein -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[1]. Bei der Untersuchung von Dominoparkettierungen werden sehr häufig Schröder-Pfade verwendet.
Mathematische Herangehensweise
[Bearbeiten | Quelltext bearbeiten]Schröder-Pfade
[Bearbeiten | Quelltext bearbeiten]Es existiert eine Bijektion zwischen Dominoparkettierungen und Schröder-Pfaden. Diese Beziehung wird in vielen Beweisen verwendet.
Definition
[Bearbeiten | Quelltext bearbeiten]Ein großer Schröder-Pfad der Länge ist ein Pfad in , der zwischen und unter Verwendung von up steps , down steps und level steps ohne die -Achse zu unterschreiten aufgespannt wird. Wenn ein großer Schröder-Pfad keine level steps auf der -Achse besitzt, dann wird er als kleiner Schröder-Pfad bezeichnet.
Färbung
[Bearbeiten | Quelltext bearbeiten]Parkettierte Fläche
[Bearbeiten | Quelltext bearbeiten]Rechteck
[Bearbeiten | Quelltext bearbeiten]Es gibt ein Applet[2], das die Eins-zu-eins-Beziehung zwischen Dominoparkettierungen und Schröder-Pfaden visualisiert.
Existenz
[Bearbeiten | Quelltext bearbeiten]Die Existenz einer Dominoparkettierung kann mit Hilfe des Färbearguments gezeigt werden. Dabei wird häufig das Schachbrettmuster verwendet.[3]
Anzahl
[Bearbeiten | Quelltext bearbeiten]Es seien und natürliche Zahlen und ein -Rechteck. Die Anzahl aller Dominoparkettierungen von kann durch die Formel
berechnet werden.(vgl. dazu )[4]
Aztekischer Diamant
[Bearbeiten | Quelltext bearbeiten]Definition
[Bearbeiten | Quelltext bearbeiten]Ein Aztekischer Diamant der Ordnung , bezeichnet mit , ist die Vereinigung aller Einheitsquadrate, deren Eckpunkte in der Menge
liegen.
Satz vom Aztekischen Diamant
[Bearbeiten | Quelltext bearbeiten]Sei eine natürliche Zahl. Für die Anzahl der Dominoparkettierungen vom Aztekischen Diamanten der Ordnung gilt
Beweis
[Bearbeiten | Quelltext bearbeiten]Es wurde ein Beweis mittels Schröder-Pfaden, Schröder-Zahlen und Determinanten von Hankel-Matrizen geführt.[5], [6], [7] Dominoparkettierungen von Aztekischen Diamanten können zum Beispiel mit Hilfe des Shuffling-Algorithmus[8] erzeugt werden. Ein weiterer Beweis basiert auf Schröder-Pfaden.[9]
Satz vom Arktischen Kreis
[Bearbeiten | Quelltext bearbeiten]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])
Beweis
[Bearbeiten | Quelltext bearbeiten]Einzelnachweise
[Bearbeiten | Quelltext bearbeiten]- ↑ R. Lyons: A bird's eye view of uniform spanning trees and forests., {Aldous, David (ed.) et al., Microsurveys in discrete probability. DIMACS workshop, Princeton, NJ, USA, June 2--6, 1997. Providence, RI: AMS, American Mathematical Society. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 41, 135-162 (1998).
- ↑ http://www1.informatik.uni-mainz.de/~klenke/simulations/cftp/domino-forward/ForwardDomino.html
- ↑ F. Adrila, R. P. Stanley: Tilings., 2005
- ↑ F. Adrila, R. P. Stanley: Tilings., 2005
- ↑ V. Wiechert, K. Dannowski: Tilings-Exact Enumeration, 2010
- ↑ Sen-Peng Eu and Tung-Shan Fu: A Simple Proof of the Aztec Diamond Theorem.In: Electr. J. Comb., Nr. 8, 2005, (http://www.combinatorics.org/Volume_12/Abstracts/v12i1r18.html)
- ↑ Brualdi, Richard A.,Kirkland, Stephen: Aztec diamonds and digraphs, and Hankel determinants of Schröder numbers. In:J. Comb. Theory Ser. B, Nr. 94, 2005, S.334-351 (http://dl.acm.org/citation.cfm id=1176556.1176563)
- ↑ http://halcanary.org/mathapplets/
- ↑ B. J. Fleming, P. J. Forrester: Interlaced particle systems and tilings of the Aztec diamond, 2010, (http://www.citebase.org/abstract?id=oai:arXiv.org:1004.0474)