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

Укладка домино квадрата 8×8.

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

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

Для некоторых классов мозаик на регулярной двухмерной сетке можно определить функцию высоты, связывающую целое число с вершинами сетки. Например, нарисуйте шахматную доску, зафиксируйте узел $A_{0}$ высотой 0, то для любого узла существует путь из $A_{0}$ к этому. На этом пути определите высоту каждого узла $A_{n+1}$ (т.е. углы квадратов) будут высотой предыдущего узла $A_{n}$ плюс один, если квадрат справа от пути от $A_{n}$ к $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 , у + 1, z + 1) и ( x , y - 1, z + 1). Граница области, рассматриваемая как последовательность целочисленных точек на плоскости ( x , y ), однозначно поднимается (после выбора начальной высоты) до пути в этом трехмерном графе . Необходимым условием для того, чтобы эта область была мозаичной, является то, что этот путь должен замыкаться, образуя простую замкнутую кривую в трех измерениях, однако этого условия недостаточно. Используя более тщательный анализ траектории границы, Терстон дал критерий мозаики региона, который был как достаточным, так и необходимым.

Подсчет мозаик регионов

Укладка домино квадрата 8×8 с использованием минимального количества пар «длинное ребро-длинное ребро» (1 пара в центре). Это расположение также является допустимой мозаикой татами квадрата 8x8, при этом четыре домино не соприкасаются во внутренней точке.

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

Когда и m , и n нечетны, формула правильно сводит к нулю возможные разбиения домино.

Особый случай возникает при облицовке $2\times n$ прямоугольник с n домино: последовательность сводится к последовательности Фибоначчи .

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

1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, ... (последовательность A004003 в OEIS ).

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

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

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

Татами

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

Приложения в статистической физике

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

См. также

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

Ссылки

• Бараона, Франциско (1982), «О вычислительной сложности моделей спинового стекла Изинга», Journal of Physics A: Mathematical and General , 15 (10): 3241–3253, Бибкод : 1982JPhA...15.3241B , doi : 10.1088/ 0305-4470/15/10/028 , МР   0684591
• Эриксон, Алехандро; Раски, Франк (2013), «Покрытие татами Домино является NP-полным», в Лекроке, Тьерри; Мушард, Лоран (ред.), Комбинаторные алгоритмы: 24-й международный семинар, IWOCA 2013, Руан, Франция, 10–12 июля 2013 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 8288, Гейдельберг: Springer, стр. 140–149, arXiv : 1305.6669 , doi : 10.1007/978-3-642-45278-9_13 , ISBN  978-3-642-45277-2 , МР   3162068 , S2CID   12738241
• Кастелейн, П.В. (1961), «Статистика димеров на решетке, I: количество расположений димеров на квадратичной решетке», Physica , 27 (12): 1209–1225, Бибкод : 1961Phy....27.1209K , дои : 10.1016/0031-8914(61)90063-5
• Кеньон, Ричард ; Окуньков, Андрей (2005), «Что такое... димер?» (PDF) , Уведомления Американского математического общества , 52 (3): 342–343.
• Кларнер, Дэвид ; Поллак, Джордан (1980), «Разбиение прямоугольников фиксированной ширины на домино», Discrete Mathematics , 32 (1): 45–52, doi : 10.1016/0012-365X(80)90098-9 , MR   0588907 , Zbl   0444.05009
• Раски, Фрэнк ; Вудкок, Дженнифер (2009), «Подсчет плиток татами фиксированной высоты» , Электронный журнал комбинаторики , 16 (1): R126, doi : 10.37236/215 , MR   2558263
• Терстон, WP (1990), «Группы мозаики Конвея», American Mathematical Monthly , 97 (8), Mathematical Association of America: 757–773, doi : 10.2307/2324578 , JSTOR   2324578
• Темперли, HNV ; Фишер, Майкл Э. (1961), «Проблема о димерах в статистической механике – точный результат», Philosophical Magazine , 6 (68): 1061–1063, Бибкод : 1961PMag....6.1061T , doi : 10.1080/14786436108243366

Дальнейшее чтение

• Бодини, Оливье; Латапи, Матье (2003), «Обобщенные мозаики с функциями высоты» (PDF) , Morfismos , 7 (1): 47–68, arXiv : 2101.08347 , заархивировано из оригинала (PDF) 25 ноября 2021 г. , получено в 2021 г. 09-19
• Фаазе, Ф.Дж. (1998), "О количестве конкретных охватывающих подграфов графов $G\times P_{n}$», Ars Combinatoria , 49 : 129–154, MR   1633083.
• Хок, Дж.Л.; Маккистан, Р.Б. (1984), «Заметка о профессиональном вырождении димеров в насыщенном двумерном решеточном пространстве», Discrete Applied Mathematics , 8 : 101–104, doi : 10.1016/0166-218X(84)90083-0 , МР   0739603
• Кеньон, Ричард (2000), «Модель плоского димера с границей: обзор», Бааке, Майкл; Муди, Роберт В. (ред.), Направления математических квазикристаллов , Серия монографий CRM, том. 13, Американское математическое общество , стр. 307–328, ISBN.  0-8218-2629-8 , МР   1798998
• Пропп, Джеймс (2005), «Лямбда-определители и мозаика домино», « Достижения в области прикладной математики» , 34 (4): 871–879, arXiv : math.CO/0406301 , doi : 10.1016/j.aam.2004.06.005 , S2CID   15679557
• Селлерс, Джеймс А. (2002), «Разбиения домино и произведения чисел Фибоначчи и Пелла» , Журнал целочисленных последовательностей , 5 (статья 02.1.2): 12, Bibcode : 2002JIntS...5...12S
• Стэнли, Ричард П. (1985), «О димерных покрытиях прямоугольников фиксированной ширины», Discrete Applied Mathematics , 12 : 81–87, doi : 10.1016/0166-218x(85)90042-3 , MR   0798013
• Уэллс, Дэвид (1997), Словарь любопытных и интересных чисел Penguin (переработанная редакция), Лондон: Penguin, стр. 182, ISBN  0-14-026149-4