Poliomina

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
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[1]) 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:

Nontromino 001.svg Nontromino 002.svg Nontetromino 001.svg Nontetromino 007.svg Nontetromino 014.svg Nontetromino 015.svg Nonpolyomino 005.svg Nonpolyomino 022.svg Nonpolyomino 065.svg Nonpolyomino 073.svg Nonpolyomino 071.svg

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.[2] 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.[3] 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.[4] Beseda poliomina izhaja iz starogrške besede πολυ: poly - veliko, iz polýs - mnog, in domina.[5] 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.[6]

Štetje poliomin[uredi | uredi kodo]

Proste, enostranske in negibne poliomine[uredi | uredi kodo]

Pri štetju obstajajo trije običajni načini razlikovanja poliomin:[7][8]

  • 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_nA001168)
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
17   50.107.909 417.496.576.187 417.546.684.096 7.946.380 42.161.529 100.203.194 400.795.844

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

Simetrije poliomin[uredi | uredi kodo]

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.[11] 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:
  • 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)
Polyomino simmetry 001.svg Polyomino simmetry 002.svg Polyomino simmetry 003.svg Polyomino simmetry 004.svg Polyomino simmetry 005.svg Polyomino simmetry 006.svg Polyomino simmetry 007.svg Polyomino simmetry 008.svg  
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[uredi | uredi kodo]

Induktivni algoritmi[uredi | uredi kodo]

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.[12] 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.[13]

Metoda s prenosno matriko[uredi | uredi kodo]

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

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[uredi | uredi kodo]

Negibne poliomine[uredi | uredi kodo]

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.[16] 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:[17]

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

Najboljša znana spodnja meja za \lambda je 3,980137.[18] Najboljša znana zgornja meja, neizboljšana še od 1970-ih, je \lambda < 4,65.[19]

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[uredi | uredi kodo]

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.[11]

Posebni razredi poliomin[uredi | uredi kodo]

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.[20][21][22]

Glej tudi[uredi | uredi kodo]

Opombe in sklici[uredi | uredi kodo]

  1. ^ Potočnik (2002).
  2. ^ Golomb (Polyominoes, predgovor k prvi izdaji) je zapisal »opažanje, da obstaja dvanajst različnih vzorcev (pentomin), ki jih lahko tvorimo iz petih povezanih kamenčkov na igralni deski za go, … se pripisuje starodavnemu mojstru te igre.«
  3. ^ Jelliss, George Peter (1988). "Dissection Problems in PFCS/FCR" (v angleščini). Pridobljeno dne 2011-08-30. 
  4. ^ Golomb (1994).
  5. ^ Tavzes (2002), str. 900.
  6. ^ Grünbaum; Shephard (1987).
  7. ^ Redelmeier (1981).
  8. ^ Golomb (1994), § 6.
  9. ^ Jensen, Iwan. "Series for lattice animals or polyominoes" (v angleščini). Pridobljeno dne 2007-05-06. 
  10. ^ Oliveira e Silva, Tomás. "Animal enumerations on the {4,4} Euclidean tiling" (v angleščini). Pridobljeno dne 2007-05-06. 
  11. ^ 11,0 11,1 Redelmeier (1981), § 3.
  12. ^ Golomb (1994), str. 73-79.
  13. ^ Redelmeier (1981), § 4 in § 6.
  14. ^ Jensen (2001).
  15. ^ Conway (1995).
  16. ^ Jensen; Guttmann (2000).
  17. ^ Demaine, Erik D.; O'Rourke, Joseph (2001-11-30). "Problem 37: Counting Polyominoes". The Open Problems Project (v angleščini). Pridobljeno dne 2011-08-31. 
  18. ^ Barequet idr. (2006).
  19. ^ Klarner; Rivest (1973).
  20. ^ Bousquet-Mélou (1998).
  21. ^ Delest (1988).
  22. ^ Bousquet-Mélou; Fédou (1995).

Viri[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]