Ацтекский бриллиант

В комбинаторике разбиений ацтекским бриллиантом (или ацтекским диамантом) порядка $n$ называется фигура, состоящая из клеток, наведённых плоской целочисленной решёткой, центры которых (точки с полуцелыми координатами) удовлетворяют неравенству $|x|+|y|\leq n$ .

Эти фигуры изучаются в связи со свойствами множества их замощений домино (разбиений на плитки размером $1\times 2$ клеток).

История

Ацтекский бриллиант впервые упомянут в работе Элкиса, Куперберга, Ларсена и Проппа^[1]^[2].

Теорема о полярном круге (см. ниже) доказана У. Джокушем, Дж. Проппом и П. Шором в 1995 году.^[3]

Связанные понятия

Ранг разбиения

Процесс вычисления функции высоты одной из точек разбиения ацтекского бриллианта порядка 3

Последовательность элементарных поворотов, приводящих к горизонтальному замощению, для разбиения ранга 4

Рангом разбиения $T$ ацтекского бриллианта на домино называется минимальное количество поворотов двух доминошек, имеющих общую длинную грань, вокруг центра их общей грани, необходимое для того, чтобы превратить разбиение в такое, где все плитки лежат горизонтально (такое разбиение, очевидно, существует только одно). Можно доказать, что такое превращение через такие преобразования всегда возможно, так что понятие ранга определено для любого разбиения $T$ .^[2]

Максимальный возможный ранг разбиения ацтекского бриллианта порядка $n$ достигается при разбиении, в котором все плитки ориентированы вертикально. В этом случае ранг равен ${\frac {1}{6}}n(n+1)(2n+1)$ ^[4]

Функция высоты

Для произвольного фиксированного разбиения бриллианта удобно рассматривать функцию высоты. Это функция, определённая на узлах целочисленной решётки, находящихся внутри бриллианта или на его границе, и принимающая целочисленные значения.

Пусть фиксировано некоторое разбиение бриллианта на плитки домино. Рассмотрим раскраску клеток бриллианта в шахматном порядке, в которой верхняя из самых правых клеток - чёрная. На каждой из границ клеток поставим стрелку в таком направлении, чтобы белая клетка была справа от стрелки, а чёрная - слева. Обозначим точку $(-n;0)$ как $v_{0}$ . Рассмотрим любой путь от $v_{0}$ до $v$ , проходящий исключительно по границам разбивающих бриллиант плиток домино. Тогда для точки решётки $v$ функция высоты $H(v)$ будет равна разности количества стрелок на этом пути, лежащих, соответственно, сонаправленно и обратно направленно этому пути.^[2]^[5]

В разных источниках определение функции может различаться на константу, но для приложений это несущественно.

Данное определение оказывается независимо от выбора пути, а зависит только от разбиения.

Стандартная нотация плиток в разбиении

Для упрощения иллюстраций и формулировки доказательств часто используется условное деление всех плиток $1\times 2$ конкретного рассматриваемого замощения на четыре класса.^[6]^[7] Для их описания удобно представить раскраску клеток ацтекского бриллианта по типу шахматной доски такую, что верхняя из двух самых левых клеток - чёрная. Тогда классы определяются так:

N (north - север) - горизонтально ориентированная плитка, у которой левая клетка - чёрная;
S (south - юг) - горизонтально ориентированная плитка, у которой левая клетка - белая;
W (west - запад) - вертикально ориентированная плитка, у которой верхняя клетка - чёрная;
E (east - восток) - вертикально ориентированная плитка, у которой верхняя клетка - белая.

Названия классов, как видно, соответствуют сторонам, в которых находятся клетки при двух тривиальных разбиениях (где каждая горизонталь или вертикаль - прямая линия из последовательных плиток). При иллюстрации бриллианта плитки разных классов иногда изображаются разными цветами.

Теорема о количестве разбиений

Первым рассматриваемым наукой вопросом относительно ацтекского бриллианта было количество возможных разбиений этой фигуры на плитки домино.

Следующая теорема может быть доказана многими способами с привлечением различных математических методов и конструкций - в частности, конденсации Доджсона, знакочередующихся матриц, взвешенных совершенных паросочетаний или чисел и путей Шредера (все четыре перечисленных инструмента относятся к разным возможным доказательствам).

Существует ровно $2^{\frac {n(n+1)}{2}}$ способов разбить ацтекский бриллиант порядка $n$ на плитки размера $1\times 2$ клеток, углы которых лежат в узлах целочисленной решётки.

Ниже мы будем обозначать количество таких разбиений через $AD(n)$ (от английского "aztec diamond")

Доказательство через знакочередующиеся матрицы

При доказательстве через знакочередующиеся матрицы^[англ.] произвольному разбиению ацтекского бриллианта порядка $n$ ставится в соответствие матрица размера $n\times n$ , элементы которой соответствуют целым точкам, сравнимым по модулю 2 и лежащим внутри бриллианта (каждая диагональ воспринимается как строка или столбец матрицы). Если такая точка принадлежит границам двух доминошек, то соответствующий элемент матрицы принимается равным -1, если трём, то 0, если четырём, то 1.

Можно доказать, что определяемые таким образом матрицы всегда будут знакочередующимися. Более того, можно доказать, что конкретную матрицу $A$ можно получить ровно из $2^{N_{+}(A)}$ разбиений, где ${N_{+}(A)}$ - количество единиц в матрице $A$ .

Аналогично, рассматривая не сравнимые по модулю 2 целые точки, лежащие внутри фигуры и на границе, и соответствующие матрицы размера $(n+1)\times (n+1)$ , можно доказать, что любой такой матрице соответствует $2^{N_{-}(A)}$ разбиений, где ${N_{-}(A)}$ - количество минус единиц в матрице $A$ .

В итоге из очевидного для знакочередующихся матриц размера $n\times n$ тождества $N_{+}(A)=N_{-}(A)+n$ и полученного тождества $AD(n)=\sum \limits _{A\in {\mathcal {M}}_{n+1}}{2^{N_{-}(A)}}=\sum \limits _{A\in {\mathcal {M}}_{n}}{2^{N_{+}(A)}}$ (где ${\mathcal {M}}_{n}$ - множество всех знакочередующихся матриц порядка $n$ ) легко получается, что^[8]

AD(n)=2^{n}\sum \limits _{A\in {\mathcal {M}}_{n}}{2^{N_{-}(A)}}=2^{n}AD(n-1)=2^{n+(n-1)}AD(n-2)=\dots =2^{(1+2+\dots +n)}=2^{\frac {n(n+1)}{2}}

Доказательство через паросочетания

При доказательстве через паросочетания рассматривается граф $G_{n}$ , вершины которого соответствуют клеткам ацтекского бриллианта порядка $n$ , а рёбра проходят между вершинами, клетки которых соседствуют по горизонтали или по вертикали. Количество замощений ацтекского бриллианта порядка $n$ равно количеству совершенных паросочетаний в графе $G$ .

В доказательстве для произвольного графа $G=(V,E)$ и функции весов на его рёбрах $\omega :E\to {\mathbb {R} }$ рассматривается его статистическая сумма $Z(G)=\sum \limits _{M}\prod \limits _{e\in M}\omega (e)$ , где суммирование под знаком суммы ведётся по всем возможном совершенным паросочетаниям.

Основой доказательства является лемма, позволяющая вырезать из графа четыре вершины, правильным образом перестроив рёбра и веса рядом с ними, так, что статистическая сумма графа изменится на предсказуемую величину. Это возможно только если удаляемые вершины находятся в особой рёберной конфигурации с некоторыми другими четырьмя вершинами. Чтобы добиться существования большого количества таких конфигураций в рассматриваемом графе, граф $G_{n}$ можно расширить до некоторого графа ${\tilde {G_{n}}}$ , правильным образом утроив вершины так, что количество паросочетаний не изменится.

Веса рёбер графа $G_{n}$ полагаются равными единице (тогда количество паросочетаний равно статистической сумме), так же как и веса графа ${\tilde {G_{n}}}$ , а нетривиальные веса появляются только после применения леммы об удалении вершин. Однако в получившемся после всех возможных удалений вершин графе ${\tilde {G_{n}}}^{*}$ все веса на рёбрах равны либо $1$ , либо ${\frac {1}{2}}$ , причём рёбра с весом $1$ непременно входят в любое паросочетание. Кроме того, ${\tilde {G_{n}}}^{*}$ после отбрасывания рёбер веса $1$ оказывается равным графу $G_{n-1}$ ацтекского бриллианта предыдущего порядка, только с уменьшенным в два раза весом каждого ребра (а в каждом паросочетании участвуют ровно $n(n-1)$ его рёбер). Это позволяет вывести рекуррентную формулу:^[9]

AD(n)=Z(G_{n})=Z({\tilde {G_{n}}})=2^{n^{2}}Z({\tilde {G_{n}}}^{*})=2^{n^{2}}{\frac {Z(G_{n-1})}{2^{n(n-1)}}}=2^{n}Z(G_{n-1})=2^{n}AD(n-1)

Доказательство через числа Шрёдера

Ещё один способ доказательства - взаимо-однозначно сопоставить каждому разбиению ацтекского бриллианта порядка $n$ набор из $n$ непересекающихся путей Шрёдера. Тогда количество возможных разбиений оказывается равным количеству таких наборов.

Для этого достаточно отметить середины вертикальных отрезков нижней левой части границы бриллианта, а далее вести от них линии, каждый раз проводя новый отрезок симметрично относительно центра домино, в котором отрезок находится - горизонтально для горизонтально лежащих плиток и под наклоном для вертикальных плиток. Тогда, если продолжить вне бриллианта каждый путь наклонными линиями до единого уровня, то получится как раз $n$ непересекающихся путей Шрёдера (каждый путь по бриллианту гарантированно закончится на той же горизонтали, где начался).

Более того, количество $H_{n}$ таких наборов оказывается равным определителю матрицы Ганкеля, составленной из чисел Шрёдера. Рассматривая малые пути Шрёдера (то есть такие, где горизонтальные отрезки не лежат на уровне 0) и количество $G_{n}$ их наборов без пересечений (оно тоже будет выражаться матрицей Ганкеля, но для другой последовательности), можно вывести соотношения $H_{n}=G_{n+1}$ и $H_{n}=2^{n}G_{n}$ , откуда легко получить рекуррентное выражение для $H_{n}$ ^[10]:

AD(n)=H_{n}=2^{n}H_{n-1}=2^{n}AD(n-1)

Доказательство через сдвиг цепочки пересекающихся доминошек

В этом доказательстве из ацтекского бриллианта сначала получают новую фигуру, вырезав четыре клетки. Причём вырезаемые клетки удовлетворяют следующим условиям:

в шахматной раскраске две из них - белые, а две - чёрные;
при вырезании любых чёрной и белой клетки замощений клеток вблизи половины границы определяется однозначно, так что оставшаяся часть представляет собой ацтекский бриллиант порядка $n-1$ ;
при вырезании четырёх клеток однозначно определяется ориентация всех доминошек, касающихся границы, так что оставшаяся часть представляет собой ацтекский бриллиант порядка $n-2$ .

Рассматривая произвольную пару разбиений самого бриллианта и фигуры с четырьмя вырезанными клетками, можно выделить цепочку пересекающихся доминошек, идущую из одной клетки в другую (доминошки из одного и другого разбиения чередуются, любые две соседние доминошки пересекаются по одной клетке). Тогда, поменяв местами части этой цепочки из одного разбиения и из другого, можно получить разбиения двух фигур, у каждой из которых вырезано только по две клетки. Это даёт рекуррентное соотношение^[4]

AD(n)AD(n-2)=2AD(n-1)^{2}

Тем же методом можно вывести короткую формулу для частного случая производящей функции (см. ниже):

AD(n;x)=(1+x)^{\frac {n(n+1)}{2}}

Производящая функция разбиений

Пусть $r(T)$ обозначает ранг разбиения $T$ , а $v(T)$ - половину количества вертикальных плиток в этом разбиении (количество вертикальных плиток всегда чётно, поскольку любая целочисленная горизонтальная линия делит бриллиант на две части с чётным количеством клеток в каждой - значит, каждую такую горизонтальную линую пересекает чётное количество вертикальных плиток).

В работе Элкиса, Куперберга, Ларсена и Проппа рассматривалась производящая функция $AD(n;x,q)=\sum \limits _{T}x^{v(T)}q^{r(T)}$ , где суммирование ведётся по всем возможным разбиениям $T$ ацтекского бриллианта порядка $n$ . В работе было установлено, что $AD(n;x,q)=\prod \limits _{k=0}^{n-1}{{(1+xq^{2k+1})}^{n-k}}$ .

В частности, из этого тождества следует и обычная формула для числа разбиений: $AD(n;1,1)=\prod \limits _{k=0}^{n-1}2^{n-k}=2^{\frac {n(n+1)}{2}}$

Случайные разбиения

Алгоритм генерации случайного разбиения

Известен алгоритм равновероятного выбора случайного разбиения бриллианта заданного размера из всех разбиений такого размера.^[6]^[11]

Для генерации случайного разбиения размера $n$ алгоритм использует заранее сгенерированное случайное разбиение ацтекского бриллианта размера $n-1$ и специальным образом преобразует его со внесением дополнительной случайности. Таким образом, для генерации случайного разбиения размера $n$ нужно последовательно генерировать разбиения размера $1,2,\dots ,n-1,n$ .

Преобразование при переходе от размера $n-1$ к $n$ включает в себя три стадии:

Разрушение. Из разбиения удаляются следующие пары плиток (если таковые присутствуют):
- плитка S, соприкасающаяся нижней гранью с клеткой типа N;
- плитка E, соприкасающаяся правой гранью с плиткой типа W.
Сдвиг. Все оставшиеся плитки сдвигаются на одну клетку согласно своему типу в стандартной нотации - N вверх, S вниз, E вправо, W влево. Предшествующая стадия разрушения гарантирует, что при этом не возникнет наложений одной плитки на другую.
Генерация. Доказано, что в результате двух предыдущих стадий все пустые клетки в области ацтекского бриллианта размера $n$ можно разбить на квадраты размера 2x2. На стадии генерации каждый такой квадрат отдельно заполняется равновероятно либо двумя вертикальными, либо двумя горизонтальными плитками.

Примеры типичных случайных разбиений ацтекских бриллиантов порядков, 10, 15, 25 и 40, раскрашенных соответственно стандартной нотации плиток. Форма области с хаотичным поведением стремится к вписанному кругу.

Теорема о полярном круге

Рассмотрим окружность, вписанную в квадрат, ограничивающий ацтекский бриллиант. Она отрезает от квадрата четыре угла. Оказывается, что у случайно выбираемого замощения с очень большой вероятностью почти все доминошки, попадающие в эти углы, т. е. вне этой окружности, будут "заморожены": в нижнем и верхнем углу они все будут горизонтальными, а в левом и правом — вертикальными. Напротив, поведение замощения внутри этой окружности предсказать нельзя — оно является хаотичным. Все вышесказанное составляет утверждение теоремы о полярном круге, доказанной в 1995 году У. Джокушем, Дж. Проппом и П. Шором^[12]^[3]:

Пусть $p_{n,\varepsilon }$ - вероятность того, что при случайной раскраске бриллианта порядка $n$ все плитки вне увеличенной в $1+\varepsilon$ раз вписанной в этот бриллиант окружности будут расположены детерминированным образом, то есть на верхнем краю все клетки будут из класса N, внизу - из класса S, справа - из класса W, слева - из класса E.

Тогда для любого $\varepsilon >0$ имеет место $p_{n,\varepsilon }\to 1$ при $n\to \infty$ .

Фактически теорема утверждает, что в случайных разбиениях достаточно больших бриллиантов почти вся область вне вписанной окружности будет заполнена ровно, по типу тривиальных разбиений.

Примечания

↑ Смирнов, 2015, с. 5.
↑ ¹ ² ³ Noam Elkies, Greg Kuperberg, Michael Larsen, James Propp. Alternating sign matrices and domino tilings // arXiv:math/9201305. — 1991-05-31. Архивировано 25 марта 2018 года.
↑ ¹ ² William Jockusch, James Propp, Peter Shor. Random Domino Tilings and the Arctic Circle Theorem // arXiv:math/9801068. — 1998-01-13. Архивировано 25 сентября 2017 года.
↑ ¹ ² Кохась, 2008.
↑ Смирнов, 2015.
↑ ¹ ² "", Eric Nordenstam, "", Vol. 15 (2010), Paper no. 3, pages. On the Shuffling Algorithm for Domino Tilings (англ.) // Electronic Journal of Probability. — 2010. — Vol. 15. — P. 75-95. Архивировано 25 марта 2018 года.
↑ Для школьников. 013. Малый ШАД - Асимптотические задачи комбинаторики - Виктор Клепцын (неопр.). YouTube (22 апреля 2015). Дата обращения: 24 марта 2018.
↑ Смирнов, 2015, с. 7-24.
↑ Смирнов, 2015, с. 25-32.
↑ Смирнов, 2015, с. 33-42.
↑ Eric Nordenstam. On the Shuffling Algorithm for Domino Tilings // arXiv:0802.2592 [math]. — 2008-02-19. Архивировано 25 марта 2018 года.
↑ Смирнов, 2015, с. 46.

Литература

Смирнов, Е. Ю. Три взгляда на ацтекский бриллиант. — М.: МЦНМО, 2015. — 48 с. — ISBN 978-5-4439-0279-1.
К. Кохась. Разбиение ацтекских диамантов и квадратов на домино // Записки научных семинаров ПОМИ. — 2008. — Т. 360. — С. 180-230.

Ссылки

Burkard Polster. The ARCTIC CIRCLE THEOREM or Why do physicists play dominoes? (неопр.) Mathologer. YouTube Video (24 декабря 2020). Дата обращения: 28 декабря 2020.

[_2ef55c543b322d55-1] Смирнов, 2015, с. 5.

[Elkies_1991-2] ¹ ² ³ Noam Elkies, Greg Kuperberg, Michael Larsen, James Propp. Alternating sign matrices and domino tilings // arXiv:math/9201305. — 1991-05-31. Архивировано 25 марта 2018 года.

[Arctic_Circle-3] ¹ ² William Jockusch, James Propp, Peter Shor. Random Domino Tilings and the Arctic Circle Theorem // arXiv:math/9801068. — 1998-01-13. Архивировано 25 сентября 2017 года.

[_e2ea3c568f29da3a-4] ¹ ² Кохась, 2008.

[_4e83fdc8dfc4ad20-5] Смирнов, 2015.

[Shuffling-6] ¹ ² "", Eric Nordenstam, "", Vol. 15 (2010), Paper no. 3, pages. On the Shuffling Algorithm for Domino Tilings (англ.) // Electronic Journal of Probability. — 2010. — Vol. 15. — P. 75-95. Архивировано 25 марта 2018 года.

[7] Для школьников. 013. Малый ШАД - Асимптотические задачи комбинаторики - Виктор Клепцын (неопр.). YouTube (22 апреля 2015). Дата обращения: 24 марта 2018.

[_331d22fb996691da-8] Смирнов, 2015, с. 7-24.

[_62501a5b8e0ab08f-9] Смирнов, 2015, с. 25-32.

[_3ae52f649587b665-10] Смирнов, 2015, с. 33-42.

[11] Eric Nordenstam. On the Shuffling Algorithm for Domino Tilings // arXiv:0802.2592 [math]. — 2008-02-19. Архивировано 25 марта 2018 года.

[_fd1937209643058a-12] Смирнов, 2015, с. 46.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]