Benutzer:MiaFr/Dominoparkettierung

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.

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

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.

Parkettierte Fläche

[Bearbeiten | Quelltext bearbeiten]
Datei:Dominoparkettierung eines Quadrats.gif
Dominoparkettierung eines Quadrats

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

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

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]
Aztekische Diamanten der Ordnung 1, 2 und 3.

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

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]
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])

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. 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).
  2. http://www1.informatik.uni-mainz.de/~klenke/simulations/cftp/domino-forward/ForwardDomino.html
  3. F. Adrila, R. P. Stanley: Tilings., 2005
  4. F. Adrila, R. P. Stanley: Tilings., 2005
  5. V. Wiechert, K. Dannowski: Tilings-Exact Enumeration, 2010
  6. 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)
  7. 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)
  8. http://halcanary.org/mathapplets/
  9. 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)