Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
«Полимино» перенаправляется сюда. Для книги Соломона Голомба см. Полимино: головоломки, шаблоны, проблемы и упаковки .
18 односторонних пентамино , в том числе 6 зеркальных пар
35 бесплатных гексомино , окрашенных в соответствии с их симметрией.
Одно бесплатное домино .

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

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

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

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

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

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

Перечень полимино [ править ]

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

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

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

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

пимя (  последовательность OEIS )свободныйодносторонний ( A000988 )фиксированный ( A001168 )
всего ( A000105 )с отверстиями ( A001419 )без отверстий ( A000104 )
1мономино10111
2домино10112
3Тромино20226
4тетромино505719
5пентамино120121863
6гексомино35 год035 год60216
7гептомино1081107196760
8Octomino36963637042,725
9нономино1,285371,2482,5009 910
10Decino4 6551954 4609 18936 446
11ундкомино1707397916 09433 896135 268
12додекомино63 6004,66358 937126 759505 861

По состоянию на 2004 год Иван Дженсен насчитал фиксированные полимино до n = 56; количество фиксированных полимино с 56 ячейками составляет примерно 6,915 × 10 31 . [8] Свободные полимино были пронумерованы до n = 28 Томасом Оливейрой и Силвой [9], а затем до n = 45 Тошихиро Сиракавой. [10]

Симметрии полимино [ править ]

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

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

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

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

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

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

пнет ( A006749 )зеркало (90 °) ( A006746 )зеркало (45 °) ( A006748 )C 2 ( A006747 )D 2  (90 °) ( A056877 )D 2  (45 °) ( A056878 )C 4 ( A144553 )D 4 ( A142886 )
100000001
200001000
300101000
411011001
552211001
6206252000
7849743100
8316235184111
91,1963826194002
104 4619022738100
1116 750147917310200
1262 8783417927815333

[12]

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

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

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

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

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

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

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

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

Трансфер-матричный метод [ править ]

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

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

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

Асимптотический рост количества полимино [ править ]

Фиксированные полимино [ править ]

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

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

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

существуют. Другими словами, п растет экспоненциально . Наиболее известная нижняя граница для λ - 4,00253. [19] Самая известная верхняя граница, не улучшавшаяся с 1970-х годов, - λ <4.65 . [20]

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

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

Бесплатные полимино [ править ]

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

Особые классы полимино [ править ]

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

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

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

Направленные полимино [22], выпуклые полимино [22] столбца (или строки), [23] и выпуклые полимино [24] были эффективно пронумерованы областью n , а также некоторыми другими параметрами, такими как периметр, с использованием производящих функций .

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

Тайлинг с полимино [ править ]

В развлекательной математике часто ставятся задачи, связанные с мозаикой заданной области или всей плоскости с помощью полимино [26], и связанные с этим задачи исследуются в математике и информатике .

Мозаичные области с наборами полимино [ править ]

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

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

Мозаичные области с копиями одного полимино [ править ]

Другой класс задач спрашивает, могут ли копии данного полимино мозаить прямоугольник , и если да, то какие прямоугольники они могут мозаить. [29] Эти проблемы были тщательно изучены для конкретных полимино, [30] и таблицы результатов для отдельных полимино доступны. [31] Кларнер и Гёбель показали, что для любого полимино существует конечное множество простых прямоугольников, которые оно мозаично, так что все остальные прямоугольники, которые оно мозаично, могут быть выложены этими простыми прямоугольниками. [32] [33] Каменецкий и Кук показали, как различные непересекающиеся (так называемые «дырявые») полимино могут мозаить прямоугольники. [34]

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

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

Покрытие плоскости копиями одного полимино [ править ]

Два мозаичных нономино, не удовлетворяющих критерию Конвея.

Также много обсуждалось мозаичное размещение на плоскости копий одного полимино. В 1965 году было отмечено, что все полимино до гексомино [38] и все гептомино, кроме четырех, покрывают плоскость. [39] Затем Дэвид Берд установил, что все октимино, кроме 26, покрывают самолет. [40] Роудс обнаружил, что все, кроме 235, полимино порядка 9, [41] и такие результаты были расширены до более высоких порядков Роадсом (до порядка 14) [42] и другими. Полимино, покрывающие плоскость, классифицируются по симметрии их мозаик и по количеству аспектов (ориентаций), в которых плитки появляются в них. [43] [44]

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

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

Укладка общей фигуры мозаикой из различных полимино [ править ]

Минимальный показатель совместимости для T и W пентоминых .

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

Полимино в головоломках и играх [ править ]

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

Этимология [ править ]

Слово Полимин и имена различных порядков Полимина все беки-формация от слова домино , общий игровой элемент , состоящий из двух квадратов, с первой буквой D- причудливо интерпретируется как вариант префикс ди- означающего «два . " Считается, что название « домино» для игровой фишки произошло от «пятнистого маскарадного домино» , от латинского « dominus» . [51]

Большинство числовых префиксов - греческие. Полимино порядка 9 и 11 чаще принимает латинские префиксы нона- (нонамин) и undeca- (undecomino) , чем греческие префиксы ennea- (enneomino) и hendeca- (hendecomino).

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

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

Заметки [ править ]

  1. ^ Голомба ( полимино Предисловие к первому изданию) пишет«наблюдениечто есть двенадцать отличительные узоры (пентомино)которые могут быть образованы пять соединенных камней на Go борту ... приписывается древним мастером этой игры».
  2. ^ Голомб, Соломон В. (1994). Полимино (2-е изд.). Принстон, Нью-Джерси: Издательство Принстонского университета. ISBN 978-0-691-02444-8.
  3. ^ Гарднер, М. (ноябрь 1960). «Подробнее о формах, которые можно сделать сложными домино (математические игры)». Scientific American . 203 (5): 186–201. DOI : 10.1038 / Scientificamerican1160-186 . JSTOR 24940703 . 
  4. ^ Уиттингтон, SG; Сотерос, CE (1990). «Решетчатые животные: точные результаты и дикие догадки». В Grimmett, G .; Уэлш, Д. (ред.). Беспорядок в физических системах . Издательство Оксфордского университета.
  5. ^ Грюнбаум, Бранко ; Шепард, GC (1987). Плитки и узоры . Нью-Йорк: WH Freeman and Company. ISBN 978-0-7167-1193-3.
  6. ^ Редельмайер, Д. Хью (1981). «Подсчет полимино: еще одна атака» . Дискретная математика . 36 (2): 191–203. DOI : 10.1016 / 0012-365X (81) 90237-5 .
  7. ↑ Голомб, глава 6
  8. ^ Иван Дженсен. «Серия для решетчатых зверюшек или полимино» . Архивировано 12 июня 2007 года . Проверено 6 мая 2007 .
  9. ↑ Tomás Oliveira e Silva. «Перечисления животных на {4,4} евклидовой плитке» . Архивировано 23 апреля 2007 года . Проверено 6 мая 2007 .
  10. ^ "Гармонический Магический Квадрат, Перечисление Полимино с учетом симметрии" (PDF) .
  11. ^ a b Редельмайер, раздел 3
  12. ^ Подсчет полимино: еще одна атака
  13. Перейти ↑ Golomb, pp. 73–79
  14. ^ Редельмайер, раздел 4
  15. ^ Редельмайер, раздел 6
  16. ↑ Дженсен, Иван (февраль 2001 г.). «Перечисления решетчатых животных и деревьев». Журнал статистической физики . 102 (3–4): 865–881. arXiv : cond-mat / 0007239 . Bibcode : 2001JSP ... 102..865J . DOI : 10,1023 / A: 1004855020556 . S2CID 10549375 . 
  17. ^ Конвей, Эндрю (1995). «Перечисление 2D перколяционных рядов методом конечных решеток: теория». Журнал физики A: математический и общий . 28 (2): 335–349. Bibcode : 1995JPhA ... 28..335C . DOI : 10.1088 / 0305-4470 / 28/2/011 . Zbl 0849.05003 . 
  18. ^ Дженсен, Иван; Гуттманн, Энтони Дж. (2000). «Статистика решетчатых зверей (полимино) и многоугольников». Журнал физики A: математический и общий . 33 (29): L257 – L263. arXiv : cond-mat / 0007238v1 . Bibcode : 2000JPhA ... 33L.257J . DOI : 10.1088 / 0305-4470 / 33/29/102 . S2CID 6461687 . 
  19. ^ Barequet, Гилл. «λ> 4: улучшенная нижняя граница константы роста полимино» . Проверено 2 февраля 2017 . Цитировать журнал требует |journal=( помощь )
  20. ^ Кларнер, DA; Ривест, Р.Л. (1973). «Процедура улучшения верхней границы количества n -мино» (PDF) . Канадский математический журнал . 25 (3): 585–602. CiteSeerX 10.1.1.309.9151 . DOI : 10,4153 / CJM-1973-060-4 . Архивировано из оригинала (PDF версии технического отчета) 26 ноября 2006 года . Проверено 11 мая 2007 .  
  21. ^ Уилф, Герберт С. (1994). Генерирующаяфункционология (2-е изд.). Бостон, Массачусетс: Academic Press. п. 151. ISBN. 978-0-12-751956-2. Zbl  0831.05001 .
  22. ^ Буске-Mélou, Мирей (1998). «Новые результаты подсчета двумерных животных» . Дискретная математика . 180 (1–3): 73–106. DOI : 10.1016 / S0012-365X (97) 00109-X .
  23. ^ Делест, М.-П. (1988). «Производящие функции для столбчато-выпуклых полимино» . Журнал комбинаторной теории, Серия А . 48 (1): 12–31. DOI : 10.1016 / 0097-3165 (88) 90071-4 .
  24. ^ Буске-Mélou, Мирей ; Феду, Жан-Марк (1995). «Производящая функция выпуклых полимино: разрешение q -дифференциальной системы» . Дискретная математика . 137 (1–3): 53–75. DOI : 10.1016 / 0012-365X (93) E0161-V .
  25. ^ Picciotto, Анри (1999), Геометрия Labs , MathEducationPage.org, стр. 208.
  26. ^ Мартин, Джордж Э. (1996). Полимино: Путеводитель по головоломкам и задачам по укладке плитки (2-е изд.). Математическая ассоциация Америки . ISBN 978-0-88385-501-0.
  27. ^ CB Haselgrove; Дженифер Хазелгроув (октябрь 1960 г.). «Компьютерная программа для пентамино» (PDF) . Эврика . 23 : 16–18.
  28. ^ Голомб, Соломон В. (1970). «Мозаика из наборов полимино» . Журнал комбинаторной теории . 9 : 60–71. DOI : 10.1016 / S0021-9800 (70) 80055-2 .
  29. ↑ Голомб, Полимино , глава 8
  30. ^ Рид, Майкл. «Ссылки на выпрямляемые полиомино» . Архивировано из оригинала на 2004-01-16 . Проверено 11 мая 2007 .
  31. ^ Рид, Майкл. «Список известных простых прямоугольников для различных полимино» . Архивировано из оригинала на 2007-04-16 . Проверено 11 мая 2007 .
  32. ^ Кларнер, DA; Гебель, Ф. (1969). «Упаковочные коробки с одинаковыми фигурами». Indagationes Mathematicae . 31 : 465–472.
  33. ^ Klarner, Дэвид А. (февраль 1973). «Повторение теоремы о конечном базисе» (PDF) . Технический отчет Стэнфордского университета STAN-CS-73–338. Архивировано из оригинального (PDF) 23 октября 2007 года . Проверено 12 мая 2007 .
  34. ↑ Каменецкий, Дмитрий; Кук, Тристром (2015). «Укладка прямоугольников дырявыми полимино». arXiv : 1411.2699 [ cs.CG ].
  35. ^ Голомб, Соломон В. (1966). «Плитка из полимино» . Журнал комбинаторной теории . 1 (2): 280–296. DOI : 10.1016 / S0021-9800 (66) 80033-9 .
  36. ^ Мур, Кристофер ; Робсон, Джон Майкл (2001). «Проблемы с жесткой плиткой с помощью простых плиток» (PDF) . Архивировано из оригинального (PDF) 17 июня 2013 года.
  37. ↑ Петерсен, Иварс (25 сентября 1999 г.), «Math Trek: Tiling with Polyominoes» , Science News , заархивировано из оригинала 20 марта 2008 г. , получено 11 марта 2012 г..
  38. ↑ Гарднер, Мартин (июль 1965 г.). «О соотношении математики и упорядоченных образцов оп-арта». Scientific American . 213 (1): 100–104. DOI : 10.1038 / Scientificamerican1265-100 .
  39. ^ Гарднер, Мартин (август 1965). «Мысли о задаче общения с разумными организмами в иных мирах». Scientific American . 213 (2): 96–100. DOI : 10.1038 / Scientificamerican0865-96 .
  40. ^ Гарднер, Мартин (август 1975). «Еще о мозаике плоскости: возможности полимино, полиалмазов и полигексов». Scientific American . 233 (2): 112–115. DOI : 10.1038 / Scientificamerican0875-112 .
  41. ^ Rawsthorne, Daniel A. (1988). «Сложность мозаики малых n -мино ( n <10)» . Дискретная математика . 70 : 71–75. DOI : 10.1016 / 0012-365X (88) 90081-7 .
  42. Перейти ↑ Rhoads, Glenn C. (2003). Плоские мозаики и поиск апериодического прототила . Кандидатская диссертация, Университет Рутгерса.
  43. ^ Грюнбаум и Шепард, раздел 9.4
  44. ^ Китинг, К .; Винс, А. (1999). "Изоэдральная мозаика Полимино плоскости" . Дискретная и вычислительная геометрия . 21 (4): 615–630. DOI : 10.1007 / PL00009442 .
  45. Перейти ↑ Rhoads, Glenn C. (2005). «Плоские мозаики полимино, полигексами и полиалмазами» . Журнал вычислительной и прикладной математики . 174 (2): 329–353. Bibcode : 2005JCoAM.174..329R . DOI : 10.1016 / j.cam.2004.05.002 .
  46. ^ Niţică Виорел (2003). «Повторение плитки». МАССА selecta . Провиденс, Род-Айленд: Американское математическое общество. С. 205–217. Руководство по ремонту 2027179 . 
  47. ^ Mireles, JL, "Поли 2 омино"
  48. ^ "Реста, Г.," Полиполимино " " . Архивировано 22 февраля 2011 года . Проверено 2 июля 2010 .
  49. ^ "Zucca, L.," Воспоминание о программном прошлом " " . Архивировано 15 марта 2012 года . Проверено 15 декабря 2011 .
  50. ^ Барбанс, Улдис; Цибулис, Андрис; Ли, Гилберт; Лю, Энди; Уэйнрайт, Роберт (2005). «Теория чисел Полимино (III)». В Сипре - Барри Артур ; Demaine, Erik D .; Demaine, Martin L .; Роджерс, Том (ред.). Дань математику . Уэллсли, Массачусетс: А.К. Петерс. С. 131–136. ISBN 978-1-56881-204-5.
  51. ^ Оксфордский словарь английского языка , 2-е издание, запись домино

Внешние ссылки [ править ]

Онлайн-решатели полимино [ править ]

  • Решатель полимино на основе Java с открытым исходным кодом
  • Интерактивное приложение для мозаики из полимино

Публикации [ править ]

  • Полимино конечно-прямоугольные мозаики Карла Дальке
  • Реализация и описание метода Дженсена
  • Статья с описанием современных оценок (PS)
  • Вайстейн, Эрик В. «Полёмино» . MathWorld .
  • MathPages - Примечания по перечислению полимино с различной симметрией
  • Список задач рассечения в Fairy Chess Review
  • Тетрады Карла Шерера, Демонстрационный проект Вольфрама .
  • Описание различных алгоритмов решения
  • Бесплатные генераторы полимино Rosettacode на различных языках программирования