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

Геометрическая конструкция Мозаика домино из квадрата 8 × 8

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

• 1 Функции высоты
• 2 Условие роста Терстона
• 3 Подсчет тайлинга регионов
• 4 Татами
• 5 Вырожденные кривые заполнения пространства
• 6 См. Также
• 7 Ссылки

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

Количество способов покрыть $m\; \times \; n\; \{\backslash \; displaystyle\; m\; \backslash \; умножить\; на\; n\}$прямоугольник с $mn\; 2\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{mn\}\; \{2\}\}\}$домино, рассчитанный независимо Temperley Fisher (1961) и Kasteleyn (1961), определяется как

$\prod \; j\; =\; 1\; \lceil \; m\; 2\; \rceil \; \prod \; k\; =\; 1\; \lceil \; n\; 2\; \rceil \; (4\; cos\; 2\; \; \pi \; jm\; +\; 1\; +\; 4\; cos\; 2\; \; \pi \; kn\; +\; 1).\; \{\backslash \; displaystyle\; \backslash \; prod\; \_\; \{j\; =\; 1\}\; ^\; \{\backslash \; lceil\; \{\backslash \; frac\; \{m\}\; \{2\}\}\; \backslash \; rceil\}\; \backslash \; prod\; \_\; \{k\; =\; 1\}\; ^\; \{\backslash \; lceil\; \{\backslash \; frac\; \{n\}\; \{2\}\}\; \backslash \; rceil\}\; \backslash \; left\; (4\; \backslash \; cos\; ^\; \{2\}\; \{\backslash \; frac\; \{\backslash \; pi\; j\}\; \{m\; +\; 1\}\}\; +\; 4\; \backslash \; cos\; ^\; \{2\}\; \{\backslash \; frac\; \{\backslash \; pi\; k\}\; \{n\; +\; 1\}\}\; \backslash \; справа).\}$

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

Особый случай возникает при мозаике прямоугольника $2\; \times \; n\; \{\backslash \; displaystyle\; 2\; \backslash \; times\; n\}$с n доминошками: последовательность сводится к последовательности Фибоначчи (последовательность A000045 в OEIS ) (Klarner Pollack 1980) ошибка harv: нет цели: CITEREFKlarnerPollack1980 (help ).

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

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

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

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

• 

  Ацтекский ромб 4-го порядка, имеющий 1024 плитки домино.

• 

  Одна из возможных плиток

Татами - японские коврики в форме домино (прямоугольник 1x2). Они используются для облицовки комнат плиткой, но с дополнительными правилами их размещения. В частности, как правило, стыки, на которых встречаются три татами, считаются благоприятными, в то время как стыки, где встречаются четыре татами, - неблагоприятными, поэтому правильная плитка татами - это такая плитка, где только три татами встречаются в любом углу (Mathar 2013 ; Руски и Вудкок 2009). Задача облицовки неправильной комнаты татами, которые пересекаются с тремя татами, в углу - это NP-complete (Erickson Ruskey 2013).

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

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

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

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

• Бодини, Оливье; Латапи, Матье (2003), «Обобщенные мозаики с функциями высоты» (PDF), Morfismos, 7 (1): 47–68, ISSN 1870-6525, заархивировано из оригинала 10 февраля 2012 г., извлечено 8 сентября 2008 г. CS1 maint: непригодный URL (ссылка )
• Эриксон, Алехандро; Руски, Фрэнк (2013), «Покрытие татами домино является NP-полным», Комбинаторные алгоритмы, Конспекты лекций по вычислительным наукам, 8288, Springer, Heidelberg, pp. 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, MR 0739603
• Kasteleyn, PW (1961), "The statisti cs димеров на решетке. 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, MR 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), Тротуарная прямоугольная г egions с прямоугольными плитками: татами и мозаики без татами, arXiv : 1311.6135, Bibcode : 2013arXiv1311.6135M
• Propp, James (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)
• Стэнли, Ричард П. (1985), «О димерных покрытиях прямоугольников фиксированной ширины», Дискретная прикладная математика, 12: 81–87, doi : 10.1016 / 0166-218x (85) 90042-3, MR 0798013
• Терстон, WP (1990), «Тайлинг-группы Конвея», American Mathematical Monthly, Mathematical Association of America, 97 (8): 757–773, doi : 10.2307 / 2324578, JSTOR 2324578
• Уэллс, Дэвид ( 1997), Словарь любопытных и интересных чисел Penguin (исправленное издание), Лондон: Penguin, стр. 182, ISBN 0-14-026149-4
• Темперли, Х. Н. В. ; Фишер, Майкл Э. (1961), «Проблема Димера в статистической механике - точный результат», Philosophical Magazine, 6 (68): 1061–1063, doi : 10.1080 / 14786436108243366