Домино черепица

Плитка домино из квадрата 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 домино: последовательность сводится к последовательности Фибоначчи (последовательность A000045 в OEIS ) ( Klarner & Pollack 1980 ) . ${\ 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). Они используются для облицовки комнат плиткой, но с дополнительными правилами их размещения. В частности, как правило, соединения, на которых встречаются три татами, считаются благоприятными, в то время как соединения, где встречаются четыре, - неблагоприятными, поэтому правильная плитка татами - это такая плитка, где только три татами встречаются в любом углу ( Mathar 2013 ; Ruskey & Woodcock 2009 ). Задача выложить плиткой неправильную комнату татами, которые пересекаются с тремя татами в углу, является NP-полной ( Erickson & Ruskey 2013 ).

Вырожденные кривые, заполняющие пространство [ править ]

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

^ Фрактал Мункреса определен в «Теореме 44.1» в faculty.etsu.edu/gardnerr/5357/notes/Munkres-44

Бодини, Оливье; Latapy, Matthieu (2003), "Generalized Tilings with Height Functions" (PDF) , Morfismos , 7 (1): 47–68, ISSN 1870-6525 , заархивировано из оригинала 10 февраля 2012 г. , извлечено из 2008-09- 08CS1 maint: неподходящий URL ( ссылка )
Эриксон, Алехандро; Раски, Франк (2013), «Покрытие татами домино является NP-полным», Комбинаторные алгоритмы , Конспекты лекций в Comput. Sci., 8288 , Springer, Heidelberg, стр. 140–149, arXiv : 1305.6669 , doi : 10.1007 / 978-3-642-45278-9_13 , MR 3162068 , S2CID 12738241
Faase, F. (1998), "О количестве конкретных остовных подграфов графов GX P_n", Ars Combin. , 49 : 129–154, MR 1633083
Hock, JL; McQuistan, RB (1984), «Заметка о профессиональном вырождении димеров в насыщенном двумерном решетчатом пространстве», Discrete Applied Mathematics , 8 : 101–104, DOI : 10.1016 / 0166-218X (84) 90083-0 , Руководство по ремонту 0739603
Kasteleyn, PW (1961), "Статистика димеров на решетке. I. Число расположений димеров на квадратной решетке", Physica , 27 (12): 1209–1225, Bibcode : 1961Phy .... 27.1209K , DOI : 10,1016 / 0031-8914 (61) 90063-5
Кеньон, Ричард (2000), «Модель плоского димера с границей: обзор», в Бааке, Майкл; Муди, Роберт В. (ред.), Направления в математических квазикристаллах , Серия монографий CRM, 13 , Провиденс, Род-Айленд: Американское математическое общество , стр. 307–328, ISBN 0-8218-2629-8, Руководство по ремонту 1798998 , Zbl 1026.82007
Кеньон, Ричард; Окуньков, Андрей (2005), "Что такое ... димер?" (PDF) , Уведомления Американского математического общества , 52 (3): 342–343, ISSN 0002-9920
Кларнер, Дэвид ; Поллак, Джордан (1980), «Домино-мозаики прямоугольников с фиксированной шириной», Дискретная математика , 32 (1): 45–52, DOI : 10.1016 / 0012-365X (80) 90098-9 , MR 0588907 , Zbl 0444.05009
Матар, Ричард Дж. (2013), Мощение прямоугольных областей прямоугольными плитками: татами и мозаики без татами , arXiv : 1311.6135 , Bibcode : 2013arXiv1311.6135M
Пропп, Джеймс (2005), «Лямбда-детерминанты и домино-мозаики», Успехи в прикладной математике , 34 (4): 871–879, arXiv : math.CO/0406301 , doi : 10.1016 / j.aam.2004.06.005 , S2CID 15679557
Раски, Фрэнк ; Вудкок, Дженнифер (2009), "Подсчет фиксированной высоты Таты разбиения" , Электронный журнал комбинаторика , 16 (1): R126, DOI : 10,37236 / 215 , MR 2558263
Селлерс, Джеймс А. (2002), «Мостики домино и произведения чисел Фибоначчи и Пелла» , Журнал целочисленных последовательностей , 5 (статья 02.1.2): 12, Bibcode : 2002JIntS ... 5 ... 12S
Стэнли, Ричард П. (1985), «О димерных покрытиях прямоугольников фиксированной ширины», Дискретная прикладная математика , 12 : 81–87, DOI : 10.1016 / 0166-218x (85) 90042-3 , MR 0798013
Thurston, WP (1990), "облицовочные группы Конвея", Американские математические Месячные , Математическая ассоциация Америки, 97 (8): 757-773, DOI : 10,2307 / 2324578 , JSTOR 2324578
Уэллс, Дэвид (1997), Словарь любопытных и интересных чисел Penguin (пересмотренное издание), Лондон: Penguin, стр. 182, ISBN 0-14-026149-4
Темперли, HNV ; Фишер, Майкл Э. (1961), «Проблема Димера в статистической механике - точный результат», Philosophical Magazine , 6 (68): 1061–1063, Bibcode : 1961PMag .... 6.1061T , doi : 10.1080 / 14786436108243366

[Munkres-1] Фрактал Мункреса определен в «Теореме 44.1» в faculty.etsu.edu/gardnerr/5357/notes/Munkres-44