Полимино

Полимино образованная — это плоская геометрическая фигура, соединением одного или нескольких равных квадратов от края к краю. Это полиформа , ячейки которой имеют квадратную форму. Его можно рассматривать как конечное подмножество правильной квадратной мозаики .

Полимино используются в популярных головоломках по крайней мере с 1907 года, а перечисление пентамино датируется древностью. ^{[ 1 ]} Многие результаты с фигурами размером от 1 до 6 клеток были впервые опубликованы в журнале Fairy Chess Review в период с 1937 по 1957 год под названием «Задачи о расчленении». Название полимино было изобретено Соломоном В. Голомбом в 1953 году. ^{[ 2 ]} и он был популяризирован Мартином Гарднером в колонке « Математические игры » в ноябре 1960 года в журнале Scientific American . ^{[ 3 ]}

С полимино связаны полиалмазы , образованные из равносторонних треугольников ; многогексы , образованные из правильных шестиугольников ; и другие плоские полиформы . Полимино были обобщены на более высокие измерения путем объединения кубов в поликубы или гиперкубов в полигиперкубы.

В статистической физике изучение полимино и их многомерных аналогов (которые в этой литературе часто называют решетчатыми животными ) применяется к задачам физики и химии. Полимино использовались в качестве моделей разветвленных полимеров и перколяционных кластеров. ^{[ 4 ]}

Как и многие головоломки в развлекательной математике , полимино поднимает множество комбинаторных задач. Самый простой — это перебор полимино заданного размера. Никакой формулы не найдено, за исключением особых классов полимино. Известен ряд оценок и существуют алгоритмы их расчета.

Полимино с дырками неудобно для некоторых целей, например, для решения задач мозаики. В некоторых контекстах полимино с отверстиями исключаются, позволяя использовать только односвязные полимино. ^{[ 5 ]}

Перечисление полимино

Свободные полимино ( n = от 2 до 6)
Одно бесплатное домино
Два бесплатных тримино
Пять бесплатных тетромино
12 свободных пентамино , раскрашенных в соответствии с их симметрией.
35 бесплатных гексомино , раскрашенных в соответствии с их симметрией.

Свободные, односторонние и фиксированные полимино

Существует три распространенных способа различения полимино для перечисления: ^{[ 6 ]}^{[ 7 ]}

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

В следующей таблице показано количество полимино разных типов с n ячейками.

н	имя	бесплатно			односторонний	зафиксированный
н	имя	общий	с дырками	без дырок	односторонний	зафиксированный
1	мономино	1	0	1	1	1
2	домино	1	0	1	1	2
3	тримино	2	0	2	2	6
4	тетрамино	5	0	5	7	19
5	пентамино	12	0	12	18	63
6	гексомино	35	0	35	60	216
7	гептамино	108	1	107	196	760
8	октамино	369	6	363	704	2,725
9	нономино	1,285	37	1,248	2,500	9,910
10	декомино	4,655	195	4,460	9,189	36,446
11	ундекомино	17,073	979	16,094	33,896	135,268
12	Додекомино	63,600	4,663	58,937	126,759	505,861
OEIS Последовательность		А000105	А001419	А000104	А000988	А001168

Фиксированные полимино были пронумерованы в 2004 году до n = 56 Иваном Дженсеном, ^{[ 8 ]} а в 2024 году до n = 70 — Джилл Барекет и Гил Бен-Шахар. ^{[ 9 ]}

Свободные полимино были пронумерованы в 2007 году до n = 28 Томасом Оливейрой и Силвой, ^{[ 10 ]}в 2012 году до n = 45 Тосихиро Сиракава, ^{[ 11 ]} а в 2023 году — до n = 50 — Джон Мейсон. ^{[ 12 ]}

Вышеупомянутые последовательности OEIS, за исключением A001419, включают счетчик 1 для количества нулевых полимино; нуль-полимино — это полимино, состоящее из нулевых квадратов.

Симметрии полимино

Группа диэдра D ₄ это группа симметрий — ( группа симметрии ) квадрата. Эта группа содержит четыре вращения и четыре отражения. Он генерируется попеременными отражениями относительно оси x и диагонали. Одному свободному полимино соответствует не более 8 фиксированных полимино, которые являются его образами при симметриях D ₄ . Однако эти изображения не обязательно различны: чем больше симметрии у свободного полимино, тем меньше у него различных фиксированных аналогов. Следовательно, свободное полимино, инвариантное относительно некоторых или всех нетривиальных симметрий D4 _, может соответствовать только 4, 2 или 1 фиксированному полимино. Математически свободные полимино представляют собой классы эквивалентности фиксированных полимино в группе D ₄ .

Полимино имеют следующие возможные симметрии; ^{[ 13 ]} в каждом случае указано наименьшее количество квадратов, необходимых в полимино с такой симметрией:

8 фиксированных полимино на каждое свободное полимино:
- нет симметрии (4)
4 фиксированных полимино на каждое свободное полимино:
- зеркальная симметрия относительно одного из направлений линий сетки (4)
- зеркальная симметрия относительно диагональной линии (3)
- 2-кратная вращательная симметрия: C ₂ (4)
2 фиксированных полимино на каждое свободное полимино:
- симметрия относительно обоих направлений линий сетки и, следовательно, также 2-кратная вращательная симметрия: D ₂ (2) (также известная как четырехгруппа Клейна )
- симметрия относительно обоих диагональных направлений, а значит, и 2-кратная вращательная симметрия: D ₂ (7)
- 4-кратная вращательная симметрия: C ₄ (8)
1 фиксированное полимино на каждое свободное полимино:
- вся симметрия квадрата: D ₄ (1).

Точно так же количество односторонних полимино зависит от симметрии полимино следующим образом:

По 2 односторонних полимино на каждое свободное полимино:
- нет симметрии
- 2-кратная вращательная симметрия: C ₂
- 4-кратная вращательная симметрия: C ₄
По 1 одностороннему полимино на каждое свободное полимино:
- вся симметрия квадрата: D ₄
- зеркальная симметрия относительно одного из направлений линий сетки
- зеркальная симметрия относительно диагональной линии
- симметрия относительно обоих направлений линий сетки и, следовательно, также 2-кратная вращательная симметрия: D ₂
- симметрия относительно обоих диагональных направлений и, следовательно, также 2-кратная вращательная симметрия: D ₂ .

В следующей таблице показано количество полимино с n квадратами, отсортированное по группам симметрии.

н	никто	зеркало 90°	зеркало 45°	С ₂	D_Д2 90°	D_Д2 45°	С ₄	Д ₄
1	0	0	0	0	0	0	0	1
2	0	0	0	0	1	0	0	0
3	0	0	1	0	1	0	0	0
4	1	1	0	1	1	0	0	1
5	5	2	2	1	1	0	0	1
6	20	6	2	5	2	0	0	0
7	84	9	7	4	3	1	0	0
8	316	23	5	18	4	1	1	1
9	1,196	38	26	19	4	0	0	2
10	4,461	90	22	73	8	1	0	0
11	16,750	147	91	73	10	2	0	0
12	62,878	341	79	278	15	3	3	3
OEIS Последовательность	А006749	А006746	А006748	А006747	А056877	А056878	А144553	А142886

^{[ 14 ]}

Алгоритмы перебора фиксированных полимино

Индуктивные алгоритмы

Каждое полимино размера n +1 можно получить добавлением квадрата к полимино размера n . Это приводит к алгоритмам индуктивного генерирования полимино.

Проще всего, если имеется список полимино размера n , квадраты могут быть добавлены рядом с каждым полимино в каждой возможной позиции, а полученное полимино размера n +1 добавлено в список, если оно не является дубликатом уже найденного; уточнения в порядке перечисления и маркировки соседних квадратов, которые не следует учитывать, уменьшают количество случаев, которые необходимо проверять на наличие дубликатов. ^{[ 15 ]} Этот метод можно использовать для подсчета как свободных, так и фиксированных полимино.

Более сложный метод, описанный Редельмейером, использовался многими авторами как способ не только подсчета полимино (без требования, чтобы все полимино размера n были сохранены в размере для перечисления полимино размера n +1), но и для доказательства верхнего ограничения на их количество. Основная идея заключается в том, что мы начинаем с одного квадрата, а затем рекурсивно добавляем квадраты. В зависимости от деталей, он может считать каждое n -мино n раз, по одному разу, начиная с каждого из n квадратов, или может быть настроен на подсчет каждого только один раз.

Самая простая реализация предполагает добавление по одному квадрату за раз. Начиная с начального квадрата, пронумеруйте соседние квадраты по часовой стрелке сверху: 1, 2, 3 и 4. Теперь выберите число от 1 до 4 и добавьте квадрат в этом месте. Пронумеруйте ненумерованные соседние квадраты, начиная с 5. Затем выберите число, большее, чем выбранное ранее число, и добавьте этот квадрат. Продолжайте выбирать число, большее, чем номер текущего квадрата, добавляя этот квадрат, а затем нумеруя новые соседние квадраты. Когда n было создано n квадратов, было создано -омино.

Этот метод гарантирует, что каждое фиксированное полимино будет подсчитано ровно n раз, по одному разу для каждого начального квадрата. Его можно оптимизировать так, чтобы каждое полимино считалось только один раз, а не n раз. Начиная с начального квадрата, объявите его нижним левым квадратом полимино. Просто не нумеруйте квадраты, находящиеся в нижнем ряду или слева от квадратов в том же ряду. Это версия, описанная Редельмейером.

Если вместо этого кто-то хочет подсчитать свободные полимино, то можно проверить симметрию после создания каждого n -омино. Однако это быстрее ^{[ 16 ]} генерировать симметричные полимино отдельно (разновидностью этого метода) ^{[ 17 ]} и так определим количество свободных полимино по лемме Бернсайда .

Трансфер-матричный метод

Самый современный алгоритм перебора фиксированных полимино был открыт Иваном Дженсеном . ^{[ 18 ]} Усовершенствование метода Эндрю Конвея. ^{[ 19 ]} он экспоненциально быстрее, чем предыдущие методы (однако время его работы по-прежнему экспоненциально зависит от n ).

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

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

Асимптотический рост числа полимино

Фиксированные полимино

Теоретические аргументы и численные расчеты подтверждают оценку количества фиксированных полимино размера n.

A_{n}\sim {\frac {c\lambda ^{n}}{n}}

где λ = 4,0626 и с = 0,3169. ^{[ 20 ]} Однако этот результат не доказан, а значения λ и c являются лишь оценками.

Известные теоретические результаты далеко не так конкретны, как эта оценка. Доказано, что

\lim _{n\rightarrow \infty }(A_{n})^{\frac {1}{n}}=\lambda

существует. Другими словами, растет _An экспоненциально . Самая известная нижняя граница λ , найденная в 2016 году, равна 4,00253. ^{[ 21 ]} Самая известная верхняя граница — λ < 4,5252 . ^{[ 22 ]}

Чтобы установить нижнюю границу, существует простой, но очень эффективный метод — объединение полимино. Определите верхний правый квадрат как самый правый квадрат в самой верхней строке полимино. Аналогичным образом определите нижний левый квадрат. Затем правый верхний квадрат любого полимино размера n можно присоединить к левому нижнему квадрату любого полимино размера m, чтобы получить уникальное ( n + m )-мино. Это доказывает A _n A _m ≤ A _{n + m} . Используя это уравнение, можно показать, λ ≥ ( An _что ) ^{1/ н} для всех н . Уточнения этой процедуры в сочетании с данными для An _. дают нижнюю границу, приведенную выше

Верхняя оценка достигается обобщением индуктивного метода перебора полимино. Вместо того, чтобы добавлять по одному квадрату за раз, за раз добавляется группа квадратов. Это часто называют добавлением веток . Доказав, что каждое n -мино представляет собой последовательность веточек, и доказав пределы комбинаций возможных веточек, можно получить верхнюю границу числа n -мино. Например, в изложенном выше алгоритме на каждом шаге мы должны выбирать большее число, и добавляется не более трех новых чисел (поскольку к любому пронумерованному квадрату примыкает не более трех ненумерованных клеток). Это можно использовать для получения верхней границы 6,75. Используя 2,8 миллиона ветвей, Кларнер и Ривест получили верхнюю границу 4,65. ^{[ 23 ]} который впоследствии был улучшен Барекетом и Шалахом до 4,5252. ^{[ 22 ]}

Бесплатные полимино

Аппроксимации количества фиксированных и свободных полимино связаны простым образом. Свободное полимино без симметрии (вращение или отражение) соответствует 8 различным фиксированным полимино, а при больших n большинство n -амино не имеют симметрии. Следовательно, количество фиксированных n -амино примерно в 8 раз превышает количество свободных n -амино. Более того, это приближение экспоненциально точнее с увеличением n . ^{[ 13 ]}

Специальные классы полимино

Известны точные формулы перечисления полимино специальных классов, таких как класс выпуклых полимино и класс направленных полимино.

Определение выпуклого полимино отличается от обычного определения выпуклости , но похоже на определение, используемое для ортогональной выпуклой оболочки . Полимино называется выпуклым по вертикали или по столбцу, если его пересечение с любой вертикальной линией выпукло (другими словами, в каждом столбце нет отверстий). Аналогично, полимино называется выпуклым по горизонтали или ряду, если его пересечение с любой горизонтальной линией выпукло. Полимино называется выпуклым, если оно выпукло по строкам и столбцам. ^{[ 24 ]}

Полимино называется направленным, если оно содержит квадрат, известный как корень , такой, что в любой другой квадрат можно попасть, перемещаясь на один квадрат вверх или вправо, не покидая полимино.

Направленное полимино, ^{[ 25 ]} столбец (или строка) выпуклые полимино, ^{[ 26 ]} и выпуклые полимино ^{[ 27 ]} были эффективно пронумерованы по площади n , а также по некоторым другим параметрам, таким как периметр, с использованием производящих функций .

Полимино называется равномерным, если его площадь равна периметру. Равное полимино должно состоять из четного числа квадратов; возможно любое четное число больше 15. Например, 16-мино в форме квадрата 4 × 4 и 18-мино в форме прямоугольника 3 × 6 равны. Для полимино с 15 квадратами или меньше периметр всегда превышает площадь. ^{[ 28 ]}

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

В развлекательной математике часто возникают задачи по разбиению заданной области или всей плоскости полимино. ^{[ 29 ]} и смежные проблемы исследуются в математике и информатике .

Замощение регионов наборами полимино

Головоломки обычно требуют разложить данную область заданным набором полимино, например 12 пентамино. В книгах Голомба и Гарднера есть много примеров. Типичная головоломка — выложить прямоугольник 6×10 двенадцатью пентамино; в 1960 году было найдено 2339 решений этой проблемы. ^{[ 30 ]} Там, где разрешено несколько копий полимино в наборе, Голомб определяет иерархию различных областей, которые набор может быть мозаичным, например, прямоугольники, полосы и всю плоскость, и показывает, могут ли полимино из данного набора быть мозаичными. плоскость неразрешима путем отображения наборов плиток Ванга в наборы полимино. ^{[ 31 ]}

Поскольку общая задача замощения областей плоскости наборами полимино является NP-полной , ^{[ 32 ]} укладка мозаики из нескольких частей быстро становится затруднительной, поэтому требуется помощь компьютера. Традиционный подход к мозаике конечных областей плоскости использует метод информатики, называемый обратным поиском . ^{[ 33 ]}

В Jigsaw Sudokus квадратная сетка состоит из областей в форме многочлена (последовательность A172477 в OEIS ).

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

Другой класс задач спрашивает, могут ли копии данного полимино замостить прямоугольник , и если да, то какие прямоугольники они могут замостить. ^{[ 34 ]} Эти проблемы были тщательно изучены для конкретных полимино. ^{[ 35 ]} и таблицы результатов для отдельных полимино доступны. ^{[ 36 ]} Кларнер и Гёбель показали, что для любого полимино существует конечное множество простых прямоугольников, которые оно замостило, так что все остальные прямоугольники, которые оно замостило, можно замостить этими простыми прямоугольниками. ^{[ 37 ]}^{[ 38 ]} Каменецкий и Кук показали, как различные непересекающиеся (называемые «дырчатыми») полимино могут замостить прямоугольники. ^{[ 39 ]}

Помимо прямоугольников, Голомб дал свою иерархию для отдельных полимино: полимино может замостить прямоугольник, половину полосы, изогнутую полосу, увеличенную копию самого себя, квадрант, полосу, полуплоскость , всю плоскость, определенные комбинации или ничего из этого. Среди них есть определенные последствия, как очевидные (например, если полимино замостит полуплоскость, то он замостит всю плоскость), так и менее очевидные (например, если полимино замостит увеличенную копию самого себя, то он замостит квадрант) . В этой иерархии характеризуются полимино размером до 6 (со статусом одного гексомино, которое, как позже выяснилось, замостило прямоугольник, не разрешенное на тот момент). ^{[ 40 ]}

В 2001 году Кристофер Мур и Джон Майкл Робсон показали, что задача замощения одного полимино копиями другого является NP-полной . ^{[ 41 ]}^{[ 42 ]}

Замощение плоскости копиями одного полимино

Замощение плоскости копиями одного полимино также много обсуждалось. В 1965 г. было отмечено, что все полимино вплоть до гексомино ^{[ 43 ]} и все гептамино, кроме четырех, застилают плоскость плиткой. ^{[ 44 ]} Затем Дэвид Берд установил, что все октамино, за исключением 26, украшают плоскость. ^{[ 45 ]} Роусторн обнаружил, что все полимино размером 9, кроме 235, ^{[ 46 ]} и такие результаты были распространены Роудсом на большую площадь (до размера 14) ^{[ 47 ]} и другие. Полимино, замощающие плоскость, классифицируются по симметрии их замощений и по количеству аспектов (ориентаций), в которых плитки появляются в них. ^{[ 48 ]}^{[ 49 ]}

Изучение того, какие полимино могут замостить плоскость, было облегчено с помощью критерия Конвея : за исключением двух нономино, все мозаичные полимино до размера 9 образуют участок, по крайней мере, из одной плитки, удовлетворяющей этому критерию, с более частыми исключениями большего размера. ^{[ 50 ]}

Несколько полимино могут замостить более крупные копии самих себя, и повторение этого процесса рекурсивно дает рептилий мозаику плоскости в виде . Например, для каждого положительного целого числа $n$ можно объединить $n 2$ копии L-тромино, L-тетромино или P-пентамино в одну большую форму, аналогичную меньшему полимино, из которого оно было сформировано. ^{[ 51 ]}

Замощение общей фигуры различными полимино

Минимальная цифра совместимости пентамино T и W.

Проблема совместимости состоит в том, чтобы взять два или более полимино и найти фигуру, которую можно объединить в мозаику. Совместимость полимино широко изучается с 1990-х годов. Хорхе Луис Мирелес и Джованни Реста опубликовали сайты с систематическими результатами. ^{[ 52 ]}^{[ 53 ]} а Ливио Зукка показывает результаты для некоторых сложных случаев, например, для трех разных пентамино. ^{[ 54 ]} Общая проблема может быть сложной. Первая фигура совместимости пентамино L и X была опубликована в 2005 году и содержала по 80 плиток каждого вида. ^{[ 55 ]} Многие пары полимино оказались несовместимыми в результате систематического исчерпания. Неизвестен алгоритм определения совместимости двух произвольных полимино.

Полимино в головоломках и играх.

Помимо описанных выше проблем с мозаикой, существуют развлекательные математические головоломки, которые требуют сложения полимино для создания других фигур. Гарднер предложил несколько простых игр с набором свободных пентамино и шахматной доской. В некоторых вариантах головоломки судоку на сетке используются участки в форме неномино. Видеоигра «Тетрис» основана на семи односторонних тетромино (в игре пишется «Тетримино»), а в настольной игре « Блокус» используются все свободные полимино вплоть до пентамино.

Этимология

Слово полимино и названия полимино различных размеров являются обратными образованиями от слова домино , обычной игровой фигуры, состоящей из двух квадратов. Считается, что название «домино» игровой фигуры произошло от пятнистого домино в маскарадной одежде , от латинского dominus . ^{[ 56 ]} первая буква d- Несмотря на такое происхождение слова, в названии полимино домино причудливо интерпретируется как вариант приставки di-, означающей «два», и заменяется другими числовыми префиксами .

См. также

Теория перколяции , математическое исследование случайных подмножеств целочисленных сеток. Конечные компоненты связности этих подмножеств образуют полимино.
Диаграмма Юнга , особый вид полимино, используемый в теории чисел для описания целочисленных разбиений, а также в теории групп и приложениях в математической физике для описания представлений симметричной группы.
Блокус — настольная игра с использованием полимино.
Квадратный граф — разновидность неориентированного графа, включающая в качестве частного случая графы вершин и ребер полимино.
Поликуб , его аналог в трёх измерениях.

Примечания

↑ Голомб ( «Полимино» , предисловие к первому изданию) пишет: «Наблюдение о том, что существует двенадцать отличительных узоров (пентамино), которые могут быть образованы пятью соединенными камнями на доске го … приписывается древнему мастеру этой игры» .
^ Голомб, Соломон В. (1994). Полимино (2-е изд.). Принстон, Нью-Джерси: Издательство Принстонского университета. ISBN 978-0-691-02444-8 .
^ Гарднер, М. (ноябрь 1960 г.). «Подробнее о фигурах, которые можно составить из сложного домино (Математические игры)». Научный американец . 203 (5): 186–201. дои : 10.1038/scientificamerican1160-186 . JSTOR 24940703 .
^ Уиттингтон, СГ; Сотерос, CE (1990). «Решеточные животные: строгие результаты и дикие догадки». В Гримметте, Г.; Уэлш, Д. (ред.). Беспорядок в физических системах . Издательство Оксфордского университета.
^ Грюнбаум, Бранко ; Шепард, GC (1987). Плитки и узоры . Нью-Йорк: WH Freeman and Company. ISBN 978-0-7167-1193-3 .
^ Редельмайер, Д. Хью (1981). «Подсчет полимино: еще одна атака» . Дискретная математика . 36 (2): 191–203. дои : 10.1016/0012-365X(81)90237-5 .
^ Голомб, глава 6
^ Иван Дженсен. «Серия для решетчатых животных или полимино» . Архивировано из оригинала 12 июня 2007 г. Проверено 6 мая 2007 г.
^ «Материалы симпозиума по разработке алгоритмов и экспериментам (ALENEX) 2024 г. - Повторный подход к подсчету полимино» .
^ Томас Оливейра и Силва. «Нумерации животных на евклидовом мозаике {4,4}» . Архивировано из оригинала 23 апреля 2007 г. Проверено 6 мая 2007 г.
^ «Гармонический магический квадрат, перечисление полимино с учетом симметрии» (PDF) .
^ «Подсчет полимино размера 50» (PDF) .
^ Jump up to: ^а ^б Редельмайер, секция 3
^ Редельмейер, Д. Хью (1981). «Подсчет полимино: еще одна атака» . Дискретная математика . 36 (2): 191–203. дои : 10.1016/0012-365X(81)90237-5 .
^ Голомб, стр. 73–79.
^ Редельмейер, раздел 4
^ Редельмейер, раздел 6
^ Дженсен, Иван (февраль 2001 г.). «Перечисления решетчатых животных и деревьев». Журнал статистической физики . 102 (3–4): 865–881. arXiv : cond-mat/0007239 . Бибкод : 2001JSP...102..865J . дои : 10.1023/А:1004855020556 . S2CID 10549375 .
^ Конвей, Эндрю (1995). «Перечисление двумерных перколяционных рядов методом конечных решеток: теория». Журнал физики A: Математический и общий . 28 (2): 335–349. Бибкод : 1995JPhA...28..335C . дои : 10.1088/0305-4470/28/2/011 . Збл 0849.05003 .
^ Дженсен, Иван; Гутманн, Энтони Дж. (2000). «Статистика решетчатых животных (полимино) и многоугольников». Журнал физики A: Математический и общий . 33 (29): Л257–Л263. arXiv : cond-mat/0007238v1 . Бибкод : 2000JPhA...33L.257J . дои : 10.1088/0305-4470/33/29/102 . S2CID 6461687 .
^ Бареке, Гилл; Роте, Гюнтер; Шала, Мира. «λ > 4: улучшенная нижняя граница константы роста полимино». Коммуникации АКМ . 59 (7): 88–95. дои : 10.1145/2851485 .
^ Jump up to: ^а ^б Бареке, Гилл; Шалах, Мира (2022). «Улучшенные верхние границы констант роста полимино и поликубов» . Алгоритмика . 84 (12): 3559–3586. arXiv : 1906.11447 . дои : 10.1007/s00453-022-00948-6 .
^ Кларнер, Д.А.; Ривест, Р.Л. (1973). «Процедура улучшения верхней границы числа n -омино» (PDF) . Канадский математический журнал . 25 (3): 585–602. CiteSeerX 10.1.1.309.9151 . дои : 10.4153/CJM-1973-060-4 . S2CID 121448572 . Архивировано из оригинала (версия технического отчета в формате PDF) 26 ноября 2006 г. Проверено 11 мая 2007 г.
^ Уилф, Герберт С. (1994). Генерирующая функционалология (2-е изд.). Бостон, Массачусетс: Академическая пресса. п. 151. ИСБН 978-0-12-751956-2 . Збл 0831.05001 .
^ Буске-Мелу, Мирей (1998). «Новые перечислительные результаты по двумерно направленным животным» . Дискретная математика . 180 (1–3): 73–106. дои : 10.1016/S0012-365X(97)00109-X .
^ Делест, М.-П. (1988). «Производящие функции для выпуклых по столбцу полимино» . Журнал комбинаторной теории, серия А. 48 (1): 12–31. дои : 10.1016/0097-3165(88)90071-4 .
^ Буске-Мелу, Мирей ; Феду, Жан-Марк (1995). «Производящая функция выпуклых полимино: разрешение q -дифференциальной системы» . Дискретная математика . 137 (1–3): 53–75. дои : 10.1016/0012-365X(93)E0161-V .
^ Пиччотто, Анри (1999), Geometry Labs , MathEducationPage.org, стр. 208 .
^ Мартин, Джордж Э. (1996). Полимино: Путеводитель по головоломкам и задачам по мозаике (2-е изд.). Математическая ассоциация Америки . ISBN 978-0-88385-501-0 .
^ CB Хазелгроув; Дженифер Хазелгроув (октябрь 1960 г.). «Компьютерная программа для пентамино» (PDF) . Эврика . 23 :16–18.
^ Голомб, Соломон В. (1970). «Замощение наборами полимино» . Журнал комбинаторной теории . 9 : 60–71. дои : 10.1016/S0021-9800(70)80055-2 .
^ ЭД Демейн; М.Л. Демейн (июнь 2007 г.). «Головоломки, сопоставление ребер и упаковка полимино: связи и сложность» . Графы и комбинаторика . 23 : 195–208. дои : 10.1007/s00373-007-0713-4 . S2CID 17190810 .
^ СВ Голомб; Л.Д. Баумерт (1965). «Программирование возврата» . Журнал АКМ . 12 (4): 516–524. дои : 10.1145/321296.321300 .
^ Голомб, Полимино , глава 8
^ Рид, Майкл. «Ссылки на спрямляемые полимино» . Архивировано из оригинала 16 января 2004 г. Проверено 11 мая 2007 г.
^ Рид, Майкл. «Список известных простых прямоугольников для различных полимино» . Архивировано из оригинала 16 апреля 2007 г. Проверено 11 мая 2007 г.
^ Кларнер, Д.А.; Гебель, Ф. (1969). «Упаковка коробочек с соответствующими фигурками». Математические исследования . 31 : 465–472.
^ Кларнер, Дэвид А. (февраль 1973 г.). «Возвращение к теореме о конечном базисе» (PDF) . Технический отчет Стэнфордского университета STAN-CS-73–338. Архивировано из оригинала (PDF) 23 октября 2007 г. Проверено 12 мая 2007 г.
^ Каменецкий Дмитрий; Кук, Тристром (2015). «Замощение прямоугольников дырявым полимино». arXiv : 1411.2699 [ cs.CG ].
^ Голомб, Соломон В. (1966). «Замощение полимино» . Журнал комбинаторной теории . 1 (2): 280–296. дои : 10.1016/S0021-9800(66)80033-9 .
^ Мур, Кристофер ; Робсон, Джон Майкл (2001). «Сложные проблемы с укладкой простых плиток» (PDF) . Архивировано из оригинала (PDF) 17 июня 2013 г.
^ Петерсен, Иварс (25 сентября 1999 г.), «Math Trek: мозаика с полимино» , Science News , заархивировано из оригинала 20 марта 2008 г. , получено 11 марта 2012 г.
^ Гарднер, Мартин (июль 1965 г.). «О связи математики и упорядоченных узоров оп-арта». Научный американец . 213 (1): 100–104. дои : 10.1038/scientificamerican1265-100 .
^ Гарднер, Мартин (август 1965 г.). «Мысли о задаче общения с разумными организмами других миров». Научный американец . 213 (2): 96–100. doi : 10.1038/scientificamerican0865-96 .
^ Гарднер, Мартин (август 1975 г.). «Подробнее о замощении плоскости: возможности полимино, полиалмазов и полигексов». Научный американец . 233 (2): 112–115. doi : 10.1038/scientificamerican0875-112 .
^ Роусторн, Дэниел А. (1988). «Сложность мозаики маленьких n -омино
( n <10)» . Дискретная математика . 70 : 71–75. doi : 10.1016/0012-365X(88)90081-7 .
^ Роудс, Гленн К. (2003). Плоские мозаики и поиск апериодического прототиля . Докторская диссертация, Университет Рутгерса.
^ Грюнбаум и Шепард, раздел 9.4.
^ Китинг, К.; Винс, А. (1999). «Изоэдральная полимино мозаика плоскости» . Дискретная и вычислительная геометрия . 21 (4): 615–630. дои : 10.1007/PL00009442 .
^ Роудс, Гленн К. (2005). «Плоские замощения полимино, полигексами и полиалмазами» . Журнал вычислительной и прикладной математики . 174 (2): 329–353. Бибкод : 2005JCoAM.174..329R . дои : 10.1016/j.cam.2004.05.002 .
^ Ницица, Виорел (2003). «Возвращение к реп-плиткам». МАССОВЫЙ выбор . Провиденс, Род-Айленд: Американское математическое общество. стр. 205–217. МР 2027179 .
^ Мирелес, JL, "Поли ²омино"
^ «Реста Г. «Полиполимино» » . Архивировано из оригинала 22 февраля 2011 г. Проверено 2 июля 2010 г.
^ «Зукка, Л., «Тройные пентамино» » . Проверено 20 апреля 2023 г.
^ Барбанс, Улдис; Цибулис, Андрис; Ли, Гилберт; Лю, Энди; Уэйнрайт, Роберт (2005). «Теория чисел полимино (III)». В Ципре, Барри Артур ; Демейн, Эрик Д.; Демейн, Мартин Л.; Роджерс, Том (ред.). Дань уважения математику . Уэлсли, Массачусетс: АК Питерс. стр. 131–136. ISBN 978-1-56881-204-5 .
^ Оксфордский словарь английского языка , 2-е издание, входное домино

Внешние ссылки

[1] Голомб ( «Полимино» , предисловие к первому изданию) пишет: «Наблюдение о том, что существует двенадцать отличительных узоров (пентамино), которые могут быть образованы пятью соединенными камнями на доске го … приписывается древнему мастеру этой игры» .

[2] Голомб, Соломон В. (1994). Полимино (2-е изд.). Принстон, Нью-Джерси: Издательство Принстонского университета. ISBN 978-0-691-02444-8 .

[3] Гарднер, М. (ноябрь 1960 г.). «Подробнее о фигурах, которые можно составить из сложного домино (Математические игры)». Научный американец . 203 (5): 186–201. дои : 10.1038/scientificamerican1160-186 . JSTOR 24940703 .

[4] Уиттингтон, СГ; Сотерос, CE (1990). «Решеточные животные: строгие результаты и дикие догадки». В Гримметте, Г.; Уэлш, Д. (ред.). Беспорядок в физических системах . Издательство Оксфордского университета.

[5] Грюнбаум, Бранко ; Шепард, GC (1987). Плитки и узоры . Нью-Йорк: WH Freeman and Company. ISBN 978-0-7167-1193-3 .

[6] Редельмайер, Д. Хью (1981). «Подсчет полимино: еще одна атака» . Дискретная математика . 36 (2): 191–203. дои : 10.1016/0012-365X(81)90237-5 .

[7] Голомб, глава 6

[8] Иван Дженсен. «Серия для решетчатых животных или полимино» . Архивировано из оригинала 12 июня 2007 г. Проверено 6 мая 2007 г.

[9] «Материалы симпозиума по разработке алгоритмов и экспериментам (ALENEX) 2024 г. - Повторный подход к подсчету полимино» .

[10] Томас Оливейра и Силва. «Нумерации животных на евклидовом мозаике {4,4}» . Архивировано из оригинала 23 апреля 2007 г. Проверено 6 мая 2007 г.

[11] «Гармонический магический квадрат, перечисление полимино с учетом симметрии» (PDF) .

[12] «Подсчет полимино размера 50» (PDF) .

[Redelmeier,_section_3-13] Jump up to: ^а ^б Редельмайер, секция 3

[14] Редельмейер, Д. Хью (1981). «Подсчет полимино: еще одна атака» . Дискретная математика . 36 (2): 191–203. дои : 10.1016/0012-365X(81)90237-5 .

[15] Голомб, стр. 73–79.

[16] Редельмейер, раздел 4

[17] Редельмейер, раздел 6

[18] Дженсен, Иван (февраль 2001 г.). «Перечисления решетчатых животных и деревьев». Журнал статистической физики . 102 (3–4): 865–881. arXiv : cond-mat/0007239 . Бибкод : 2001JSP...102..865J . дои : 10.1023/А:1004855020556 . S2CID 10549375 .

[19] Конвей, Эндрю (1995). «Перечисление двумерных перколяционных рядов методом конечных решеток: теория». Журнал физики A: Математический и общий . 28 (2): 335–349. Бибкод : 1995JPhA...28..335C . дои : 10.1088/0305-4470/28/2/011 . Збл 0849.05003 .

[20] Дженсен, Иван; Гутманн, Энтони Дж. (2000). «Статистика решетчатых животных (полимино) и многоугольников». Журнал физики A: Математический и общий . 33 (29): Л257–Л263. arXiv : cond-mat/0007238v1 . Бибкод : 2000JPhA...33L.257J . дои : 10.1088/0305-4470/33/29/102 . S2CID 6461687 .

[21] Бареке, Гилл; Роте, Гюнтер; Шала, Мира. «λ > 4: улучшенная нижняя граница константы роста полимино». Коммуникации АКМ . 59 (7): 88–95. дои : 10.1145/2851485 .

[:0-22] Jump up to: ^а ^б Бареке, Гилл; Шалах, Мира (2022). «Улучшенные верхние границы констант роста полимино и поликубов» . Алгоритмика . 84 (12): 3559–3586. arXiv : 1906.11447 . дои : 10.1007/s00453-022-00948-6 .

[23] Кларнер, Д.А.; Ривест, Р.Л. (1973). «Процедура улучшения верхней границы числа n -омино» (PDF) . Канадский математический журнал . 25 (3): 585–602. CiteSeerX 10.1.1.309.9151 . дои : 10.4153/CJM-1973-060-4 . S2CID 121448572 . Архивировано из оригинала (версия технического отчета в формате PDF) 26 ноября 2006 г. Проверено 11 мая 2007 г.

[W151-24] Уилф, Герберт С. (1994). Генерирующая функционалология (2-е изд.). Бостон, Массачусетс: Академическая пресса. п. 151. ИСБН 978-0-12-751956-2 . Збл 0831.05001 .

[25] Буске-Мелу, Мирей (1998). «Новые перечислительные результаты по двумерно направленным животным» . Дискретная математика . 180 (1–3): 73–106. дои : 10.1016/S0012-365X(97)00109-X .

[26] Делест, М.-П. (1988). «Производящие функции для выпуклых по столбцу полимино» . Журнал комбинаторной теории, серия А. 48 (1): 12–31. дои : 10.1016/0097-3165(88)90071-4 .

[27] Буске-Мелу, Мирей ; Феду, Жан-Марк (1995). «Производящая функция выпуклых полимино: разрешение q -дифференциальной системы» . Дискретная математика . 137 (1–3): 53–75. дои : 10.1016/0012-365X(93)E0161-V .

[28] Пиччотто, Анри (1999), Geometry Labs , MathEducationPage.org, стр. 208 .

[29] Мартин, Джордж Э. (1996). Полимино: Путеводитель по головоломкам и задачам по мозаике (2-е изд.). Математическая ассоциация Америки . ISBN 978-0-88385-501-0 .

[30] CB Хазелгроув; Дженифер Хазелгроув (октябрь 1960 г.). «Компьютерная программа для пентамино» (PDF) . Эврика . 23 :16–18.

[31] Голомб, Соломон В. (1970). «Замощение наборами полимино» . Журнал комбинаторной теории . 9 : 60–71. дои : 10.1016/S0021-9800(70)80055-2 .

[32] ЭД Демейн; М.Л. Демейн (июнь 2007 г.). «Головоломки, сопоставление ребер и упаковка полимино: связи и сложность» . Графы и комбинаторика . 23 : 195–208. дои : 10.1007/s00373-007-0713-4 . S2CID 17190810 .

[33] СВ Голомб; Л.Д. Баумерт (1965). «Программирование возврата» . Журнал АКМ . 12 (4): 516–524. дои : 10.1145/321296.321300 .

[34] Голомб, Полимино , глава 8

[35] Рид, Майкл. «Ссылки на спрямляемые полимино» . Архивировано из оригинала 16 января 2004 г. Проверено 11 мая 2007 г.

[36] Рид, Майкл. «Список известных простых прямоугольников для различных полимино» . Архивировано из оригинала 16 апреля 2007 г. Проверено 11 мая 2007 г.

[37] Кларнер, Д.А.; Гебель, Ф. (1969). «Упаковка коробочек с соответствующими фигурками». Математические исследования . 31 : 465–472.

[38] Кларнер, Дэвид А. (февраль 1973 г.). «Возвращение к теореме о конечном базисе» (PDF) . Технический отчет Стэнфордского университета STAN-CS-73–338. Архивировано из оригинала (PDF) 23 октября 2007 г. Проверено 12 мая 2007 г.

[39] Каменецкий Дмитрий; Кук, Тристром (2015). «Замощение прямоугольников дырявым полимино». arXiv : 1411.2699 [ cs.CG ].

[40] Голомб, Соломон В. (1966). «Замощение полимино» . Журнал комбинаторной теории . 1 (2): 280–296. дои : 10.1016/S0021-9800(66)80033-9 .

[41] Мур, Кристофер ; Робсон, Джон Майкл (2001). «Сложные проблемы с укладкой простых плиток» (PDF) . Архивировано из оригинала (PDF) 17 июня 2013 г.

[42] Петерсен, Иварс (25 сентября 1999 г.), «Math Trek: мозаика с полимино» , Science News , заархивировано из оригинала 20 марта 2008 г. , получено 11 марта 2012 г.

[43] Гарднер, Мартин (июль 1965 г.). «О связи математики и упорядоченных узоров оп-арта». Научный американец . 213 (1): 100–104. дои : 10.1038/scientificamerican1265-100 .

[44] Гарднер, Мартин (август 1965 г.). «Мысли о задаче общения с разумными организмами других миров». Научный американец . 213 (2): 96–100. doi : 10.1038/scientificamerican0865-96 .

[45] Гарднер, Мартин (август 1975 г.). «Подробнее о замощении плоскости: возможности полимино, полиалмазов и полигексов». Научный американец . 233 (2): 112–115. doi : 10.1038/scientificamerican0875-112 .

[46] Роусторн, Дэниел А. (1988). «Сложность мозаики маленьких n -омино
( n <10)» . Дискретная математика . 70 : 71–75. doi : 10.1016/0012-365X(88)90081-7 .

[47] Роудс, Гленн К. (2003). Плоские мозаики и поиск апериодического прототиля . Докторская диссертация, Университет Рутгерса.

[48] Грюнбаум и Шепард, раздел 9.4.

[49] Китинг, К.; Винс, А. (1999). «Изоэдральная полимино мозаика плоскости» . Дискретная и вычислительная геометрия . 21 (4): 615–630. дои : 10.1007/PL00009442 .

[50] Роудс, Гленн К. (2005). «Плоские замощения полимино, полигексами и полиалмазами» . Журнал вычислительной и прикладной математики . 174 (2): 329–353. Бибкод : 2005JCoAM.174..329R . дои : 10.1016/j.cam.2004.05.002 .

[51] Ницица, Виорел (2003). «Возвращение к реп-плиткам». МАССОВЫЙ выбор . Провиденс, Род-Айленд: Американское математическое общество. стр. 205–217. МР 2027179 .

[52] Мирелес, JL, "Поли ²омино"

[53] «Реста Г. «Полиполимино» » . Архивировано из оригинала 22 февраля 2011 г. Проверено 2 июля 2010 г.

[54] «Зукка, Л., «Тройные пентамино» » . Проверено 20 апреля 2023 г.

[55] Барбанс, Улдис; Цибулис, Андрис; Ли, Гилберт; Лю, Энди; Уэйнрайт, Роберт (2005). «Теория чисел полимино (III)». В Ципре, Барри Артур ; Демейн, Эрик Д.; Демейн, Мартин Л.; Роджерс, Том (ред.). Дань уважения математику . Уэлсли, Массачусетс: АК Питерс. стр. 131–136. ISBN 978-1-56881-204-5 .

[56] Оксфордский словарь английского языка , 2-е издание, входное домино

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]

[ 35 ]

[ 36 ]

[ 37 ]

[ 38 ]

[ 39 ]

[ 40 ]

[ 41 ]

[ 42 ]

[ 43 ]

[ 44 ]

[ 45 ]

[ 46 ]

[ 47 ]

[ 48 ]

[ 49 ]

[ 50 ]

[ 51 ]

[ 52 ]

[ 53 ]

[ 54 ]

[ 55 ]

[ 56 ]

v т и Полиформы
Полимино	Домино Тромино Тетромино Пентамино Гексомино Гептомино Октамино Нономино декомино
Высшие измерения	Полиоминоид Поликуб
Другие	Поляболо Полиграфтер Полигекс Полиалмаз Псевдо-полимино Полистик
Игры и головоломки	Блоки Кубик сомы Змеиный куб Танграм Гексастикс Тантрикс Тетрис
ВикиПроект Портал