Ацтекский бриллиант (Gemytvtnw Qjnllngum)

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

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

История

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

Теорема о полярном круге (см. ниже) доказана У. Джокушем, Дж. Проппом и П. Шором в 1995 году.^[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. На стадии генерации каждый такой квадрат отдельно заполняется равновероятно либо двумя вертикальными, либо двумя горизонтальными плитками.

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

Рассмотрим окружность, вписанную в квадрат, ограничивающий ацтекский бриллиант. Она отрезает от квадрата четыре угла. Оказывается, что у случайно выбираемого замощения с очень большой вероятностью почти все доминошки, попадающие в эти углы, т. е. вне этой окружности, будут "заморожены": в нижнем и верхнем углу они все будут горизонтальными, а в левом и правом — вертикальными. Напротив, поведение замощения внутри этой окружности предсказать нельзя — оно является хаотичным. Все вышесказанное составляет утверждение теоремы о полярном круге, доказанной в 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]