diamante azteco

diamante azteco (Reindirizzato dal teorema del diamante azteco) Vai alla navigazione Vai alla ricerca Un diamante azteco dell'ordine 4 In matematica combinatoria, un diamante azteco di ordine n è costituito da tutti i quadrati di un reticolo quadrato i cui centri (X,y) soddisfare |X| + |y| ≤ n. Qui n è un numero intero fisso, e il reticolo quadrato è costituito da quadrati unitari con l'origine come vertice di 4 di loro, in modo che sia x che y siano semiinteri.[1] Uno di 1024 possibili tessere domino di un ordine 4 Diamante azteco Una tessera domino di un diamante azteco di ordine 50, scelto uniformemente a caso. I quattro angoli del diamante al di fuori dell'area approssimativamente circolare sono "congelato".

Il teorema del diamante azteco afferma che il numero di tessere domino del diamante azteco di ordine n è 2n(n+1)/2.[2] Il teorema del Circolo Polare Artico afferma che una piastrellatura casuale di un grande diamante azteco tende a rimanere congelato al di fuori di un certo cerchio.[3] È comune colorare le piastrelle nel modo seguente. Per prima cosa considera una colorazione a scacchiera del diamante. Ogni tessera coprirà esattamente un quadrato nero. Piastrelle verticali in cui il quadrato superiore copre un quadrato nero, è colorato in un colore, e le altre tessere verticali in un secondo. Analogamente per le piastrelle orizzontali.

Knuth ha anche definito i diamanti aztechi dell'ordine n + 1/2.[4] Sono identici ai poliomini associati ai numeri quadrati centrati.

Contenuti 1 Percorsi non intersecanti 2 Altri problemi di piastrellatura 3 Generazione di tassellature valide 4 Riferimenti 5 Collegamenti esterni Percorsi non intersecanti Qualcosa di molto utile per contare le tassellature è osservare i percorsi non intersecanti attraverso il corrispondente grafo orientato. Se definiamo i nostri movimenti attraverso una piastrellatura (piastrellatura domino) essere (1,1) quando siamo sul fondo di una piastrellatura verticale (1,0) dove siamo alla fine di una piastrellatura orizzontale (1,-1) quando siamo in cima a una piastrellatura verticale Allora attraverso qualsiasi piastrellatura possiamo avere questi percorsi dalle nostre sorgenti ai nostri pozzi. Questi movimenti sono simili ai percorsi di Schröder. Per esempio, considera un diamante azteco di ordine 2, e dopo aver disegnato il suo grafo orientato possiamo etichettare le sue sorgenti e pozzi. {stile di visualizzazione a_{1},un_{2}} sono le nostre fonti e {stile di visualizzazione b_{1},b_{2}} sono i nostri lavandini. Sul suo grafico diretto, possiamo tracciare un percorso da {stile di visualizzazione a_{io}} a {stile di visualizzazione b_{j}} , questo ci dà una matrice di percorso, {stile di visualizzazione P_{2}} , {stile di visualizzazione P_{2}={inizio{bmatrice}un_{1}b_{1}&a_{2}b_{1}\un_{1}b_{2}&a_{2}b_{2}\fine{bmatrice}}={inizio{bmatrice}6&2\2&2\end{bmatrice}}} dove {stile di visualizzazione a_{io}b_{j}=} tutti i percorsi da {stile di visualizzazione a_{io}} a {stile di visualizzazione b_{j}} . Il numero di tassellature per l'ordine 2 ghiaccialo {stile di visualizzazione (P_{2})=12-4=8=2^{2(2+1)/2}} Secondo Lindstrom-Gessel-Viennot, se lasciamo che S sia l'insieme di tutte le nostre fonti e T sia l'insieme di tutti i nostri pozzi del nostro grafo orientato allora det {stile di visualizzazione (P_{n})=} numero di percorsi non intersecanti da S a T.[5] Considerando il grafico diretto del diamante azteco, è stato anche dimostrato da Eu e Fu che i percorsi di Schröder e le piastrellature del diamante azteco sono in biiezione.[6] Quindi, trovare il determinante della matrice dei cammini, {stile di visualizzazione P_{n}} , ci darà il numero di tassellature per il Diamante azteco dell'ordine n.

Un altro modo per determinare il numero di tassellature di un diamante azteco è utilizzare matrici Hankel di numeri di Schröder grandi e piccoli,[6] usando ancora il metodo di Lindstrom-Gessel-Viennot.[5] Trovare il determinante di queste matrici ci dà il numero di cammini non intersecanti di numeri di Schröder piccoli e grandi, che è in biiezione con le piastrellature. I piccoli numeri di Schröder sono {stile di visualizzazione {1,1,3,11,45,cdot }={si_{0},si_{1},si_{2},si_{3},si_{4},cdot }} e i grandi numeri di Schröder lo sono {stile di visualizzazione {1,2,6,22,90,cdot }={X_{0},X_{1},X_{2},X_{3},X_{4},cdot }} , e in generale lo saranno le nostre due matrici di Hankel {stile di visualizzazione H_{n}={inizio{bmatrice}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}\fine{bmatrice}}} e {stile di visualizzazione G_{n}={inizio{bmatrice}si_{1}&y_{2}&cdots &y_{n}\si_{2}&y_{3}&cdots &y_{n+1}\vdots &vdots &&vdots \y_{n}&y_{n+1}&cdots &y_{2n-1}\fine{bmatrice}}} dove {stile di visualizzazione (H_{n})=2^{2(n+1)/2}} e quello {stile di visualizzazione (G_{n})=2^{2(n-1)/2}} dove {stile di visualizzazione ngeq 1} (È anche vero che det {stile di visualizzazione (H_{n}^{0})=2^{2(n-1)/2}} dove questa è la matrice di Hankel come {stile di visualizzazione H_{n}} , ma iniziato con {stile di visualizzazione x_{0}} invece di {stile di visualizzazione x_{1}} per la prima voce della matrice nell'angolo in alto a sinistra).

Altri problemi di piastrellatura Considera la forma, {stile di visualizzazione 2 volte n} bloccare, e possiamo porre la stessa domanda del Diamante azteco di ordine n. Come questo è stato dimostrato in molti documenti, faremo riferimento a.[7] Lasciare il {stile di visualizzazione 2 volte n} la forma del blocco deve essere indicata con {stile di visualizzazione B_{n}} , allora si può vedere il numero di tassellature di {stile di visualizzazione B_{n}=F_{n}} dove {stile di visualizzazione F_{n}} è poi {stile di visualizzazione ^{th}} Numero di Fibonacci e {stile di visualizzazione ngeq 0} . Resta inteso che {stile di visualizzazione B_{0}} è un {stile di visualizzazione 2 volte 0} forma che può essere solo piastrellata 1 modo, nessun modo. Usando l'induzione, ritenere {stile di visualizzazione B_{1}} e questo è giusto {stile di visualizzazione 2 volte 1} tessera domino dove c'è solo {stile di visualizzazione F_{1}=1} piastrellatura. Assumendo il numero di tassellature per {stile di visualizzazione B_{n}=F_{n}} , allora consideriamo {stile di visualizzazione B_{n+1}} . Concentrandosi su come possiamo iniziare la nostra piastrellatura, abbiamo due casi. Possiamo iniziare con la nostra prima tessera verticale, il che significa che ci rimane {stile di visualizzazione B_{n}} che ha {stile di visualizzazione F_{n}} tassellature diverse. L'altro modo in cui possiamo iniziare la nostra piastrellatura è posare due piastrelle orizzontali una sopra l'altra, che ci lascia {stile di visualizzazione B_{n-1}} che ha {stile di visualizzazione F_{n-1}} tassellature diverse. Sommando i due insieme, il numero di tassellature per {stile di visualizzazione B_{n+1}=F_{n}+F_{n-1}=F_{n+1}} .[7] Generare tassellature valide Trovare tassellature valide del diamante azteco comporta la soluzione del sottostante problema di copertura dell'insieme. Permettere {stile di visualizzazione D={d_{1},d_{2},punti ,d_{n}}} essere l'insieme di domino 2X1 in cui ogni domino in D può essere posizionato all'interno del diamante (senza oltrepassarne i confini) quando non sono presenti altri domino. Permettere {stile di visualizzazione S={S_{1},S_{2},punti ,S_{m}}} essere l'insieme di quadrati 1X1 che si trovano all'interno del diamante che deve essere coperto. Si possono trovare due domino all'interno di D per coprire qualsiasi casella di confine all'interno di S, e si possono trovare quattro domino all'interno di D per coprire qualsiasi quadrato non di confine all'interno di S.

Definire {stile di visualizzazione c(S_{io})sottoinsieme D} essere l'insieme delle tessere del domino che ricoprono il quadrato {stile di visualizzazione s_{io}} , e lascia {stile di visualizzazione x_{io}} essere una variabile indicatore tale che {stile di visualizzazione x_{io}=1} se la {stile di visualizzazione i^{th}} domino è utilizzato nella piastrellatura, e 0 altrimenti. Con queste definizioni, il compito di piastrellare il diamante azteco può essere ridotto a un problema di soddisfazione dei vincoli formulato come un programma intero binario: {stile di visualizzazione somma minima _{1leq ileq m}0cdot x_{io}} Soggetto a: {somma dello stile di visualizzazione _{iin c(S_{io})}X_{io}=1,} per {displaystyle 1leq ileq m} , e {stile di visualizzazione x_{io}in {0,1}} .

Il {stile di visualizzazione i^{th}} vincolo garantire quel quadrato {stile di visualizzazione s_{io}} sarà coperto da un'unica tessera, e la raccolta di {stile di visualizzazione m} vincoli assicura che ogni quadrato sarà coperto (nessun foro nel rivestimento). Questa formulazione può essere risolta con pacchetti di programmazione interi standard. Ulteriori vincoli possono essere costruiti per forzare il posizionamento di particolari domino, assicurarsi che venga utilizzato un numero minimo di tessere del domino orientate orizzontalmente o verticalmente, o generare tassellature distinte.

Un approccio alternativo consiste nell'applicare l'algoritmo X di Knuth per enumerare tassellature valide per il problema.

Riferimenti ^ Stanley, Riccardo P. (1999), Combinatoria enumerativa. vol. 2, Studi Cambridge in matematica avanzata, vol. 62, Cambridge University Press, ISBN 978-0-521-56069-6, SIG 1676282, archiviato dall'originale in poi 2008-10-05, recuperato 2008-11-18 ^ Elkies, Noam; Kuperberg, Greg; Larsen, Michael; Tappo, Giacomo (1992), "Matrici a segno alternato e tassellature domino. io", Giornale di combinatoria algebrica, 1 (2): 111–132, doi:10.1023/UN:1022420103267, ISSN 0925-9899, SIG 1226347 ^ Jockusch, William; Tappo, Giacomo; Breve, Peter (1998), Piastrellature casuali del domino e teorema del circolo polare artico, arXiv:matematica/9801068, Bibcode:1998matematica......1068J ^ Knuth, Donald E. (2019), "Prefascicolo 5c (sezione 7.2.2.1, Collegamenti danzanti)", L'arte della programmazione informatica, vol. 4, p. 93 ^ Salta su: a b Majumdar, Diptapriya. "Algoritmi grafici avanzati: Lemma di Gessel Viennot" (PDF). Archiviato (PDF) dall'originale in poi 2018-03-05. Recuperato 22 aprile 2014. ^ Salta su: ab me, Sen Peng; Fu, Tung Shan (2005). "Una semplice prova del diamante azteco". Elettrone. J. Combina., 12:Documento di ricerca. L'Electroninc Journal of Combinatorics: 0412041. CiteSeerX 10.1.1.214.7065. ^ Salta su: a b Martinez, Megan; Kanoff, Ilene. "Domino Tiling e i numeri di Fibonacci" (PDF). Archiviato (PDF) dall'originale in poi 2016-05-03. Recuperato 2 Marzo 2018. Weissstein esterno sinistro, Eric W. "Diamante azteco". Math World. Categorie: Combinatoria enumerativa