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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}}}$

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

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

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

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

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

${\displaystyle 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)}$

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

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

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

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

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

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

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

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

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

${\displaystyle AD(n)AD(n-2)=2AD(n-1)^{2}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

Литература

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

Ссылки

• Burkard Polster. (неопр.) Mathologer . YouTube Video (24 декабря 2020). Дата обращения: 28 декабря 2020.