Укладка плитки домино

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

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

Более подробную информацию можно найти в работе Кеньона и Окунькова (2005).

Уильям Терстон  (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 ), поднимается однозначно (после выбора начальной высоты) до пути в этом трехмерном графе . Необходимым условием для того, чтобы эта область была мозаичной, является то, что этот путь должен замкнуться, образуя простую замкнутую кривую в трех измерениях, однако этого условия недостаточно. Используя более тщательный анализ граничного пути, Терстон дал критерий мозаичности области, который был как достаточным, так и необходимым.

Число способов покрытия прямоугольника костяшками домино, независимо вычисленное Темперли и Фишером (1961) и Кастелейном (1961), определяется по формуле (последовательность A099390 в OEIS )${\displaystyle m\times n}$${\displaystyle {\frac {mn}{2}}}$$${\displaystyle \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 нечетны, формула корректно сводит к нулю возможные варианты укладки домино.

Особый случай возникает при замощении прямоугольника n костяшками домино: последовательность сводится к последовательности Фибоначчи . ^[1]${\displaystyle 2\times n}$

Другой особый случай имеет место для квадратов с m = n = 0, 2, 4, 6, 8, 10, 12, ...:

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

Число мозаик региона очень чувствительно к граничным условиям и может резко меняться при, казалось бы, незначительных изменениях формы региона. Это иллюстрируется числом мозаик ацтекского ромба порядка n , где число мозаик равно 2 ^{( n  + 1) n /2} . Если его заменить на «расширенный ацтекский ромб» порядка n с 3 длинными рядами в середине вместо 2, число мозаик падает до гораздо меньшего числа D( n , n ), числа Деланнуа , которое имеет только экспоненциальный, а не суперэкспоненциальный рост по n . Для «уменьшенного ацтекского ромба» порядка n только с одним длинным средним рядом существует только одна мозаика.

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

Татами — это японские напольные коврики в форме домино (прямоугольник 1x2). Они используются для облицовки комнат, но с дополнительными правилами о том, как их можно размещать. В частности, обычно стыки, где сходятся три татами, считаются благоприятными, в то время как стыки, где сходятся четыре, считаются неблагоприятными, поэтому правильная укладка татами — это та, где в каждом углу сходятся только три татами. ^[2] Задача об укладке плиткой неправильной комнаты татами, которые сходятся по три в углу, является NP-полной . ^[3]

Существует однозначное соответствие между периодической плиткой домино и конфигурацией основного состояния полностью фрустрированной модели Изинга на двумерной периодической решетке. ^[4] Чтобы увидеть это, отметим, что в основном состоянии каждая пластинка спиновой модели должна содержать ровно одно фрустрированное взаимодействие . Поэтому, если смотреть со стороны дуальной решетки , каждое фрустрированное ребро должно быть «покрыто» прямоугольником 1x2 , таким образом, чтобы прямоугольники охватывали всю решетку и не перекрывались, или плиткой домино дуальной решетки.

• Свободное поле Гаусса , предел масштабирования функции высоты в общей ситуации (например, внутри вписанного диска большого ацтекского алмаза)
• Задача об изуродованной шахматной доске — головоломка, связанная с замощением плитками домино области размером 62 клетки стандартной шахматной доски 8×8 (или шахматной доски ).
• Статистическая механика