Domino obklady - Domino tiling - Wikipedia

Domino obklady čtverce 8 × 8

v geometrie, a domino obklady regionu v Euklidovské letadlo je mozaikování regionu do dominos, tvary vytvořené spojením dvou jednotkové čtverce setkání od okraje k okraji. Ekvivalentně je to perfektní shoda v mřížkový graf vytvořený umístěním vrcholu do středu každého čtverce oblasti a spojením dvou vrcholů, když odpovídají sousedním čtvercům.

Výškové funkce

U některých tříd obkladů na pravidelné mřížce ve dvou rozměrech je možné definovat funkci výšky spojující celé číslo s vrcholy mřížky. Například nakreslete šachovnici, opravte uzel ${ displaystyle A_ {0}}$ s výškou 0, pak pro jakýkoli uzel existuje cesta z ${ displaystyle A_ {0}}$ k tomu. Na této cestě definujte výšku každého uzlu ${ displaystyle A_ {n + 1}}$ (tj. rohy čtverců) jako výška předchozího uzlu ${ displaystyle A_ {n}}$ plus jeden, pokud je čtverec na pravé straně cesty od ${ displaystyle A_ {n}}$ na ${ displaystyle A_ {n + 1}}$ je černá a minus jedna jinak.

Více podrobností naleznete v Kenyon & Okounkov (2005).

Thurstonův výškový stav

William Thurston (1990) popisuje test pro určení, zda má jednoduše připojená oblast, vytvořená jako spojení jednotkových čtverců v rovině, domino obklady. On tvoří neorientovaný graf který má jako své vrcholy body (X,y,z) v trojrozměrném celočíselná mřížka, kde je každý takový bod spojen se čtyřmi sousedy: pokud X + y je sudé, pak (X,y,z) je připojen k (X + 1,y,z + 1), (X − 1,y,z + 1), (X,y + 1,z - 1) a (X,y − 1,z - 1), zatímco pokud X + y je liché, pak (X,y,z) je připojen k (X + 1,y,z − 1), (X − 1,y,z − 1), (X,y + 1,z + 1) a (X,y − 1,z + 1). Hranice oblasti, považovaná za posloupnost celočíselných bodů v (X,y) rovina, jedinečně se zvedne (jakmile je vybrána výchozí výška) na cestu v tomto trojrozměrný graf. Nutnou podmínkou, aby tato oblast mohla být tileable, je to, že tato cesta se musí uzavřít, aby vytvořila jednoduchou uzavřenou křivku ve třech rozměrech, avšak tato podmínka není dostatečná. Pomocí pečlivější analýzy hraniční cesty Thurston stanovil kritérium pro tileabilitu oblasti, které bylo dostatečné a nezbytné.

Počítání obkladů regionů

Domino obklady čtverce 8 × 8 s použitím minimálního počtu párů od dlouhé hrany k dlouhé hraně (1 pár uprostřed). Toto ujednání je také platné Tatami obklad čtverce 8x8, aniž by se ve vnitřním bodě dotýkaly čtyři domino.

Počet způsobů, jak pokrýt ${ displaystyle m krát n}$ obdélník s ${ displaystyle { frac {mn} {2}}}$ domino, počítané nezávisle na Temperley a Fisher (1961) a Kasteleyn (1961), darováno

{ displaystyle prod _ {j = 1} ^ { lceil { frac {m} {2}} rceil} prod _ {k = 1} ^ { lceil { frac {n} {2}} rceil} left (4 cos ^ {2} { frac { pi j} {m + 1}} + 4 cos ^ {2} { frac { pi k} {n + 1}} že jo).}

Když obojí m a n jsou liché, vzorec se správně sníží na nulovou možnou úroveň domino.

Zvláštní případ nastane při obkládání ${ displaystyle 2 krát n}$ obdélník s n domino: sekvence se snižuje na Fibonacciho sekvence (sekvence A000045 v OEIS ) (Klarner & Pollack 1980 ).

Další speciální případ se stane u čtverců s m = n = 0, 2, 4, 6, 8, 10, 12, ... je

1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, ... (sekvence A004003 v OEIS ).

Tato čísla najdete tak, že je napíšete jako Pfaffian z ${ displaystyle mn times mn}$ šikmo symetrická matice jehož vlastní čísla lze najít výslovně. Tuto techniku lze použít v mnoha předmětech souvisejících s matematikou, například při klasickém 2-dimenzionálním výpočtu funkce korektoru dimer-dimer v statistická mechanika.

Počet naklonění oblasti je velmi citlivý na okrajové podmínky a může se dramaticky měnit se zjevně nevýznamnými změnami ve tvaru oblasti. To je ilustrováno počtem naklonění an Aztécký diamant řádu n, kde je počet obkladů 2^(n + 1)n/2. Pokud je toto nahrazeno „rozšířeným aztéckým diamantem“ objednávky n se 3 dlouhými řadami uprostřed spíše než 2, počet naklonění klesne na mnohem menší počet D (n,n), a Delannoyovo číslo, který má spíše pouze exponenciální než superexponenciální růst v n. Za „snížený aztécký diamant“ objednávky n pouze s jednou dlouhou střední řadou je pouze jeden obklad.

Aztécký diamant řádu 4, který má 1024 domino obkladů
Jeden možný obklad

Tatami

Tatami jsou japonské podlahové rohože ve tvaru domina (obdélník 1x2). Používají se k obkládání místností, ale s dalšími pravidly, jak mohou být umístěny. Zejména se obvykle považují za příznivé křižovatky, kde se setkávají tři tatami, zatímco křižovatky, kde se setkávají čtyři tatami, jsou nepříznivé, takže správný obklad tatami je takový, kde se v každém rohu setkávají pouze tři tatamiMathar 2013; Ruskey & Woodcock 2009 ). Problém obkládání nepravidelné místnosti tatami, které splňují tři do rohu, je NP-kompletní (Erickson & Ruskey 2013 ).

Degenerované křivky vyplňování prostoru

Jakákoli konečná sada buněk pravidelná čtvercová mřížka n×n lze indexovat vybraným Křivka vyplňování prostoru to je v souladu se čtverci (které tvoří rekurzivní čtyři rozdělení mřížky čtyřúhelníkové jednotky), s indexem i v rozmezí od 0 do n²-1. Geometricky lze křivku nakreslit jako cestu středem čtvercových buněk. Domino obklady se získají sloučením sousedních buněk. Index j každé domino získá funkce j=podlaha (i ÷ 2) původního indexu mřížky. Nové fraktální křivka je „degenerovaná křivka“, protože je to další fraktál. Příklady:

„Zvrhlý Mortonova křivka vyplňování prostoru "vytváří pravidelné horizontálně orientované domino obklady; křivka souvisí s Geohash indexování, kde se křivka tvaru Z transformuje na křivku tvaru И.

„Zvrhlý Hilbertova křivka vyplňování prostoru "vyrábí neperiodický obkladový systém, míchání horizontálně a vertikálně orientovaných domino, 50% z každé orientace. Degenerovaná Hilbertova křivka je izomorfní s Munkresovým fraktálem.^[1]

Viz také

Gaussovo volné pole, měřítko limitu funkce výšky v obecné situaci (např. uvnitř vepsaného disku velkého aztéckého diamantu)
Zmatený problém s šachovnicí, hádanka týkající se domino obkladů 62 čtverečních podmnožiny šachovnice
Statistická mechanika

Reference

^ Munkresův fraktál je definován v části „Věta 44,1“ faculty.etsu.edu/gardnerr/5357/notes/Munkres-44

Bodini, Olivier; Latapy, Matthieu (2003), "Zobecněné naklonění s výškovými funkcemi" (PDF), Morfismos, 7 (1): 47–68, ISSN 1870-6525, archivovány od originálu dne 2012-02-10, vyvoláno 2008-09-08CS1 maint: unfit url (odkaz)
Erickson, Alejandro; Ruskey, Franku (2013), „Potah Domino tatami je NP-kompletní“, Kombinatorické algoritmy, Poznámky k přednášce ve Výpočtu. Sci., 8288, Springer, Heidelberg, str. 140–149, arXiv:1305.6669, doi:10.1007/978-3-642-45278-9_13, PAN 3162068, S2CID 12738241
Faase, F. (1998), „K počtu konkrétních překlenovacích podgrafů grafů G X P_n“, Ars Combin., 49: 129–154, PAN 1633083
Hock, J. L .; McQuistan, R. B. (1984), „Poznámka o profesní degeneraci dimerů v nasyceném dvourozměrném mřížovém prostoru“, Diskrétní aplikovaná matematika, 8: 101–104, doi:10.1016 / 0166-218X (84) 90083-0, PAN 0739603
Kasteleyn, P. W. (1961), „Statistika dimerů na mřížce. I. Počet dimerních uspořádání na kvadratické mřížce“, Physica, 27 (12): 1209–1225, Bibcode:1961Phy .... 27,1209K, doi:10.1016/0031-8914(61)90063-5
Kenyon, Richard (2000), „The planar dimer model with boundary: a survey“, in Baake, Michael; Moody, Robert V. (eds.), Pokyny v matematických kvazikrystalechSérie monografií CRM, 13, Providence, RI: Americká matematická společnost, str. 307–328, ISBN 0-8218-2629-8, PAN 1798998, Zbl 1026.82007
Kenyon, Richard; Okounkov, Andreji (2005), „Co je ... dimer?“ (PDF), Oznámení Americké matematické společnosti, 52 (3): 342–343, ISSN 0002-9920
Klarner, David; Pollack, Jordan (1980), „Domino obklady obdélníků s pevnou šířkou“, Diskrétní matematika, 32 (1): 45–52, doi:10.1016 / 0012-365X (80) 90098-9, PAN 0588907, Zbl 0444.05009
Mathar, Richard J. (2013), Dlažba obdélníkových oblastí obdélníkovými dlaždicemi: obklady tatami a netatami, arXiv:1311.6135, Bibcode:2013arXiv1311.6135M
Propp, James (2005), „Lambda-determinanty a dominové obklady“, Pokroky v aplikované matematice, 34 (4): 871–879, arXiv:math.CO/0406301, doi:10.1016 / j.aam.2004.06.005, S2CID 15679557
Ruskey, Franku; Woodcock, Jennifer (2009), „Počítání obkladů tatami s pevnou výškou“, Electronic Journal of Combinatorics, 16 (1): R126, doi:10.37236/215, PAN 2558263
Sellers, James A. (2002), „Domino obklady a výrobky z Fibonacciho a Pellova čísla“, Journal of Integer Sequences, 5 (Článek 02.1.2)
Stanley, Richard P. (1985), „Na dimerních krytech obdélníků pevné šířky“, Diskrétní aplikovaná matematika, 12: 81–87, doi:10.1016 / 0166-218x (85) 90042-3, PAN 0798013
Thurston, W. P. (1990), „Conway's tiling groups“, Americký matematický měsíčník, Mathematical Association of America, 97 (8): 757–773, doi:10.2307/2324578, JSTOR 2324578
Wells, David (1997), Slovník tučňáků zvědavých a zajímavých čísel (přepracované vydání), London: Penguin, s. 182, ISBN 0-14-026149-4
Temperley, H. N. V.; Fisher, Michael E. (1961), „Dimerův problém ve statistické mechanice - přesný výsledek“, Filozofický časopis, 6 (68): 1061–1063, doi:10.1080/14786436108243366

[Munkres-1] Munkresův fraktál je definován v části „Věta 44,1“ faculty.etsu.edu/gardnerr/5357/notes/Munkres-44

[1]