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

Замощение квадрата плитками домино

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

На популярном математическом ютуб-канале Mathologer имеется видео на тему разбиений на домино.

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

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

Более детальную информацию можно найти в статье Кениона и Окунькова .

Условие высоты Тёрстона

Уильям Пол Тёрстон (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$ прямоугольника ${\frac {mn}{2}}$ костяшками домино вычислили независимо в 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).$

Если m и n оба нечётны, формула корректно даёт нулевое число возможных мозаик домино.

Специальным случаем является замощение $2\times n$ прямоугольника n костяшками домино — получается последовательность Фибоначчи (последовательность A000045 в OEIS) .

Другой специальный случай возникает для квадратов с m = n = 0, 2, 4, 6, 8, 10, 12, … — 1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, … (последовательность A004003 в OEIS).

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

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

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

См. также

• Статистическая механика
• Гауссово свободное поле
• Домино (полимино), задача об «Изуродованной» шахматной доске

Ссылки

• Популярное видео на ютуб-канале Mathologer

Литература

• Olivier Bodini, Matthieu Latapy. Generalized Tilings with Height Functions // Morfismos. — 2003. — Т. 7, вып. 1. — С. 47–68. — ISSN 1870-6525. Архивировано 10 февраля 2012 года..
• F. Faase. On the number of specific spanning subgraphs of the graphs G X P_n // Ars Combin.. — 1998. — Т. 49. — С. 129–154.
• J. L. Hock, R. B. McQuistan. A note on the occupational degeneracy for dimers on a saturated two-dimenisonal lattice space // Discrete Appl. Math.. — 1984. — Т. 8. — С. 101–104. — doi:10.1016/0166-218X(84)90083-0.
• P. W. Kasteleyn. The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice // Physica. — 1961. — Т. 27, вып. 12. — С. 1209–1225. — doi:10.1016/0031-8914(61)90063-5. — ..
• Richard Kenyon. Directions in mathematical quasicrystals / Michael Baake, Robert V. Moody. — Providence, RI: American Mathematical Society, 2000. — Т. 13. — С. 307–328. — ISBN 0-8218-2629-8.
• Richard Kenyon, Andrei Okounkov. What is … a dimer? // Notices of the American Mathematical Society. — 2005. — Т. 52, вып. 3. — P. 342–343. — ISSN 0002-9920..
• David Klarner, Jordan Pollack. Domino tilings of rectangles with fixed width // Discrete Mathematics. — 1980. — Т. 32, вып. 1. — doi:10.1016/0012-365X(80)90098-9..
• Richard J. Paving rectangular regions with rectangular tiles: tatami and non-tatami tilings. — 2013.
• Lambda-determinants and domino-tilings // Advances in Applied Mathematics. — 2005. — Т. 34, вып. 4. — С. 871–879. — doi:10.1016/j.aam.2004.06.005. — arXiv:math.CO/0406301..
• Frank Ruskey, Jennifer Woodcock. Counting fixed-height Tatami tilings. — 2009. — Т. 16, вып. 1. — С. R126.
• James A. Sellers. Domino tilings and products of Fibonacci and Pell numbers // Journal of Integer Sequences. — 2002. — Т. 5, вып. Article 02.1.2..
• Richard P. Stanley. On dimer coverings of rectangles of fixed width // Discrete Appl. Math. — 1985. — Т. 12. — С. 81–87. — doi:10.1016/0166-218x(85)90042-3.
• W. P. Thurston. Conway's tiling groups. — American Mathematical Monthly. — Mathematical Association of America, 1990. — Т. 97. — С. 757–773. — doi:10.2307/2324578..
• David Wells. The Penguin Dictionary of Curious and Interesting Numbers. — London: Penguin, 1997. — С. 182. — ISBN 0-14-026149-4..
• H. N. V. Temperley, Michael E. Fisher. Dimer problem in statistical mechanics-an exact result // Philosophical Magazine. — 1961. — Т. 6, вып. 68. — С. 1061–1063. — doi:10.1080/14786436108243366.