Поліміно або поліоміно англ polyomino плоскі геометричні фігури утворені шляхом з єднання декількох одноклітинних квадра

Поліміно, або поліоміно (англ. polyomino) — плоскі геометричні фігури, утворені шляхом з'єднання декількох одноклітинних квадратів по їх сторонам. Це поліформи, сегменти яких є квадратами.

Укладка 12 пентаміно на шаховій дошці 8×8 з вирізаним центральним квадратом 2×2

Повний набір 35 (двосторонніх) . Якщо заборонити перевертати фігури гексаміно, повний набір буде складатися з 60 «односторонніх» гексаміно.

Фігуру поліміно можна розглядати як скінченну зв'язну підмножину нескінченної шахівниці, яку може обійти тура.

Назва поліміно

Поліміно (n-міно) носять назву по числу n квадратів, з яких вони складаються:

n	Назва	n	Назва
1	мономіно	6	^[ru]
2	доміно	7	^[ru]
3	^[ru]	8	^[ru]
4	тетраміно	9	^[en] або еннеоміно
5	пентаміно	10	декаміно

Історія

Поліміно використовувалися в рекреаційній математиці принаймні з 1907 року, а відомі були ще в давнину. Багато результатів з фігурами, що містять від 1 до 6 квадратів, були вперше опубліковані в журналі «Fairy Chess Review» в період з 1937 по 1957 р., під назвою «проблеми розсічення» (англ. «dissection problems»). Назва «поліміно» або «поліоміно» (англ. polyomino) було придумано в 1953 році і потім популяризовано Мартіном Гарднером.

У 1967 році журнал «Наука і життя» опублікував серію статей про пентаміно. Надалі протягом ряду років публікувалися завдання, пов'язані з поліміно та іншими поліморфами.

Узагальнення поліміно

Укладання всіх 94 двосторонніх псевдопентаміно

Залежно від того, чи дозволяється перевертання або обертання фігур, відрізняються такі три види поліміно:

двосторонні поліміно, або вільні поліміно (англ. free polyominoes) — поліміно, які дозволяється повертати і перевертати;
односторонні поліміно (англ. one-sided polyominoes) — поліміно, які дозволяється повертати в площині, але не дозволяється перевертати;
фіксовані поліміно (англ. fixed polyominoes) — поліміно, що недозволено ні повертати, ні перевертати.

Залежно від умов зв'язності сусідніх комірок розрізняються:

поліміно — набори квадратів, які може обійти візир;
псевдополіміно, або поліплети — набори квадратів, які може обійти король;
квазіполіміно — довільні набори квадратів нескінченної шахової дошки.

У наступній таблиці зібрані дані про число фігур поліміно і його узагальнень. Число квазі-n-міно дорівнює 1 при n = 1 і ∞ при n > 1.

n	поліміно					псевдополіміно
	двосторонні			односторонні	фіксовані	двосторонні	односторонні	фіксовані
	всі	з отворами	без отворів	односторонні	фіксовані	двосторонні	односторонні	фіксовані
	послідовність A000105 з Онлайн енциклопедії послідовностей цілих чисел, OEIS	послідовність A001419 з Онлайн енциклопедії послідовностей цілих чисел, OEIS	послідовність A000104 з Онлайн енциклопедії послідовностей цілих чисел, OEIS	послідовність A000988 з Онлайн енциклопедії послідовностей цілих чисел, OEIS	послідовність A001168 з Онлайн енциклопедії послідовностей цілих чисел, OEIS	послідовність A030222 з Онлайн енциклопедії послідовностей цілих чисел, OEIS	послідовність A030233 з Онлайн енциклопедії послідовностей цілих чисел, OEIS	послідовність A006770 з Онлайн енциклопедії послідовностей цілих чисел, OEIS
1	1	0	1	1	1	1	1	1
2	1	0	1	1	2	2	2	4
3	2	0	2	2	6	5	6	20
4	5	0	5	7	19	22	34	110
5	12	0	12	18	63	94	166	638
6	35	0	35	60	216	524	991	3 832
7	108	1	107	196	760	3 031	5 931	23 592
8	369	6	363	704	2 725	18 770	37 196	147 941
9	1 285	37	1 248	2 500	9 910	118 133	235 456	940 982
10	4 655	195	4 460	9 189	36 446	758 381	1 514 618	6 053 180
11	17 073	979	16 094	33 896	135 268	4 915 652	9 826 177	39 299 408
12	63 600	4 663	58 937	126 759	505 861	32 149 296	64 284 947	257 105 146

Поліформи

Докладніше: Поліформа

Поліформи — узагальнення поліміно, комірками якого можуть бути будь-які однакові багатокутники або багатогранники. Інакше кажучи, поліформа — плоска фігура або просторове тіло, що складається з декількох з'єднаних копій заданої основної форми.

Плоскі (двовимірні) поліформи включають в себе поліамонди, сформовані з рівносторонніх трикутників; ^[ru], сформовані з правильних шестикутників; ^[ru], що складаються з рівнобедрених прямокутних трикутників, та інші.

Приклади просторових (тривимірних) поліформ: полікуби, що складаються з тривимірних кубів; полірони (англ. polyrhons), що складаються з ромбододекаедрів.

Поліформи також узагальнюються на випадок більш високих розмірностей (наприклад, сформовані з гіперкубів — полігіперкуби).

Порядок поліміно

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

Термін був запропонований в 1968 році Д. А. Клернером. Існує множина поліміно порядка 2; прикладом є так звані L-поліміно.

Поліміно порядку 3 не існує; доказ цього було опубліковано в 1992 році. Будь-яке поліміно, з трьох копій якого можна скласти прямокутник, само є прямокутником і має порядок 1.

Існують також пліміно порядку 4, 10, 18, 24, 28, 50, 76, 92, 312; існує конструкція, що дозволяє отримати поліміно порядку 4s для будь-якого натурального s.

Див. також

Поліміно у сестринських Вікіпроєктах
	Файли у Вікісховищі^?

Примітки

Голомб С. В. Полимино, 1975
Weisstein, Eric W. Polyomino(англ.) на сайті Wolfram MathWorld.
Популярне визначення поліміно за допомогою шахової тури не є строгим: існують незв'язні підмножини квадратного паркету, які може обійти тура (наприклад, група з чотирьох полів шахової дошки a1, a8, h1, h8 не є тетраміно, хоча тура, що стоїть на одному з цих полів, може за три ходи обійти три інших поля). Більш строгим було б визначення поліміно за допомогою фігури «візир», використовуваної в шахах Тамерлана: візир ходить лише на одну клітку по горизонталі або вертикалі.
Генри Э. Дьюдени. Кентерберийские головоломки, 1975, стр. 111–113
Гарднер М. Математические головоломки и развлечения, 1971. — Глава 12. Полиомино. — с.111—124
Гарднер М. Математические новеллы, 1974. — Глава 7. Пентамино и полиомино: пять игр и серия задач. — с. 81—95
Наука и жизнь № 2—12 (1967), 1, 6, 9, 11 (1968) и др.
. Архів оригіналу за 11 вересня 2015. Процитовано 1 травня 2015.
Weisstein, Eric W. Polyplet(англ.) на сайті Wolfram MathWorld.
Weisstein, Eric W. Polyform(англ.) на сайті Wolfram MathWorld.
Col. Sicherman's Home Page. Polyform Curiosities [ 14 грудня 2014 у Wayback Machine.]. Catalogue of Polyrhons [ 11 вересня 2015 у Wayback Machine.]
Karl Dahlke. . Архів оригіналу за 15 лютого 2020. Процитовано 1 травня 2015.
Голомб С. В. Polyominoes: Puzzles, Patterns, Problems, and Packings. — 2nd ed. — Princeton University Press, 1994. — .
Weisstein, Eric W. L-Polyomino(англ.) на сайті Wolfram MathWorld.
I. N. Stewart, A. Wormstein (9 1992). Polyominoes of Order 3 Do Not Exist. Journal of Combinatorial Theory, Series A. 61 (1): 130—136. Процитовано 25 серпня 2013.

Література

Голомб С.В. Полимино / Пер. с англ. В. Фирсова. Предисл. и ред. И. Яглома. — М. : Мир, 1975. — С. 207.
Генри Э. Дьюдени. Кентерберийские головоломки / Пер. с англ. Ю.Н.Сударева. — М. : Мир, 1979. — С. 353.
Гарднер М. Математические головоломки и развлечения / Пер. с англ. Ю.А.Данилова. — М. : Мир, 1971. — С. 511.
Гарднер М. Математические новеллы / Пер. с англ. Ю.А.Данилова. Под ред. Я.А.Смородинского. — М. : Мир, 1974. — С. 456.

Посилання

Антология Мартина Гарднера Полимино [ 31 січня 2014 у Wayback Machine.]
Библиотека по математике Полимино [ 9 листопада 2014 у Wayback Machine.]
RSDN: Этюды для программистов Количество полимино [ 10 листопада 2014 у Wayback Machine.]
Michael Reid
Andrew Clarke The Poly Pages Polyominoes [ 14 травня 2015 у Wayback Machine.]
David Eppstein The Geometry Junkyard Polyominoes [ 3 липня 2015 у Wayback Machine.]
Miroslav Vicher Puzzles Pages [ 15 жовтня 2015 у Wayback Machine.]
Kevin L. Gong Polyominoes [ 3 травня 2015 у Wayback Machine.]

[golomb1975-1] Голомб С. В. Полимино, 1975

[mw_polyomino-2] Weisstein, Eric W. Polyomino(англ.) на сайті Wolfram MathWorld.

[note_wazir-3] Популярне визначення поліміно за допомогою шахової тури не є строгим: існують незв'язні підмножини квадратного паркету, які може обійти тура (наприклад, група з чотирьох полів шахової дошки a1, a8, h1, h8 не є тетраміно, хоча тура, що стоїть на одному з цих полів, може за три ходи обійти три інших поля). Більш строгим було б визначення поліміно за допомогою фігури «візир», використовуваної в шахах Тамерлана: візир ходить лише на одну клітку по горизонталі або вертикалі.

[canterbury1979-4] Генри Э. Дьюдени. Кентерберийские головоломки, 1975, стр. 111–113

[gardner_1971_12-5] Гарднер М. Математические головоломки и развлечения, 1971. — Глава 12. Полиомино. — с.111—124

[gardner_1974_7-6] Гарднер М. Математические новеллы, 1974. — Глава 7. Пентамино и полиомино: пять игр и серия задач. — с. 81—95

[nkj1967-7] Наука и жизнь № 2—12 (1967), 1, 6, 9, 11 (1968) и др.

[8] . Архів оригіналу за 11 вересня 2015. Процитовано 1 травня 2015.

[mw_polyplet-9] Weisstein, Eric W. Polyplet(англ.) на сайті Wolfram MathWorld.

[mwpf-10] Weisstein, Eric W. Polyform(англ.) на сайті Wolfram MathWorld.

[11] Col. Sicherman's Home Page. Polyform Curiosities [ 14 грудня 2014 у Wayback Machine.]. Catalogue of Polyrhons [ 11 вересня 2015 у Wayback Machine.]

[eklhad-12] Karl Dahlke. . Архів оригіналу за 15 лютого 2020. Процитовано 1 травня 2015.

[golomb1994-13] Голомб С. В. Polyominoes: Puzzles, Patterns, Problems, and Packings. — 2nd ed. — Princeton University Press, 1994. — .

[mw_Lpoly-14] Weisstein, Eric W. L-Polyomino(англ.) на сайті Wolfram MathWorld.

[order3_1992-15] I. N. Stewart, A. Wormstein (9 1992). Polyominoes of Order 3 Do Not Exist. Journal of Combinatorial Theory, Series A. 61 (1): 130—136. Процитовано 25 серпня 2013.