Мозаика домино

Замощение плитками домино области в

мозаика из плиток домино, которые образованы объединением двух единичных квадратов, соединённых по ребру. Эквивалентно — это паросочетание в графе решётки

, образованное помещением вершины в центр каждого квадрата области и соединением двух вершин, если два соответствующих квадрата смежны.

На популярном математическом

ютуб-канале Mathologer имеется видео на тему разбиений на домино^[1]

.

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

Для некоторых классов мозаик на правильной решётке в двумерных пространствах можно определить функцию высоты, сопоставляющую каждой вершине решётки целое число. Например, нарисуем шахматную доску, фиксируем точку $A_{0}$ с высотой 0, затем для любой вершины имеется путь из $A_{0}$ до неё. На этом пути определим высоту каждой вершины $A_{n+1}$ (то есть вершин квадратов) как высоту предыдущей вершины $A_{n}$ плюс единица, если квадрат справа по пути из $A_{n}$ в $A_{n+1}$ чёрный, и минус единица в противоположном случае.

Более детальную информацию можно найти в статье Кениона и Окунькова ^[2].

Условие высоты Тёрстона

Уильям Пол Тёрстон (1990) описывает тест для определения, имеет ли односвязная область, образованный объединением единичных квадратов на плоскости, замощение плитками домино. Он образует неориентированный граф, который имеет в качестве вершин точки (x,y,z) в трёхмерной целочисленной решётке, и каждая точка которого соединена с четырьмя соседними: если x + y чётно, то (x,y,z) соединяется с (x + 1,y,z + 1), (x − 1,y,z + 1), (x,y + 1,z − 1) и (x,y − 1,z − 1), в то время как в случае нечётности x + y (x,y,z) соединяется с (x + 1,y,z − 1), (x − 1,y,z − 1), (x,y + 1,z + 1) и (x,y − 1,z + 1). Граница области, рассматриваемой как последовательность целых точек на плоскости (x,y), поднимается единственным образом (при выбранной начальной высоте) до пути в этом трёхмерном графике. Необходимым условием существования замощения области плитками домино является замкнутость пути (то есть полученный путь должен образовать простую замкнутую кривую). Однако это условие не является достаточным. Используя более осторожный анализ границы, Тёрстон дал необходимый и достаточный критерий существования замощения области.

Подсчёт замощений области

Число способов замощения $m\times n$ прямоугольника ${\frac {mn}{2}}$ костяшками домино вычислили независимо в 1961 году Темперли с Фишером ^[3] и Кастеляйн,^[4] и это число равно

\prod _{j=1}^{\lceil {\frac {m}{2}}\rceil }\prod _{k=1}^{\lceil {\frac {n}{2}}\rceil }\left(4\cos ^{2}{\frac {\pi j}{m+1}}+4\cos ^{2}{\frac {\pi k}{n+1}}\right).

Если m и n оба нечётны, формула корректно даёт нулевое число возможных мозаик домино.

Специальным случаем является замощение $2\times n$ прямоугольника n костяшками домино — получается последовательность Фибоначчи (последовательность A000045 в OEIS) ^[5].

Другой специальный случай возникает для квадратов с m = n = 0, 2, 4, 6, 8, 10, 12, … — 1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, … (последовательность A004003 в OEIS).

Эти числа можно найти, записав их как Пфаффиан $mn\times mn$ кососимметричной матрицы, собственные значения которого можно найти явно. Эту технику можно применять для многих математических объектов, например, при классическом 2-мерном вычислении функции корреляции димер-димер в статистической механике.

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

числу Деланноя

, которое имеет лишь экспоненциальный, а не супер-экспоненциальный рост по n. Для «уменьшенного ацтекского диаманта» порядка n с только одним длинным средним рядом существует лишь одно замощение.