Aztekisk diamant

En aztekisk diamant av ordning 4

I kombinatorisk matematik består en aztekisk diamant av ordningen n av alla kvadrater i ett kvadratiskt gitter vars centrum ( x , y ) uppfyller | x | + | y | ≤ n . Här n ett fast heltal, och kvadratgittret består av enhetskvadrater med origo som en vertex av 4 av dem, så att både x och y är halvheltal .

En av 1024 möjliga dominoplattor av en order på 4 Aztec-diamanter

En dominoplatta av en aztekisk diamant på order-50, vald enhetligt slumpmässigt. De fyra hörnen av diamanten utanför det ungefär cirkulära området är "frysta".

Den aztekiska diamantsatsen säger att antalet dominoplattor av den aztekiska diamanten av ordning n är 2 ^{n ( n +1)/2} . Polcirkelsatsen säger att en slumpmässig beläggning av en stor aztekisk diamant tenderar att frysas utanför en viss cirkel .

Det är vanligt att färga plattorna på följande sätt. Överväg först en schackbrädefärgning av diamanten. Varje bricka kommer att täcka exakt en svart ruta. Vertikala brickor där den översta rutan täcker en svart fyrkant, färgas i en färg och de andra vertikala brickorna i en andra. Likadant för horisontella plattor.

Knuth har också definierat aztekiska diamanter av ordningen n + 1/2. De är identiska med polyominoerna som är associerade med de centrerade kvadrattalen .

Icke-korsande stigar

Något som är mycket användbart för att räkna plattsättningar är att titta på de icke-korsande vägarna genom dess motsvarande riktade graf . Om vi ​​definierar våra rörelser genom en plattsättning ( domino plattsättning ) att vara

• (1,1) när vi är botten av en vertikal plattsättning
• (1,0) där vi är slutet av en horisontell plattsättning
• (1,-1) när vi är överst i en vertikal plattsättning

Sedan genom vilken kakel som helst kan vi få dessa vägar från våra källor till våra diskbänkar . Dessa rörelser liknar Schröders stigar . Tänk till exempel på en aztekisk diamant av ordning 2, och efter att ha ritat dess riktade graf kan vi märka dess källor och sänkor . $a_{1},a_{2}$ är våra källor och $b_{1},b_{2}$ är våra sänkor. På dess riktade graf kan vi rita en väg från $a_{i}$ till $b_{j}$ , detta ger oss en vägmatris , $P_{2}$ ,

$P_{2}={\begin{bmatrix}a_{1}b_{1} &a_{2}b_{1}\\a_{1}b_{2}&a_{2}b_{2}\\\end{bmatrix}}={\begin{bmatrix}6&2\\2&2\\\end{ bmatrix}}$

där $a_{i}b_{j}=$ alla vägar från $a_{i}$ till $b_{j}$ . Antalet plattsättningar för order 2 är

det $(P_{2})=12-4=8=2^{2(2+1)/2}$

Enligt Lindstrom-Gessel-Viennot , om vi låter S vara mängden av alla våra källor och T vara mängden av alla våra sänkor av vår riktade graf då

det $(P_{n})=$ antal icke-korsande vägar från S till T.

Med tanke på den riktade grafen för den aztekiska diamanten, har det också visat sig av Eu och Fu att Schröders banor och plattsättningar av den aztekiska diamanten är i bijektion . Att hitta determinanten för vägmatrisen , $P_{n}$ , kommer därför att ge oss antalet tilings för den aztekiska diamanten av ordningen n .

Ett annat sätt att bestämma antalet beläggningar av en aztekisk diamant är att använda Hankel-matriser med stora och små Schröder-tal , med metoden från Lindstrom-Gessel-Viennot igen. Att hitta determinanten för dessa matriser ger oss antalet icke-korsande banor av små och stora Schröder-tal , som är i bijektion med plattsättningarna. De små Schrödertalen är $\{1,1,3,11,45 ,\cdots \}=\{y_{0},y_{1},y_{2},y_{3},y_{4},\cdots \}$ och de stora Schrödertalen är ${\displaystyle \{1,2,6,22,90,\cdots \}=\{x_{0 },x_{1},x_{2},x_{3},x_{4},\cdots \}} ,$ och i allmänhet kommer våra två Hankel-matriser att vara

$H_{n}={\begin{bmatrix} x_{1}&x_{2}&\cdots &x_{n}\\x_{2}&x_{3}&\cdots &x_{n+1}\\\vdots &\vdots &&\vdots \\x_{n} &x_{n+1}&\cdots &x_{2n-1}\\\end{bmatrix}}$ och $G_{n}={\begin{bmatrix}y_{1}&y_{2}&\cdots &y_{n}\\y_{2}&y_{3} &\cdots &y_{n+1}\\\vdots &\vdots &&\vdots \\y_{n}&y_{n+1}&\cdots &y_{2n-1}\\\end{bmatrix}}$

där det $(H_{n})=2^{n(n+1)/2}$ och det $(G_{n})=2^{n(n-1)/2}$ där $n\geq 1$ (Det är också sant att det $(H_{n}^{0})=2^{n(n-1)/2}$ där detta är Hankel-matrisen som $H_ {n}$ , men började med $x_{0}$ istället för $x_{1}$ för den första posten i matrisen i det övre vänstra hörnet).

Andra kakelproblem

Tänk på formen, $2\times n$ block, och vi kan ställa samma fråga som för den aztekiska diamanten av ordningen n . Eftersom detta har bevisats i många tidningar kommer vi att hänvisa till. Om du låter $2\times n$ betecknas med $B_{n}$ , då kan den ses

Antalet plattsättningar av $B_{n}=F_{n}$

där $F_{n}$ är n $^{th}$ Fibonacci-talet och $n\geq 0$ . Det är underförstått att $B_{0}$ är en $2\x 0$ form som bara kan sida vid sida 1 sätt, inga sätt. Använd induktion och överväg $B_{1}$ och det är bara $2\times 1$ dominobricka där det bara finns $F_{1}=1$ sida vid sida . Om vi ​​antar antalet plattsättningar för ${\displaystyle B_{n}=F_{n}} ,$ då betraktar vi $B_{n+1}$ . Med fokus på hur vi kan börja vår plattsättning har vi två fall. Vi kan börja med att vår första bricka är vertikal, vilket betyder att vi har $B_{n}$ som har $F_{n}$ olika plattsättningar. Det andra sättet vi kan börja vår plattsättning är genom att lägga två horisontella plattor ovanpå varandra, vilket lämnar oss med $B_{n-1}$ som har $F_{n -1}$ olika plattsättningar. Genom att addera de två tillsammans, blir antalet plattsättningar för $B_{n+1}=F_{n}+F_{n-1}= F_{n+1}$ .

Generera giltiga plattor

Att hitta giltiga plattsättningar av den aztekiska diamanten innebär lösningen av det underliggande sättnings-täckningsproblemet . Låt $D=\{d_{1},d_{2},\dots ,d_{n}\}$ vara uppsättningen av 2X1 dominobrickor där varje domino i D kan placeras inom diamanten (utan att korsa dess gränser) när inga andra dominobrickor finns. Låt $S=\{s_{1},s_{2},\dots ,s_{m}\}$ vara uppsättningen av 1X1 rutor som ligger inom diamanten som måste täckas. Två dominobrickor inom D kan hittas för att täcka vilken gränsruta som helst inom S, och fyra dominobrickor inom D kan hittas för att täcka alla icke-gränskanter inom S.

Definiera $c(s_{i})\subset D$ för att vara den uppsättning dominobrickor som täcker kvadraten $s_{i}$ , och låt $x_ {i}$ vara en indikatorvariabel så att $x_{i}=1$ om $i^{th}$ domino används i plattsättningen, och 0 annars. Med dessa definitioner kan uppgiften att lägga till den aztekiska diamanten reduceras till ett problem med begränsningstillfredsställelse formulerat som ett binärt heltalsprogram:

$\min \summa _{1\leq i\leq m}0\cdot x_{i}$

Med förbehåll för: $\sum _{i\in c(s_{i})}x_{i}=1,$ för ${\ displaystyle 1\leq i\leq m}$ , och $x_{i}\in \{0,1\}$ .

Den ${\displaystyle i^{th}}-$ begränsningen garanterar att kvadrat $s_{i}$ kommer att täckas av en enda ruta, och samlingen av $m$ -begränsningar säkerställer att varje kvadrat kommer att täckas (inga hål i täckningen). Denna formulering kan lösas med vanliga heltalsprogrammeringspaket. Ytterligare begränsningar kan konstrueras för att tvinga fram placering av speciella dominobrickor, se till att ett minimum antal horisontella eller vertikalt orienterade dominobrickor används, eller generera distinkta plattor.

Ett alternativt tillvägagångssätt är att använda Knuths Algorithm X för att räkna upp giltiga plattsättningar för problemet.

externa länkar

• Weisstein, Eric W. "Aztec Diamond" . MathWorld .