Ацтекский алмаз

Ацтекский алмаз четвертого порядка.

В комбинаторной математике ацтекский алмаз порядка n состоит из всех квадратов квадратной решетки, центры которых ( x , y ) удовлетворяют | х | + | й | ≤ п . Здесь n — фиксированное целое число, а квадратная решетка состоит из единичных квадратов с началом координат в вершине четырех из них, так что и x , и y — полуцелые числа .

Одна из 1024 возможных укладок домино ацтекского ромба 4-го порядка.

Укладка домино из ацтекского алмаза 50-го порядка, выбранная равномерно и случайным образом. Четыре угла ромба за пределами примерно круглой области «заморожены».

Теорема ацтекского ромба утверждает, что количество разбиений домино ацтекского ромба порядка n равно 2. ^{п ( п +1)/2} . Теорема о Полярном круге гласит, что случайная мозаика большого ацтекского алмаза имеет тенденцию замерзать за пределами определенного круга.

Плитку принято раскрашивать следующим образом. Сначала рассмотрим раскраску шахматной доски алмаза. Каждая плитка покрывает ровно один черный квадрат. Вертикальные плитки, где верхний квадрат закрывает черный квадрат. окрашен в один цвет, а остальные вертикальные плитки во второй. Аналогично для горизонтальной плитки.

Кнут также определил ацтекские алмазы порядка n + 1/2. Они идентичны полимино, связанным с центрированными квадратными числами .

Непересекающиеся пути

Для подсчета мозаик очень полезно рассматривать непересекающиеся пути через соответствующий ориентированный граф . Если мы определим наши движения посредством мозаики ( плитки домино ), как

• (1,1) когда мы находимся внизу вертикальной мозаики
• (1,0) где мы — конец горизонтальной мозаики
• (1,-1) когда мы находимся на вершине вертикальной мозаики

Тогда с помощью любого тайла мы можем получить эти пути от наших источников к нашим стокам . Эти движения подобны путям Шредера . Например, рассмотрим ацтекский алмаз 2-го порядка, и после построения его ориентированного графа мы можем обозначить его источники и приемники . $a_{1},a_{2}$ наши источники и $b_{1},b_{2}$ наши раковины. На его ориентированном графе можно провести путь из $a_{i}$ к $b_{j}$, это дает нам матрицу путей , $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}}$

где $a_{i}b_{j}=$ все пути из $a_{i}$ к $b_{j}$. Число плиток для порядка 2 равно

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

Согласно Линдстрему-Гесселю-Вьенно , если мы позволим S быть набором всех наших источников, а T - набором всех наших стоков нашего ориентированного графа, тогда

тот $(P_{n})=$количество непересекающихся путей из S в T.

Рассматривая ориентированный граф ацтекского ромба, Эу и Фу также показали, что пути Шредера и мозаики ацтекского ромба находятся в биекции . Следовательно, найдя определитель матрицы путей , $P_{n}$, даст нам количество плиток ацтекского ромба порядка n .

Другой способ определить количество мозаик ацтекского ромба — использовать матрицы Ганкеля больших и малых чисел Шредера : снова воспользовавшись методом Линдстрема-Гесселя-Вьенно . Нахождение определителя этих матриц дает нам количество непересекающихся путей малых и больших чисел Шредера , которое находится в биекции с мозаиками. Малые Шредера числа $\{1,1,3,11,45,\cdots \}=\{y_{0},y_{1},y_{2},y_{3},y_{4},\cdots \}$ и большие числа Шредера равны $\{1,2,6,22,90,\cdots \}=\{x_{0},x_{1},x_{2},x_{3},x_{4},\cdots \}$, и в общем случае наши две матрицы Ханкеля будут

$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}}$ и $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}}$

где это $(H_{n})=2^{n(n+1)/2}$ и это $(G_{n})=2^{n(n-1)/2}$ где $n\geq 1$ (Правда также, что это $(H_{n}^{0})=2^{n(n-1)/2}$ где это матрица Ханкеля вида $H_{n}$, но началось с $x_{0}$ вместо $x_{1}$ для первой записи матрицы в верхнем левом углу).

Другие проблемы с плиткой

Обратите внимание на форму, $2\times n$ блок, и мы можем задать тот же вопрос, что и для ацтекского алмаза порядка n . Поскольку это доказано во многих работах, мы будем ссылаться на это. Позволяя $2\times n$ форму блока обозначать $B_{n}$, тогда это видно

Количество плиток $B_{n}=F_{n}$

где $F_{n}$ это н $^{th}$ число Фибоначчи и $n\geq 0$. Понятно, что $B_{0}$ это $2\times 0$ форма, которую можно выложить плиткой только в одном направлении, без способов. Используя индукцию , рассмотрим $B_{1}$ и это просто $2\times 1$ плитка домино , где есть только $F_{1}=1$ укладка плитки. Предполагая количество мозаик для $B_{n}=F_{n}$, то мы рассматриваем $B_{n+1}$. Сосредоточившись на том, как мы можем начать мозаику, у нас есть два случая. Мы можем начать с того, что наша первая плитка будет вертикальной, что означает, что у нас останется $B_{n}$ который имеет $F_{n}$ разные плитки. Другой способ начать укладку плитки — положить две горизонтальные плитки друг на друга, в результате чего у нас останется $B_{n-1}$ у которого есть $F_{n-1}$ разные плитки. Сложив эти два числа, получим количество мозаик для $B_{n+1}=F_{n}+F_{n-1}=F_{n+1}$.

Создание действительных мозаик

Поиск допустимых мозаик ацтекского ромба включает в себя решение основной проблемы покрытия множества . Позволять $D=\{d_{1},d_{2},\dots ,d_{n}\}$ — это набор домино 2X1, где каждое домино в D может быть помещено внутри ромба (не пересекая его границы), когда других домино нет. Позволять $S=\{s_{1},s_{2},\dots ,s_{m}\}$ — это набор квадратов 1X1, лежащих внутри ромба, который необходимо покрыть. Можно найти два домино в пределах D, чтобы покрыть любой граничный квадрат в пределах S, а четыре домино в пределах D можно найти, чтобы покрыть любой неграничный квадрат в пределах S.

Определять $c(s_{i})\subset D$ быть набором домино, покрывающих квадрат $s_{i}$, и пусть $x_{i}$ быть индикаторной переменной такой, что $x_{i}=1$ если $i^{th}$ В мозаике используется домино, в противном случае — 0. С помощью этих определений задачу мозаики ацтекского ромба можно свести к задаче удовлетворения ограничений, сформулированной в виде программы двоичных целых чисел:

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

С учетом: $\sum _{i\in c(s_{i})}x_{i}=1,$ для $1\leq i\leq m$, и $x_{i}\in \{0,1\}$.

The $i^{th}$ ограничение гарантирует, что квадрат $s_{i}$ будет покрыта одной плиткой, а коллекция $m$ ограничения гарантируют, что каждый квадрат будет покрыт (без дыр в покрытии). Эту формулировку можно решить с помощью стандартных пакетов целочисленного программирования. Дополнительные ограничения могут быть созданы для принудительного размещения определенных домино, обеспечения использования минимального количества горизонтальных или вертикально ориентированных домино или создания различных мозаик.

Альтернативный подход — применить алгоритм X Кнута для перечисления допустимых мозаик для задачи.

Внешние ссылки

• Вайсштейн, Эрик В. «Ацтекский алмаз» . Математический мир .