stringtranslate.com

Полимино

18 односторонних пентамино , в том числе 6 зеркальных пар.

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

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

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

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

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

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

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

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

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

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

По состоянию на 2004 год Иван Дженсен перечислил фиксированные полимино до n = 56 – примерно 6,915 × 10.31 . [8]

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

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

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

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

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

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

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

[13]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Этимология

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

Большинство числовых префиксов греческие. Полимино размера 9 и 11 чаще принимают латинские префиксы нона- (нономино) и ундека- (ундекомино), чем греческие префиксы эннеа- (эннеомино) и хендека- (хендекомино). [ почему? ]

Смотрите также

Примечания

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

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