Poliomina

Edina prosta domina

2 prosti tromini

5 prostih tetromin

12 prostih pentomin, pobarvanih glede na njihovo simetrijo

35 prostih heksomin

108 prostih heptomin

369 prostih oktomin

Poliomína (tudi polinomína) je ravninski lik, ki ga sestavlja eden ali več skladnih neprekrivajočih se enotskih kvadratov ortogonalno povezanih po stranicah. Je vrsta poliforme, katere celica je kvadrat. Lahko jo imamo za končno podmožico pravilnega kvadratnega pokritja s povezano notranjostjo. Naslednji liki:

na primer niso poliomine, saj so vsaj enkrat povezani le z ogliščema. Takšni liki, imenovani nepoliomine, skupaj s prostimi poliominami tvorijo množico likov, imenovanih (prosti) polipleti ali polikralji, kjer je zadnje poimenovanje povezano s šahovskimi figurami, kralji. Polipleti se pojavljajo v igri življenja Johna Hortona Conwayja.

Poliomine razvrstimo po tem koliko enotskih celic imajo, kar se imenuje red poliomine:

število celic	ime
1	monomina
2	domina
3	tromina, triomina ali trinomina
4	tetromina
5	pentomina ali pentamina
6	heksomina
7	heptomina
8	oktomina
9	nonomina ali eneomina
10	dekomina
11	undekomina ali hendekomina
12	dodekomina

Poliomine se pojavljajo v priljubljenih ugankah vsaj že od leta 1907, štetje pentomin pa izvira še iz antike. Mnogo rezultatov z liki iz enega do šest kvadratov je bilo prvič objavljeno v reviji Fairy Chess Review med letoma 1937 in 1957, pod imenom »razčlenitveni problemi« (angleško dissection problems), niso pa bili opaženi, ker so bili večinoma objavljeni v nepregledni kodirani obliki. Ime poliomina je skoval ameriški matematik in inženir Solomon Wolf Golomb leta 1953, o njih pa je nato veliko pisal Martin Gardner v svoji rubriki Matematične igre v reviji Scientific American. Beseda poliomina izhaja iz starogrške besede πολυ: poly - veliko, iz polýs - mnog, in domina. Beseda domina verjetno izhaja iz pegaste široke maškaradne obleke domino, iz latinskega dominus - gospodar.

S poliominami so povezani poliamanti, ki jih sestavljajo enakostranični trikotniki; poliheksi, ki jih tvorijo pravilni šestkotniki, in druge ravninske poliforme. Poliomine so posplošili na višje razsežnosti s spajanjem kock v polikocke, ali hiperkock v polihiperkocke.

Kot pri mnogih ugankah v razvedrilni matematiki je s poliominami povezanih veliko kombinatoričnih problemov. Najosnovnejši je štetje poliomin za dano velikost. Za štetje ne obstaja noben splošni obrazec, razen za posebne razrede poliomin. Znanih je več ocen, obstajajo pa tudi algoritmi za njihovo računanje.

Poliomine z luknjami za nekatere primere niso primerne, na primer za probleme pokrivanja ravnine. Včasih se takšne poliomine izključijo in so dovoljene le enostavno povezane.

Štetje poliomin

Proste, enostranske in negibne poliomine

Pri štetju obstajajo trije običajni načini razlikovanja poliomin:

• proste poliomine so različni liki, če noben ni transformacija (vzporedni premik, vrtenje, zrcaljenje ali drsno zrcaljenje) drugega (figure, ki jih lahko vzamemo v roke in jih obrnemo).
• enostranske poliomine se razlikujejo, kadar nobena ni vzporedno premaknjena ali zavrtena (figure, ki jih ne moremo obrniti).
• negibne poliomine se razlikujejo, kadar nobena ni vzporedno premaknjena (figure, ki jih ne moremo obrniti ali zasukati).

Naslednja razpredelnica prikazuje število poliomin različnih vrst z n celicami, ter poliplete. Naj $a_{n}$ označuje število negibnih poliomin z n celicami (od katerih imajo lahko nekatere luknje).

n	ime	proste (OEIS A000105)	proste nepoliomine (A194596)	prosti polipleti (A030222)	proste z luknjami (A001419)	proste brez lukenj (A000104)	enostranske (A000988)	negibne ($a_n$, A001168)
1	monomina	1	0	1	0	1	1	1
2	domina	1	1	2	0	1	1	2
3	tromina	2	3	5	0	2	2	6
4	tetromina	5	17	22	0	5	7	19
5	pentomina	12	82	94	0	12	18	63
6	heksomina	35	489	524	0	35	60	216
7	heptomina	108	2.923	3.031	1	107	196	760
8	oktomina	369	18.401	18.770	6	363	704	2.725
9	nonomina	1.285	116.848	118.133	37	1.248	2.500	9.910
10	dekomina	4.655	753.726	758.381	195	4.460	9.189	36.446
11	undekomina	17.073	4.898.579	4.915.652	979	16.094	33.896	135.268
12	dodekomina	63.600	32.085.696	32.149.296	4.663	58.937	126.759	505.861
13		238.591	211.398.614	211.637.205	21.474	217.117	476.270	1.903.890
14		901.971	1.400.292.492	1.401.194.463	96.496	805.475	1.802.312	7.204.874
15		3.426.576	9.318.028.028	9.321.454.604	425.449	3.001.127	6.849.777	27.394.666
16		13.079.255	62.259.251.309	62.272.330.564	1.849.252	11.230.003	26.152.418	104.592.937

Iwan Jensen je preštel negibne poliomine do n = 56: $a_{56}$ je približno 6,915 · 10³¹. Proste poliomine do n = 28 je preštel Tomás Oliveira e Silva.

Simetrije poliomin

Diedrska grupa $D_{4}$ je grupa simetrij (simetrijska grupa) kvadrata. Ta grupa vsebuje štiri zasuke in štiri zrcaljenja. Tvorimo jo z izmeničnim zrcaljenjem prek osi x in prek diagonale. Ena prosta poliomina odgovarja največ 8. negibnim poliominam, ki so njene podobe pod simetrijo $D_4$. Te podobe pa niso nujno različne: več ima prosta poliomina simetrije, manj ima različnih negibnih dvojnic. Zaradi tega lahko prosta poliomina, ki je invarianta pri nekaterih ali vseh netrivialnih simetrijah $D_4$, odgovarja le 4., 2. ali 1. negibni poliomini. Matematično gledano so proste poliomine ekvivalenčni razredi negibnih poliomin pod grupo $D_4$.

Za poliomine lahko obstajajo naslednje simetrije. Za vsako simetrijo je dano najmanjše število celic v poliomini:

• 8 negibnih poliomin za vsako prosto peoliomino:
  • brez simetrije (4)
• 4 negibne poliomine za vsako prosto poliomino:
  • osna simetrija glede na smeri mrežnih črt (90°) (4)
  • osna simetrija glede na diagonale (45°) (3)
  • rotacijska simetrija reda 2: $C_2$ (4)
• 2 negibni poliomini za vsako prosto poliomino:
  • simetrija glede na smeri obeh mrežnih črt, dve osi osne simetrije: $D_2$ (90°) (2)
  • simetrija glede na smeri obeh diagonal, dve osi osne simetrije: $D_2$ (45°) (7)
  • rotacijska simetrija reda 4: $C_4$ (8)
• 1 negibna poliomina za vsako prosto poliomino:
  • vse simetrije kvadrata: $D_4$ (1).

Naslednja razpredelnica prikazuje število poliomin z n celicami, glede na simetrijske grupe, in z enojnimi luknjami.

n	brez simetrije (A006749)	zrcaljenje (90°) (A006746)	zrcaljenje (45°) (A006748)	$C_2$ (A006747)	$D_2$ (90°) (A056877)	$D_2$ (45°) (A056878)	$C_4$ (A144553)	$D_4$ (A142886)	(A001419)
1	0	0	0	0	0	0	0	1	0
2	0	0	0	0	1	0	0	0	0
3	0	0	1	0	1	0	0	0	0
4	1	1	0	1	1	0	0	1	0
5	5	2	2	1	1	0	0	1	0
6	20	6	2	5	2	0	0	0	0
7	84	9	7	4	3	1	0	0	1
8	316	23	5	18	4	1	1	1	6
9	1.196	38	26	19	4	0	0	2	37
10	4.461	90	22	73	8	1	0	0	195
11	16.750	147	91	73	10	2	0	0	979
12	62.878	341	79	278	15	3	3	3	4.663
13	237.394	564	326	1.076	17	3	2	2	21.474
14	899.265	1.294	301	1.090	30	5	0	0	96.496
15	3.422.111	2.148	1.186	4.125	35	6	0	0	425.449
16	13.069.026	4.896	1.117	4.183	60	14	12	5	1.849.252

Algoritmi za štetje negibnih poliomin

Induktivni algoritmi

Vsako poliomino reda n + 1 lahko dobimo z dodajanjem celice k poliomini reda n. Od to izhajajo induktivni algoritmi za tvorjenje poliomin.

Najbolj preprosto se lahko v seznam poliomin reda n dodajajo kvadrati k vsaki poliomini na vsako možno mesto. Poliomina reda n + 1, ki pri tem nastane, ni dvojnica tiste, ki smo jo že našli. Izboljšave pri urejevanju štetja in označevanje sosednjih kvadratov, ki jih ne bi smeli upoštevati, zmanjšajo število potrebnih primerov za preverjanje dvojnikov. Ta metoda se lahko uporablja za preštevanje tako prostih kot tudi negibnih poliomin.

Boljšo metodo, ki jo je opisal Redelmeier, je več avtorjev uporabilo kot način ne samo štetja poliomin (brez zahteve, da se vse poliomine reda n ohranjajo pri štetju tistih reda n + 1), ter tudi dokazalo zgornje meje za njihovo število. Osnovna zamisel je, da začnemo z enim samim kvadratom, in od tod, rekurzivno dodajamo kvadrate. Odvisno od podrobnosti lahko štejemo vsako n-omino n-krat, enkrat od začetka vsakega njenega n-tega kvadrata, ali pa jih štejemo vsakega enkrat.

Pri najenostavnejšemu izvajanju se dodaja samo en kvadrat na enkrat. Začnemo z enim kvadratom, oštevilčimo sosednje kvadrate v smeri urinega kazalca od zgoraj, 1, 2, 3 in 4. Sedaj izberemo število med 1 in 4, in na tem mestu dodamo kvadrat. Potem oštevilčimo neoštevilčene sosednje kvadrate in začnemo s 5. Potem izberemo številko večjo od prej izbrane številke in dodamo ta kvadrat. Nadeljujemo z izbiranjem številke večje od števila trenutnega kvadrata, dodamo ta kvadrat, ter nato številčimo nove sosednje kvadrate. Ko tvorimo n kvadratov, tvorimo n-omino. Ta metoda zagotavlja, da vsako negibno poliomino štejemo točno n-krat, enkrat od vsakega začetnega kvadrata. Lahko jo optimiramo, da štejemo vsako poliomino samo enkrat, in ne n-krat. Začnemo z začetnim kvadratom, ga označimo kot levo najnižje ležečega v poliomini. Ne številčimo drugih kvadratov, ki so v spodnji vrstici, ali levo od kvadrata v isti vrstici. To različico je opisal Redelmeier.

Pri štetju prostih poliomin moramo po tvorjenju vsake n-omine preveriti simetrije. Vendar je hitreje tvoriti simetrične poliomine ločeno (z različico te metode) in določiti število prostih poliomin z Burnsideovo lemo.

Metoda s prenosno matriko

Najsodobnejši algoritem za štetje negibnih poliomin je odkril Iwan Jensen. Izboljšava metode Andrewa Conwayja je eksponentno hitrejša od predhodnih metod, čeprav je čas njenega izvajanja še vedno eksponeneten v n.

Conwayjeva in Jensenova različica metode s prenosno matriko obsega štetje števila poliomin z določeno širino. Računanje števila za vse širine da skupno število poliomin. Osnovna zamisel za metodo je, da se obravnavajo možne začetne vrstice, nato pa se določi najmanjše število kvadratov potrebnih za tvorjenje poliomine z dano širino. Skupaj z rabo rodovnih funkcij je s tem postopkom možno prešteti več poliomin na enkrat, zaradi česar je tudi veliko hitrejši od drugih metod, kjer so mora tvoriti vsaka poliomina.

Čeprav ima izvrsten čas izvajanja, algoritem uporablja eksponentno količino pomnilnika (za n nad 50 je potrebnih več GB pomnilnika), je težji za programiranje od drugih metod, trenutno pa ni primeren tudi za štetje prostih polionim.

Asimptotična rast števila poliomin

Negibne poliomine

Teoretični argumenti in numerični računi podpirajo oceno:

$a_{n} \sim \frac{c\lambda^{n}}{n} \!\, ,$

kjer sta $\lambda = 4,0626$ in $c=0,3169$. Vendar ta rezultat ni dokazan, tako da sta vrednosti $\lambda$ in c le oceni. Znani teoretični rezultati niso niti približno tako določeni kot ta ocena. Dokazano je, da obstaja limita:

$\lim_{n\rightarrow \infty} (a_{n})^{1/n} = \lambda \!\, .$

Vrednost $a_{n}$ raste eksponentno in je približno enaka:

$a_{n} \sim n^{\lambda} \!\, .$

Najboljša znana spodnja meja za $\lambda$ je 3,980137. Najboljša znana zgornja meja, neizboljšana še od 1970-tih, je $\lambda < 4,65$.

Za določevanje spodnje meje je preprosta, vendar zelo učinkovita metoda povezovanja poliomin. Naj je zgornji-desni kvadrat najbolj desni kvadrat v najvišji vrstici poliomine. Podobno je definiran spodnji-levi kvadrat. Potem se lahko zgornji-desni kvadrat poljubne poliomine velikosti n zveže s spodnjim-levim kvadratom poljubne poliomine velkikosti m, s čimer se dobi edina (n+m)-omina. To dokazuje $a_{n}a_{m} \leq a_{n+m}$. S pomočje te enačbe se lahko pokaže, da velja $\lambda \geq (a_{n})^{1/n}$ za vse n. Ta prečiščen postopek skupaj s podatki za $a_{n}$ da zgornjo spodnjo mejo.

Zgornja meja se dobi s posplošitvijo induktivne metode za štetje poliomin. Namesto, da dodajamo po en kvadrat na enkrat, dodajamo skupino kvadratov. To pogosto opišejo kot »dodajanje rogovil«. Z dokazom, da je vsaka n-omina zaporedje rogovil, in limitami kombinacij možnih rogovil, se dobi zgornja meja števila n-omin. V zgornjih nakazanih algoritmih moramo na primer v vsakem koraku izbrati večje število, dodamo pa največ tri nova števila, ker so največ trije neoštevilčeni kvadrati sosednji poljubnemu oštevilčenemu kvadratu. Na ta način se dobi zgornja meja 6,75. Z 2,8 milijonoma rogovilami sta Klarner in Rivest dobila vrednost za zgornjo mejo 4,65.

Proste poliomine

Približka za število negibnih in prostih poliomin sta povezana na preprost način. Prosta poliomina brez simetrij (zasuka ali zrcaljenja) odgovarja osmim negibnim poliominam, in za velike n je večina n-omin brez simetrij. Zaradi tega je število negibnih n-omin približno enako 8-kratnemu številu prostih n-omin. Ko se n veča, je ta približek eksponentno točnejši.

Posebni razredi poliomin

Za štetje posebnih razredov poliomin obstajajo točni obrazci, na primer za konveksne ali usmerjene poliomine.

Definicija konveksne poliomine se razlikuje od običajne definicije konveksnosti. Poliomina je stolpčno konveksna, če je presečišče z vsako navpično črto konveksno, oziroma, če noben stolpec ne vsebuje luknje. Podobno je poliomina vrstno konveksna, če je presečišče z vsako vodoravno črto konveksno. Poliomina je konveksna, če je stolpčno in vrstno konveksna.

Poliomina je usmerjena, če vsebuje kvadrat, imenovan koren, tako da se vsak drug kvadrat lahko doseže z gibanjem navzgor ali desno za en kvadrat, brez da bi zapustili poliomino.

Usmerjene, stolpčne (ali vrstično) konveksne in konveksne poliomine so učinkovito prešteli glede na površino n ter glede na druge parametre, kot je npr. obseg, s pomočjo rodovnih funkcij.

Glej tudi

• teorija perkolacije
• Youngov diagram
• Blokus
• kvadratni graf

Viri

• Barequet, Gill; Moffie, Micha; Ribó, Ares; Rote, Günter (2006). "Counting polyominoes on twisted cylinders". Integers 6: A22. 
• Bousquet-Mélou, Mireille; Fédou, Jean-Marc (1995). "The generating function of convex polyominoes: The resolution of a q-differential system". Discrete Mathematics 137 (1–3): 53–75. doi:10.1016/0012-365X(93)E0161-V. 
• Bousquet-Mélou, Mireille (1998). "New enumerative results on two-dimensional directed animals". Discrete Mathematics 180 (1–3): 73–106. doi:10.1016/S0012-365X(97)00109-X. 
• Conway, Andrew (1995). "Enumerating 2D percolation series by the finite-lattice method: theory". Journal of Physics. A. Mathematical and General 28 (2): 335–349. doi:10.1088/0305-4470/28/2/011. 
• Delest, M.-P. (1988). "Generating functions for column-convex polyominoes". Journal of Combinatorial Theory. Series A 48 (1): 12–31. doi:10.1016/0097-3165(88)90071-4. 
• Golomb, Solomon Wolf (1994). Polyominoes (2. izd.). Princeton, New Jersey: Princeton University Press. ISBN 0-691-02444-8. 
• Grünbaum, Branko; Shephard, G. C. (1987). Tilings and Patterns. New York: W. H. Freeman and Company. ISBN 0-7167-1193-1. 
• Jensen, Iwan; Guttmann, Anthony J. (2000). "Statistics of lattice animals (polyominoes) and polygons". Journal of Physics. A. Mathematical and General 33: L257–L263. doi:10.1088/0305-4470/33/29/102. 
• Jensen, Iwan (februar 2001). "Enumerations of Lattice Animals and Trees". Journal of Statistical Physics 102 (3–4): 865–881. doi:10.1023/A:1004855020556. arXiv:cond-mat/0007239. 
• Klarner, David Anthony (1965). "Some Results Concerning Polyominoes" (PDF). Fibonacci Quarterly 3 (1): 9–20. http://www.fq.math.ca/Scanned/3-1/klarner.pdf. Pridobljeno 2011-08-31. 
• Klarner, David Anthony; Rivest, Ronald Linn (1973). "A procedure for improving the upper bound for the number of n-ominoes" (različica tehniškega poročila PDF). Canadian Journal of Mathematics 25: 585–602. http://historical.ncstrl.org/litesite-data/stan/CS-TR-72-263.pdf. Pridobljeno 2007-05-11. 
• Potočnik, Aleksander (2002). "Polinomine". Brihtnež 0 (1): str. 4-7. http://www.dmfa.si/Brihtnez/BrihtnezIndex.html. 
• Redelmeier, D. Hugh (1981). "Counting polyominoes: yet another attack". Discrete Mathematics 36: 191–203. doi:10.1016/0012-365X(81)90237-5. 
• Tavzes, Miloš, ur (2002). Veliki slovar tujk. Ljubljana: Cankarjeva založba. ISBN 961-231-271-0. 

Zunanje povezave

• Polyomino na MathWorld (v angleščini)
• Aplikacija za interaktivno pokrivanje s poliominami (v angleščini)
• Pokrivanje končnega pravokotnika Karla Dahlkeja (v angleščini)
• Uporaba in opis Jensenove metode (v angleščini)
• Članek z opisi sodobnih ocen (PS) (v angleščini)
• MathPages – opombe na štetje poliomin z različnimi simetrijami (v angleščini)
• Seznam razčlenitvenih problemov v Fairy Chess Review (v angleščini)
• Schere, Karl, Tetrads Wolfram Demonstrations Project (v angleščini)