Домино черепица - Domino tiling

Плитка домино из квадрата 8 × 8

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

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

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

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

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

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

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

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

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

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

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

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

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

• 

  Ацтекский алмаз четвертого порядка, имеющий 1024 мозаики домино.

• 

  Один возможный тайлинг

Татами

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

Вырожденные кривые заполнения пространства

Любой конечный набор ячеек, образующих регулярную квадратную сетку n × n, может быть проиндексирован выбранной кривой заполнения пространства, которая согласуется с квадратами (которые рекурсивно разбивают четырехугольную единичную сетку), с индексом i в диапазоне от 0 до п ² -1. Геометрически кривую можно провести через центр квадратных ячеек. Мозаика домино получается объединением соседних ячеек. Индекс j каждого домино будет получен функцией j = floor ( i  ÷  2) исходного индекса сетки. Новая фрактальная кривая - это «вырожденная кривая», потому что это еще один фрактал. Примеры:

«Вырожденная кривая, заполняющая пространство Мортона » дает правильную горизонтально ориентированную мозаику домино; кривая связана с индексированием Geohash , где Z-образная кривая преобразуется в кривую ˆ-образной формы.

«Вырожденная кривая, заполняющая гильбертово пространство » дает апериодическую мозаичную систему , смешивающую домино с горизонтальной и вертикальной ориентацией, по 50% каждой ориентации. Вырожденная кривая Гильберта изоморфна фракталу Мункреса.

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

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

Смотрите также

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

Примечания

использованная литература

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