Ogled vira Poliomina

[[Slika:Domino green.svg|thumb|right|80px|[[1 (število)|Edina]] prosta [[domina (matematika)|domina]]]]
[[Slika:free trominoes 001.svg|thumb|right|120px|[[2 (število)|2]] prosti [[tromina|tromini]]]]
[[Slika:free tetrominoes.svg|thumb|right|[[5 (število)|5]] prostih [[tetromina|tetromin]]]]
[[Slika:free pentominos 001.svg|thumb|right|[[12 (število)|12]] prostih [[pentomina|pentomin]], pobarvanih glede na njihovo simetrijo]]
[[Slika:All 35 free hexominoes.svg|thumb|right|[[35 (število)|35]] prostih [[heksomina|heksomin]]]]
[[Slika:Heptominoes.svg|thumb|right|[[108 (število)|108]] prostih [[heptomina|heptomin]]]]
[[Slika:The 369 Free Octominoes.svg|thumb|right||[[369 (število)|369]] prostih [[oktomina|oktomin]]]]

'''Poliomína''' (tudi '''polinomína'''<ref>{{sktxt|Potočnik|2002}}.</ref>) je [[ravnina|ravninski]] [[geometrijski lik|lik]], ki ga sestavlja eden ali več [[skladnost (geometrija)|skladnih]] [[presek|neprekrivajočih se]] [[enotski kvadrat|enotskih]] [[kvadrat (geometrija)|kvadrat]]ov [[ortogonalnost|ortogonalno]] povezanih po [[stranica]]h. Je vrsta [[poliforma|poliforme]], katere celica je kvadrat. Lahko se jo šteje za končno [[podmnožica|podmožico]] pravilnega [[kvadratno pokritje|kvadratnega pokritja]] s [[povezani prostor|povezano]] [[notranjost (topologija)|notranjostjo]]. Naslednji liki:

[[Slika:Nontromino 001.svg|50px]] [[Slika:Nontromino 002.svg|50px]] [[Slika:Nontetromino 001.svg|60px]] [[Slika:Nontetromino 007.svg|60px]] [[Slika:Nontetromino 014.svg|60px]] [[Slika:Nontetromino 015.svg|60px]] [[Slika:Nonpolyomino 005.svg|70px]] [[Slika:Nonpolyomino 022.svg|70px]] [[Slika:Nonpolyomino 065.svg|70px]] [[Slika:Nonpolyomino 073.svg|70px]] [[Slika:Nonpolyomino 071.svg|70px]]

na primer niso poliomine, saj so vsaj enkrat povezani le z [[oglišče]]ma. Takšni liki, imenovani '''nepoliomine''', skupaj s prostimi poliominami tvorijo množico likov, imenovanih (prosti) [[poliplet]]i ali [[polikralj]]i, kjer je zadnje poimenovanje povezano s [[šah]]ovskimi [[šahovska figura|figurami]], [[kralj (šah)|kralj]]i. Polipleti se pojavljajo v [[Conwayjeva igra življenja|igri življenja]] [[John Horton Conway|Johna Hortona Conwayja]].

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

{| class="wikitable"
|-
! število <br /> celic !! ime !! število prostih <br /> poliomin do ''n'' <br /> {{OEIS|id=A130866}}
|- align=right
|  1 || align=left | [[monomina]]                         ||      1
|- align=right
|  2 || align=left | [[domina (matematika)|domina]]       ||      2
|- align=right
|  3 || align=left | [[tromina]], triomina ali trinomina  ||      4
|- align=right
|  4 || align=left | [[tetromina]]                        ||      9
|- align=right
|  5 || align=left | [[pentomina]] ali pentamina          ||     21
|- align=right
|  6 || align=left | [[heksomina]]                        ||     56
|- align=right
|  7 || align=left | [[heptomina]]                        ||    164
|- align=right
|  8 || align=left | [[oktomina]]                         ||    533
|- align=right
|  9 || align=left | [[nonomina]] ali eneomina            ||  1.818
|- align=right
| 10 || align=left | [[dekomina]]                         ||  6.473
|- align=right
| 11 || align=left | undekomina ali hendekomina           || 23.546
|- align=right
| 12 || align=left | dodekomina                           || 87.146
|}

Poliomine se pojavljajo v priljubljenih [[uganka]]h vsaj že od leta 1907, štetje pentomin pa izvira še iz antike.{{efn|Golomb (''Polyominoes'', predgovor k prvi izdaji) je zapisal: »opažanje, da obstaja dvanajst različnih vzorcev (pentomin), ki se jih lahko tvori iz petih povezanih kamenčkov na igralni deski za [[go]], ... se pripisuje starodavnemu mojstru te igre.«}} 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« ({{jezik-en|dissection problems}}), niso pa bili opaženi, ker so bili večinoma objavljeni v nepregledni kodirani obliki.<ref>{{sktxt|Jellis|1988}}.</ref> 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]]''.<ref>{{sktxt|Golomb|1994}}.</ref> Beseda poliomina izhaja iz [[stara grščina|starogrške]] besede {{jezik-el2|πολυ}}: poly - ''veliko'', iz polýs - ''mnog'', in domina.<ref>{{sktxt|Tavzes|2002|pp=900}}.</ref> Beseda domina verjetno izhaja iz pegaste široke maškaradne obleke ''domino'', iz [[latinščina|latinskega]] dominus - ''[[gospodar]]''.

S poliominami so povezani [[poliamant]]i, ki jih sestavljajo [[enakostranični trikotnik]]i; [[poliheks]]i, ki jih tvorijo pravilni [[šestkotnik]]i, in druge ravninske poliforme. Poliomine so posplošili na višje [[razsežnost]]i s spajanjem [[kocka|kock]] v [[polikocka|polikocke]], [[teserakt]]ov v [[politeserakt]]e ali [[hiperkocka|hiperkock]] v [[polihiperkocka|polihiperkocke]].

Kot pri mnogih ugankah v [[razvedrilna matematika|razvedrilni matematiki]] je s poliominami povezanih veliko [[kombinatorika|kombinatoričnih]] problemov, še posebej s področja [[geometrična kombinatorika|geometrične kombinatorike]]. 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 [[algoritem|algoritmi]] za njihovo računanje.

Poliomine z luknjami za nekatere primere niso primerne, na primer za probleme [[teselacija|pokrivanja]] ravnine. Včasih se takšne poliomine izključijo in so dovoljene le [[enostavno povezani prostor|enostavno povezane]].<ref>{{sktxt|Grünbaum|Shephard|1987}}.</ref>

== Štetje poliomin ==

=== Proste, enostranske in negibne poliomine ===

Pri štetju obstajajo trije običajni načini razlikovanja poliomin:<ref>{{sktxt|Redelmeier|1981}}.</ref><ref>{{sktxt|Golomb|1994|loc=§ 6}}.</ref>

* ''proste'' poliomine so različni liki, če noben ni transformacija ([[translacija (geometrija)|vzporedni premik]], [[vrtenje]], [[zrcaljenje]] ali [[drsna simetrija|drsno zrcaljenje]]) drugega (figure, ki se jih lahko vzame v roke in se jih obrne).
* ''enostranske'' poliomine se razlikujejo, kadar nobena ni vzporedno premaknjena ali zavrtena (figure, ki se jih ne da obrniti).
* ''negibne'' poliomine se razlikujejo, kadar nobena ni vzporedno premaknjena (figure, ki se jih ne da obrniti ali zasukati).

Naslednja razpredelnica prikazuje število poliomin različnih vrst z ''n'' celicami, ter poliplete. Naj <math>a_{n}</math> označuje število negibnih poliomin z ''n'' celicami (od katerih imajo lahko nekatere luknje).
{| class=wikitable
! rowspan="4" | ''n'' !! rowspan="4" | ime !! colspan="5"| poliomine !! nepoliomine !! colspan="3"| [[poliplet]]i
|-
! colspan="3" | proste !! rowspan="2"| enostranske !! rowspan="2" | negibne !! rowspan="2" | proste !! rowspan="2"| prosti !! rowspan="2" | enostranski !!rowspan="2"| negibni 
|-
! vse   !! z luknjami !! brez lukenj 
|-
! {{OEIS2|id=A000105}} !! {{OEIS2|id=A001419}} !! {{OEIS2|id=A000104}} !! {{OEIS2|id=A000988}} !! <math>a_n</math>,&nbsp;{{OEIS2|id=A001168}} !! {{OEIS2|id=A194596}} !! {{OEIS2|id=A030222}} !! {{OEIS2|id=A030233}} !! {{OEIS2|id=A006770}}
|- align=right
|  1 || align=left | [[monomina]]                   ||     [[1 (število)|1]] ||                 [[0]] ||                     1 ||                     1 ||                     1 || 0                     || 1                     ||                     1 ||                     1
|- align=right
|  2 || align=left | [[domina (matematika)|domina]] ||                     1 ||                     0 ||                     1 ||                     1 ||     [[2 (število)|2]] || 1                     || 2                     ||                     2 ||     [[4 (število)|4]]
|- align=right
|  3 || align=left | [[tromina]]                    ||                     2 ||                     0 ||                     2 ||                     2 ||     [[6 (število)|6]] || [[3 (število)|3]]     || 5                     ||                     6 ||   [[20 (število)|20]]
|- align=right
|  4 || align=left | [[tetromina]]                  ||     [[5 (število)|5]] ||                     0 ||                     5 ||     [[7 (število)|7]] ||   [[19 (število)|19]] || [[17 (število)|17]]   || [[22 (število)|22]]   ||   [[34 (število)|34]] || [[110 (število)|110]]
|- align=right
|  5 || align=left | [[pentomina]]                  ||   [[12 (število)|12]] ||                     0 ||                    12 ||   [[18 (število)|18]] ||   [[63 (število)|63]] || [[82 (število)|82]]   || [[94 (število)|94]]   || [[166 (število)|166]] || [[638 (število)|638]]
|- align=right
|  6 || align=left | [[heksomina]]                  ||   [[35 (število)|35]] ||                     0 ||                    35 ||   [[60 (število)|60]] || [[216 (število)|216]] || [[489 (število)|489]] || [[524 (število)|524]] || [[991 (število)|991]] ||                 3.832
|- align=right
|  7 || align=left | [[heptomina]]                  || [[108 (število)|108]] ||                     1 || [[107 (število)|107]] || [[196 (število)|196]] || [[760 (število)|760]] ||                 2.923 ||                 3.031 ||                 5.931 ||                23.592
|- align=right
|  8 || align=left | [[oktomina]]                   || [[369 (število)|369]] ||                     6 || [[363 (število)|363]] || [[704 (število)|704]] ||                     2.725 ||                18.401 ||                18.770 ||                37.196 ||               147.941
|- align=right
|  9 || align=left | [[nonomina]]                   ||                 1.285 ||   [[37 (število)|37]] ||                 1.248 ||                 2.500 ||                      9.910 ||               116.848 ||               118.133 ||               235.456 ||               940.982
|- align=right
| 10 || align=left | dekomina                       ||                 4.655 || [[195 (število)|195]] ||                 4.460 ||                 9.189 ||                     36.446 ||               753.726 ||               758.381 ||             1.514.618 ||             6.053.180
|- align=right
| 11 || align=left | undekomina                     ||                17.073 || [[979 (število)|979]] ||                16.094 ||                33.896 ||                   135.268 ||             4.898.579 ||             4.915.652 ||             9.826.177 ||            39.299.408
|- align=right
| 12 || align=left | dodekomina                     ||                63.600 ||                 4.663 ||                58.937 ||               126.759 ||                  505.861 ||            32.085.696 ||            32.149.296 ||            64.284.947 ||           257.105.146
|- align=right
| 13 || align=left | &nbsp;                         ||               238.591 ||                21.474 ||               217.117 ||               476.270 ||                1.903.890 ||           211.398.614 ||           211.637.205 ||           423.241.426 ||         1.692.931.066
|- align=right
| 14 || align=left | &nbsp;                         ||               901.971 ||                96.496 ||               805.475 ||             1.802.312 ||              7.204.874 ||         1.400.292.492 ||         1.401.194.463 ||         2.802.300.793 ||        11.208.974.860
|- align=right
| 15 || align=left | &nbsp;                         ||             3.426.576 ||               425.449 ||             3.001.127 ||             6.849.777 ||             27.394.666 ||         9.318.028.028 ||         9.321.454.604 ||        18.642.694.440 ||        74.570.549.714
|- align=right
| 16 || align=left | &nbsp;                         ||            13.079.255 ||             1.849.252 ||            11.230.003 ||            26.152.418 ||           104.592.937 ||        62.259.251.309 ||        62.272.330.564 ||       124.544.085.550 ||       498.174.818.986
|- align=right
| 17 || align=left | &nbsp;                         ||            50.107.909 ||             7.946.380 ||            42.161.529 ||           100.203.194 ||          400.795.844 ||       417.496.576.187 ||       417.546.684.096 ||       835.091.956.750 ||     3.340.366.308.393
|- align=right
| 18 || align=left | &nbsp;                         ||           192.622.052 ||            33.840.946 ||           158.781.106 ||           385.221.143 ||        1.540.820.542 ||       &nbsp;          ||       &nbsp;          ||       &nbsp;          ||     &nbsp;
|- align=right
| 19 || align=left | &nbsp;                         ||          742.624.232  ||           143.060.339 ||           599.563.893 ||         1.485.200.848 ||      5.940.738.676 ||       &nbsp;          ||       &nbsp;          ||       &nbsp;          ||     &nbsp;
|- align=right
| 20 || align=left | &nbsp;                         ||        2.870.671.950  ||           601.165.888 ||         2.269.506.062 ||         5.741.256.764 ||     22.964.779.660 ||       &nbsp;          ||       &nbsp;          ||       &nbsp;          ||     &nbsp;
|}

[[Iwan Jensen|Jensen]] je preštel negibne poliomine do ''n'' = 56: <math>a_{56}</math> je približno 6,915{{e|31}}.<ref>{{sktxt|Jensen|2009}}.</ref> Proste poliomine do ''n'' = 28 je preštel Tomás Oliveira e Silva.<ref>{{sktxt|Oliveira e Silva|2015}}.</ref> V splošnem pa je problem štetja poliomin [[nerešeni matematični problemi|nerešen]].

=== Simetrije poliomin ===

[[Diedrska grupa]] <math>D_{4}</math> je [[grupa]] [[simetrija|simetrij]] ([[simetrijska grupa]]) kvadrata. Ta grupa vsebuje štiri zasuke in štiri zrcaljenja. Tvori se jo z izmeničnim zrcaljenjem prek osi ''x'' in prek [[diagonala|diagonale]]. Ena prosta poliomina odgovarja največ 8. negibnim poliominam, ki so njene podobe pod simetrijo <math>D_{4}\, </math>. 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 <math>D_{4}\, </math>, odgovarja le 4., 2. ali 1. negibni poliomini. Matematično gledano so proste poliomine [[ekvivalenčni razred]]i negibnih poliomin pod grupo <math>D_{4}\, </math>.

Za poliomine lahko obstajajo naslednje simetrije.<ref name="Redelmeier (1981), section 3">{{sktxt|Redelmeier|1981|loc=§ 3}}.</ref> 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: <math>C_{2}\, </math> (4)
* 2 negibni poliomini za vsako prosto poliomino:
** simetrija glede na smeri obeh mrežnih črt, dve osi osne simetrije: <math>D_{2}\, </math>&nbsp;(90°) (2)
** simetrija glede na smeri obeh diagonal, dve osi osne simetrije: <math>D_{2}\, </math>&nbsp;(45°) (7)
** rotacijska simetrija reda 4: <math>C_{4}\, </math> (8)
* 1 negibna poliomina za vsako prosto poliomino:
** vse simetrije kvadrata: <math>D_{4}\, </math> (1).

Naslednja razpredelnica prikazuje število poliomin z ''n'' celicami, glede na simetrijske grupe, in z enojnimi luknjami. 
{| class=wikitable
! ''n'' !! brez simetrije <br /> ({{OEIS2|id=A006749}}) !! zrcaljenje&nbsp;(90°) <br /> ({{OEIS2|id=A006746}}) !! zrcaljenje&nbsp;(45°) <br /> ({{OEIS2|id=A006748}}) !! <math>C_{2}\, </math> <br /> ({{OEIS2|id=A006747}}) !! <math>D_{2}\, </math>&nbsp;(90°) <br /> ({{OEIS2|id=A056877}}) !! <math>D_{2}\, </math>&nbsp;(45°) <br /> ({{OEIS2|id=A056878}}) !! <math>C_{4}\, </math> <br /> ({{OEIS2|id=A144553}}) !! <math>D_{4}\, </math> <br /> ({{OEIS2|id=A142886}}) !! &nbsp; <br /> ({{OEIS2|id=A001419}})
|-
| || [[Slika:Polyomino simmetry 001.svg|60px]] || [[Slika:Polyomino simmetry 002.svg|60px]] || [[Slika:Polyomino simmetry 003.svg|60px]] || [[Slika:Polyomino simmetry 004.svg|60px]] || [[Slika:Polyomino simmetry 005.svg|60px]] || [[Slika:Polyomino simmetry 006.svg|60px]] || [[Slika:Polyomino simmetry 007.svg|60px]] || [[Slika:Polyomino simmetry 008.svg|60px]] || [[Slika:Heptomino with hole.svg|50px]]
|- align=right
|  1 ||                 [[0]] ||      0 ||      0 ||      0 ||   0 ||  0 ||  0 ||  1 ||           0
|- align=right
|  2 ||                     0 ||      0 ||      0 ||      0 ||   1 ||  0 ||  0 ||  0 ||           0
|- align=right
|  3 ||                     0 ||      0 ||      1 ||      0 ||   1 ||  0 ||  0 ||  0 ||           0
|- align=right
|  4 ||     [[1 (število)|1]] ||      1 ||      0 ||      1 ||   1 ||  0 ||  0 ||  1 ||           0
|- align=right
|  5 ||     [[5 (število)|5]] ||      2 ||      2 ||      1 ||   1 ||  0 ||  0 ||  1 ||           0
|- align=right
|  6 ||   [[20 (število)|20]] ||      6 ||      2 ||      5 ||   2 ||  0 ||  0 ||  0 ||           0
|- align=right
|  7 ||   [[84 (število)|84]] ||      9 ||      7 ||      4 ||   3 ||  1 ||  0 ||  0 ||           1
|- align=right
|  8 || [[316 (število)|316]] ||     23 ||      5 ||     18 ||   4 ||  1 ||  1 ||  1 ||           6
|- align=right
|  9 ||                 1.196 ||     38 ||     26 ||     19 ||   4 ||  0 ||  0 ||  2 ||          37
|- align=right
| 10 ||                 4.461 ||     90 ||     22 ||     73 ||   8 ||  1 ||  0 ||  0 ||         195
|- align=right
| 11 ||                16.750 ||    147 ||     91 ||     73 ||  10 ||  2 ||  0 ||  0 ||         979
|- align=right
| 12 ||                62.878 ||    341 ||     79 ||    278 ||  15 ||  3 ||  3 ||  3 ||       4.663
|- align=right
| 13 ||               237.394 ||    564 ||    326 ||    283 ||  17 ||  3 ||  2 ||  2 ||      21.474
|- align=right
| 14 ||               899.265 ||  1.294 ||    301 ||  1.076 ||  30 ||  5 ||  0 ||  0 ||      96.496
|- align=right
| 15 ||             3.422.111 ||  2.148 ||  1.186 ||  1.090 ||  35 ||  6 ||  0 ||  0 ||     425.449
|- align=right
| 16 ||            13.069.026 ||  4.896 ||  1.117 ||  4.125 ||  60 || 14 || 12 ||  5 ||   1.849.252
|- align=right
| 17 ||            50.091.095 ||  8.195 ||  4.352 ||  4.183 ||  64 ||  9 ||  7 ||  4 ||   7.946.380
|- align=right
| 18 ||           192.583.152 || 18.612 ||  4.212 || 15.939 || 117 || 20 ||  0 ||  0 ||  33.840.946
|- align=right
| 19 ||           742.560.511 || 31.349 || 16.119 || 16.105 || 128 || 20 ||  0 ||  0 || 143.060.339
|- align=right
| 20 ||         2.870.523.142 || 70.983 || 15.849 || 61.628 || 236 || 56 || 44 || 12 || 601.165.888
|}

=== Algoritmi za štetje negibnih poliomin ===
==== Induktivni algoritmi ====

Vsako poliomino reda ''n'' + 1 se lahko dobi z dodajanjem celice k poliomini reda ''n''. Od tod izhajajo [[Matematična indukcija|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 se jo je že našlo. Izboljšave pri urejevanju štetja in označevanje sosednjih kvadratov, ki se jih ne bi smelo upoštevati, zmanjšajo število potrebnih primerov za preverjanje dvojnikov.<ref>{{sktxt|Golomb|1994|pp=73-79}}.</ref> 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 se začne z enim samim kvadratom, in se od tod [[rekurzija|rekurzivno]] dodaja kvadrate. Odvisno od podrobnosti se lahko šteje vsako ''n''-omino ''n''-krat, enkrat od začetka vsakega njenega ''n''-tega kvadrata, ali pa se jih šteje vsako enkrat.

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

Pri štetju prostih poliomin je treba 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 [[Burnsideova lema|Burnsideovo lemo]].<ref>{{sktxt|Redelmeier|1981|loc=§ 4 in § 6}}.</ref>

==== Metoda s prenosno matriko ====

Najsodobnejši algoritem za štetje negibnih poliomin je odkril Iwan Jensen.<ref>{{sktxt|Jensen|2001}}.</ref> Izboljšava metode [[Andrew Conway|Andrewa Conwayja]] je [[eksponentna funkcija|eksponentno]] hitrejša od predhodnih metod, čeprav je čas njenega izvajanja še vedno eksponeneten v ''n''.<ref>{{sktxt|Conway|1995}}.</ref>

Conwayjeva in Jensenova različica metode s [[prenosna matrika|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 [[rodovna funkcija|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č [[gigabajt|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:

: <math> a_{n} \sim \frac{c\lambda_{2}^{n}}{n} \!\, , </math>

kjer sta <math>\lambda_{2} = 4,0626\, </math> in <math>c = 0,3169\, </math>.<ref>{{sktxt|Jensen|Guttmann|2000}}.</ref> Vendar ta rezultat ni [[matematični dokaz|dokazan]], tako da sta vrednosti <math>\lambda_{2}\, </math> in ''c'' le oceni. Znani teoretični rezultati niso niti približno tako določeni kot ta ocena. Dokazano je, da obstaja limita:

: <math> \lim_{n\rightarrow \infty} (a_{n})^{1/n} = \lambda_{2} \!\, . </math>

Vrednost <math>a_{n}\, </math> [[eksponentna rast|raste eksponentno]] in je približno enaka:<ref>{{sktxt|Demaine|O'Rourke|2001}}.</ref>

: <math> a_{n} \sim n^{\lambda_{2}} \!\, . </math>

Najboljša znana spodnja meja za <math>\lambda_{2}</math> je 3,980137.<ref>{{sktxt|Barequet|Moffie|Ribó|Rote|2006}}.</ref> Najboljša znana zgornja meja, neizboljšana še od 1970-ih, je <math>\lambda_{2} < 4,65</math>.<ref>{{sktxt|Klarner|Rivest|1973}}.</ref> <math>\lambda_{2}\, </math> se imenuje Klarnerjeva konstanta.

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 velikosti ''m'', s čimer se dobi edina (''n''+''m'')-omina. To dokazuje <math>a_{n}a_{m} \le a_{n+m}\, </math>. S pomočje te enačbe se lahko pokaže, da velja <math>\lambda \ge (a_{n})^{1/n}\, </math> za vse ''n''. Ta prečiščen postopek skupaj s podatki za <math>a_{n}\, </math> da zgornjo spodnjo mejo.

Zgornja meja se dobi s posplošitvijo induktivne metode za štetje poliomin. Namesto, da se dodaja po en kvadrat na enkrat, se dodaja 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 je treba na primer v vsakem koraku izbrati večje število, doda pa se 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 [[David Anthony Klarner|Klarner]] in [[Ronald Rivest|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.<ref name="Redelmeier (1981), section 3"  />

=== Posebni razredi poliomin ===

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

==== Konveksnost in usmerjenost ====

Definicija konveksne poliomine se razlikuje od običajne definicije [[konveksna množica|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..<ref name=W151>{{sktxt|Wilf|1994|pp=151}}.</ref>

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 se zapustilo 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 sta npr. obseg (polobseg) ali minimalni omejitveni pravokotnik, s pomočjo [[rodovna funkcija|rodovnih funkcij]].<ref>{{sktxt|Bousquet-Mélou|1998}}.</ref><ref>{{sktxt|Delest|1988}}.</ref><ref>{{sktxt|Bousquet-Mélou|Fédou|1995}}.</ref><ref>{{sktxt|Guo|Zeng|2004}}.</ref>

Pri konveksnih poliominah je polobseg enak vsoti njihovih stolpcev in vrstic.<ref name="del_lungo_2004">{{sktxt|Del Lungo|Duchi|Frosini|Rinaldi|2004}}.</ref> Število konveksnih poliomin <math>f_{n}\, </math> s polobsegom <math>n+2\, </math> sta določila Delest in Viennot:<ref>{{sktxt|Delest|Viennot|1984}}.</ref><ref name="del_lungo_2004" /><ref name="bernini_2007">{{sktxt|Bernini|Disanto|Pinzani|Rinaldi|2007}}.</ref>

: <math> f_{n+2} = (2n+11)4^{n} - 4(2n+1) {2n\choose n}, \qquad (n \ge 0; \qquad f_{0} = 1, \qquad f_{1} = 2) \!\, . </math>

Prve vrednosti za ''n'' ≥ 0 so {{OEIS|id=A005436}}:

: 1, 2, 7, 28, 120, 528, 2344, 10416, 46160, 203680, 894312, 3907056, ... .

Število usmerjenih konveksnih poliomin <math>b_{n}\, </math> s polobsegom <math>n+2\, </math> je enako ''n''-temu [[središčni binomski koeficient|središčnemu]] [[binomski koeficient|binomskemu koeficientu]]:<ref name="del_lungo_2004" /><ref name="bernini_2007" />
[[Slika:Young diagram for 541 partition.svg|thumb|right|150px|[[Youngov diagram]] za [[particija (teorija števil)|particijo]] (5,4,1)]]

: <math> b_{n+2} = {2n\choose n} = \frac{(2n)!}{(n!)^{2}} \!\, . </math>

Prve vrednosti za ''n'' ≥ 0 so {{OEIS|id=A000984}}:

: 1, 2, 6, 20, 70, 252, 924, 3432, 12870, 48620, 184756, 705432, ... .

[[Youngov diagram|Youngovi diagrami]] (tudi [[Ferrersov diagram|Ferrersovi diagrami]]) so konveksne poliomine pri katerih so vrstice poravnane levo in dolžine vrstic šibko naraščajo (vsaka vrstica ima enako ali manjšo dolžino kot predhodnja).<ref>{{sktxt|Björner|Stanley|2010|pp=36}}.</ref> Število enostranskih Youngovih diagramov je enako številu [[particija (teorija števil)|particij]] pozitivnega celega števila. Prve vrednosti za ''n'' ≥ 0 so {{OEIS|id=A000041}}: 

: 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, ... .

Po dogovoru je ''p''(0) = 1 in ''p''(''n'') = 0 za negativne ''n''.

Posebna podmnožica usmerjenih konveksnih poliomin so ''paralelogramske poliomine''. Definirane so z dvema potema na mreži z enotskimi koraki gor (sever) (0,1) in korak desno (vzhod) (1,0), ki se sekata le v svojima izhodiščema in krajiščima. Število paralelogramskih poliomin <math>c_{n}\, </math> s polobsegom <math>n+1\, </math> je enako ''n''-temu [[catalanovo število|Catalanovemu številu]]:<ref>{{sktxt|Stanley|1999}}.</ref><ref>{{sktxt|Aval|Bouvel|Boussicault|Silimbani|2013}}.</ref><ref>{{sktxt|Leroux|Rassart|2000}}.</ref>

: <math> c_{n+1} = \frac{1}{n+1} {2n\choose n} = \frac{(2n)!}{n! \; (n+1)!}  \!\, . </math>

Prve vrednosti za ''n'' ≥ 0 so {{OEIS|id=A000108}}:

: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, ... .

==== Enakoličnost ====

Poliomina je [[enakolični lik|enakolična]], če je njena površina enaka njenemu obsegu. Enakolično poliomino mora sestavljati [[sodo število]] kvadratov. Možno je vsako sodo število večje od 15. 16-omina v obliki kvadrata 4 × 4 in 18-omina v obliki pravokotnika 3 × 6 sta na primer obe enakolični. Za poliomine z manj kot 15-imi kvadrati je obseg vedno večji od površine.<ref>{{sktxt|Picciotto|1999|pp=208}}.</ref>

== Rabe poliomin ==

Poliomine so pospešile raziskave v [[računalništvo|računalništvu]] in razvedrilni matematiki. Problemi se velikokrat nanašajo na pokritje ([[teselacija|tlakovanje]]) določenega območja ali celotne ravnine s poliominami ali pregibanje poliomin za tvorjenje drugih oblik.<ref>{{sktxt|Martin|1996}}.</ref> Gardner je predlagal več preprostih iger z množico prostih pentomin in [[šahovnica|šahovnico]]. Nekatere različice [[sestavljanka|sestavljanke]] [[sudoku]] imajo območja v obliki poliomin na mreži. [[Računalniška igra]] ''[[Tetris]]'' temelji na sedmih enostranskih tetrominah. V igri so imenovane »tetrimine«. [[Igra na deski]] ''[[Blokus]]'' uporablja vseh 21 prostih poliomin vse do pentomin.

=== Pokritje območij z množico poliomin ===

V sestavljankah je običajno treba pokriti dano območje z dano množico poliomin, kot na primer 12 prostih pentomin. Golombova in Gardnerjeva knjiga imata veliko zgledov. Tipična sestavljanka je pokritje pravokotnika 6 × 10 z 12-imi prostimi pentominami. Vseh 2339 rešitev sta leta 1960 prva našla. [[Colin Brian Haselgrove|Colin]] in [[Jenifer Haselgrove]].<ref>{{sktxt|Haselgrove|Haselgrove|1960}}.</ref>

Če so dovoljene mnogokratne kopije poliomin v množici, je Golomb definiral hierarhijo različnih območij, ki jih lahko množica pokrije, kot na primer pravokotniki, trakovi in celotna ravnina. Pokazal je, da je problem pokritja ravnine s poliominami iz dane množice [[rekurzivna množica|
neodločljiv]] s [[preslikava|preslikavnimi]] množicami [[Wangovo pokritje|Wangovih tlakovcev]] v množice poliomin.<ref>{{sktxt|Golomb|1970}}.</ref>

=== Pokritje območij s kopijami ene poliomine ===

V drugem razredu problemov je vprašanje ali kopije dane poliomine pokrijejo [[pravokotnik]], in če, katere pravokotnike lahko.<ref>{{sktxt|Golomb|1994|loc=§8}}.</ref> Takšne probleme so še posebej obsežno raziskovali za določene poliomine.<ref>{{sktxt|Reid|2011}}.</ref> Na voljo so razpredelnice rezultatov za posamezne poliomine.<ref>{{sktxt|Reid|2005}}.</ref> Klarner in Göbel sta pokazala, da za vsako poliomino obstaja končna množica takšnih ''prvotnih'' pravokotnikov, ki jih pokrije, da se lahko vsi drugi pravokotniki, ki jih pokrije, pokrijejo s temi prvotnimi pravokotniki.<ref>{{sktxt|Klarner|Göbel|1969}}.</ref><ref>{{sktxt|Klarner|1973}}.</ref>

Poleg pravokotnikov je Golomb podal svojo hierarhijo za posamezne poliomine: poliomina lahko pokrije pravokotnik, [[poltrak]], ukrivljeni trak, povečano lastno kopijo, [[kvadrant]], trak, [[polravnina|polravnino]], celotno ravnino, določene kombinacije ali nič od tega. Med njimi sta določeni posledici, obe očitni. Če na primer poliomina pokrije polravnino, pokrije tudi celotno ravnino. In, če poliomina pokrije povečano lastno kopijo, potem pokrije kvadrant. Poliomine do reda vse do 6 so karakterizirane v tej hierarhiji s statusom ene heksamine, za katero se je kasneje izkazalo, da pokrije pravokotnik, kar je bilo do tedaj nerešeno.<ref>{{sktxt|Golomb|1966}}.</ref>

Leta 2001 sta [[Cristopher Moore]] in John Michael Robson pokazala, da je problem pokritja ene poliomine s kopijami druge [[NP-polnost|NP-poln]].<ref>{{sktxt|Moore|Robson|2001}}.</ref><ref>{{sktxt|Petersen|1999}}.</ref>

=== Pokritje ravnine s kopijami ene poliomine ===
[[Slika:Conway criterion false negative nonominoes.svg|thumb|right|Dve pokrivajoči [[nonomina|nonomini]] za kateri [[Conwayjev kriterij]] ne velja.]]

Veliko so obravnavali tudi pokritje ravnine s kopijami ene poliomine. Leta 1965 so oznanili, da vse poliomine do heksomin in vse razen štirih heptomin pokrijejo ravnino.<ref>{{sktxt|Gardner|1965a}}.</ref><ref>{{sktxt|Gardner|1965b}}.</ref> Nato je David Bird ugotovil, da vse razen 26 oktomin pokrijejo ravnino.<ref>{{sktxt|Gardner|1975}}.</ref> Rawsthorne je odkril, da vse nonomine razen 235-ih pokrijejo ravnino.<ref>{{sktxt|Rawsthorne|1988}}.</ref> Takšne rezultate so razširili na višje rede Rhoads (do reda 14) in drugi.<ref>{{sktxt|Rhoads|2003}}.</ref> Poliomine, ki pokrivajo ravnino, so klasificirali po simetrijah njihovih pokritij in po številu aspektov (orientacij) v katerih se tlakovci pojavljajo v njih.<ref>{{sktxt|Grünbaum|Shephard|1987|loc=§ 9.4}}.</ref><ref>{{sktxt|Keating|Vince|1999}}.</ref>

Raziskovanje katere poliomine lahko pokrijejo ravnino je olajšala raba [[Conwayjeve kriterij|Conwayjevega kriterija]]. Razen dveh nonomin vse pokrivajoče poliomine do reda 9 tvorijo zaplato, za katero velja vsaj en tlakovec, pri čemer so izjeme pri višjih redovih pogostejše.<ref>{{sktxt|Rhoads|2005}}.</ref>

Več poliomin lahko [[množica ploščic s samopokritjem|pokrije več lastnih kopij]] in ponavljanje tega procesa rekurzivno da pokritje ravnine z [[delilna ploščica|delilnimi ploščicami]] (''rep-tile''). Za vsako pozitivno celo število ''n'' se na primer lahko skombinira ''n''<sup>2</sup> kopij L-tromine, L-tetromine ali P-pentomine v en večji lik podoben manjši poliomini iz katere je bil oblikovan.<ref>{{sktxt|Niţică|2003|pp=205–217.}}</ref>

=== Pokritje skupnega lika z različnimi poliominami ===
[[Slika:PentominoCompatibilityTW.svg|thumb|right|220px|Minimalni združljivostni lik za [[pentomina|pentomini]] T in W.]]

''Problem združljivosti'' išče lik, ki ga lahko pokrijeta dve ali več poliomin. Poliominsko združljivost so veliko raziskovali od 1990-ih. Jorge Luis Mireles in Giovanni Resta sta objavila spletni strani s sistematičnimi rezultati.<ref>{{sktxt|Mireles|2003}}.</ref><ref>{{sktxt|Resta|2009}}.</ref> Livio Zucca prikazuje rezultate za nekatere zapletene primere, kot so na primer tri različne pentomine.<ref>{{sktxt|Zucca|2014}}.</ref> Splošni problem je lahko težek. Prvi združljivostni lik za pentomini L in X je bil objavljen leta 2005 in ima  80 poliomin obeh vrst.<ref>{{sktxt|Barbans|Cibulis|Lee|Liu|2005}}.</ref> Za veliko parov poliomin so pokazali nezdružljivost s sistematičnim izčrpavanjem. Ni znan noben algoritem za odločanje ali so poljubne poliomine združljive.

=== Mreže teles ===
[[Slika:The 11 cubic nets.svg|thumb|right|220px|11 različnih prostih [[heksomina|heksomin]] predstavlja [[mreža telesa|mrežo]] [[kocka|kocke]]]]

Od poliomin lahko edino heksomine predstavljajo [[mreža telesa|mrežo telesa]] in sicer [[kocka|kocke]]. Od 35 prostih heksomin jih lahko 11 predstavlja mrežo kocke.

== Glej tudi ==

* [[teorija perkolacije]]
* [[Youngov diagram]]
* [[Blokus]]
* [[kvadratni graf]]
* [[permutomina]]

== Opombe ==

{{notelist}}

== Sklici ==

{{sklici|3}}

== Viri ==

{{refbegin|2}}
* {{citat|last1= Aval|first1= Jean-Christophe|last2= Bouvel|first2= Mathilde|last3= Boussicault|first3= Adrien|last4= Silimbani|first4= Matteo|title= Combinatorics of non-ambiguous trees|journal= [[Discrete Mathematics & Theoretical Computer Science|Discrete Mathematics and Theoretical Computer Science]]|date= 2013|volume= AS|issue= |pages= 49–60|url= http://www.dmtcs.org/pdfpapers/dmAS0105.pdf|accessdate= 2016-04-30|archive-date= 2016-06-04|archive-url= https://web.archive.org/web/20160604003940/http://www.dmtcs.org/pdfpapers/dmAS0105.pdf|url-status= dead}}
* {{citat|last1= Barbans|first1= Uldis|last2= Cibulis|first2= Andris|last3= Lee|first3= Gilbert|last4= Liu|first4= Andy|last5= Wainwright|first5= Robert|contribution= Polyomino Number Theory (III)|editor-last1= Cipra|editor-first1= Barry|editor-link1= Barry Arthur Cipra|editor-last2= Demaine|editor-first2= Erik D.|editor-last3= Demaine|editor-first3= Martin L.|editor-last4= Rodgers|editor-first4= Tom|title= Tribute to a Mathemagician|location= Wellesley, MA|publisher= A.K. Peters|date= 2005|pages= 131–136|isbn= 978-1-56881-204-5}}
* {{citat|last1= Barequet|first1= Gill|last2= Moffie|first2= Micha|last3= Ribó|first3= Ares|last4= Rote|first4= Günter|title= Counting polyominoes on twisted cylinders|journal= [[Integers]]|date= 2006|volume= 6|issue= |pages= #A22}}
* {{citat|last1= Bernini|first1= Antonio|last2= Disanto|first2= Filippo|last3= Pinzani|first3= Renzo|last4= Rinaldi|first4= Simone|title= Permutations Defining Convex Permutominoes|journal= [[Journal of Integer Sequences]]|date= 2007|volume= 10|issue= |pages= #07.9.7|url= http://www.emis.ams.org/journals/JIS/VOL10/Rinaldi/rinaldi5.pdf|accessdate= 2016-04-30|archive-date= 2016-03-04|archive-url= https://web.archive.org/web/20160304113330/http://www.emis.ams.org/journals/JIS/VOL10/Rinaldi/rinaldi5.pdf|url-status= dead}}
* {{citat|last1= Björner|first1= Anders|last2= Stanley|first2= Richard P.|date= 2010|title= A Combinatorial Miscellany|url= http://www-math.mit.edu/~rstan/papers/comb.pdf}}
* {{citat|last1= Bousquet-Mélou|first1= Mireille|last2= Fédou|first2= Jean-Marc|title= The generating function of convex polyominoes: The resolution of a ''q''-differential system|journal= [[Discrete Mathematics]]|date= 1995|volume= 137|issue= 1–3|pages= 53–75|doi= 10.1016/0012-365X(93)E0161-V}}
* {{citat|last1= Bousquet-Mélou|first1= Mireille|title= New enumerative results on two-dimensional directed animals|journal= Discrete Mathematics|date= 1998|volume= 180|issue= 1–3|pages= 73–106|doi= 10.1016/S0012-365X(97)00109-X}}
* {{citat|last1= Conway|first1= Andrew|authorlink1= Andrew Conway|title= Enumerating 2D percolation series by the finite-lattice method: theory|journal= [[Journal of Physics]]. A. Mathematical and General|date= 1995|volume= 28|issue= 2|pages= 335–349|doi= 10.1088/0305-4470/28/2/01}}
* {{citat|last1= Del Lungo|first1= A.|last2= Duchi|first2= E.|last3= Frosini|first3= A.|last4= Rinaldi|first4= Simone|title= On the generation and enumeration of some classes of convex polyominoes|journal= [[Electronic Journal of Combinatorics]]|date= 2004|volume= 11|issue= |pages= #R60|url= ftp://ftp.gwdg.de/pub/EMIS/journals/EJC/Volume_11/PostScriptfiles/v11i1r60.ps|format= [[postscript|PS]]}}{{Slepa povezava|date=maj 2024 |bot=InternetArchiveBot |fix-attempted=yes }}
* {{citat|last1= Delest|first1= Marie-Pierre|title= Generating functions for column-convex polyominoes|journal= [[Journal of Combinatorial Theory]]. Series A|date= 1988|volume= 48|issue= 1|pages= 12–31|doi= 10.1016/0097-3165(88)90071-4}}
* {{citat|last1= Delest|first1= Marie-Pierre|last2= Viennot|first2= Gérard|title= Algebraic languages and polyominoes enumeration|journal= [[Theoretical Computer Science]]|date= 1984|volume= 34|issue= |pages= 169–206|doi= 10.1016/0304-3975(84)90116-6}}
* {{citat|last1= Demaine|first1= Erik D.|last2= O'Rourke|first2= Joseph|url= http://maven.smith.edu/~orourke/TOPP/P37.html|title= Problem 37: Counting Polyominoes|work= The Open Problems Project|date= 2001-11-30|accessdate= 2011-08-31|language= en|archive-date= 2011-09-12|archive-url= https://web.archive.org/web/20110912193624/http://maven.smith.edu/~orourke/TOPP/P37.html|url-status= dead}}
* {{citat|last1= Feretić|first1= Svjetlan|title= A new way of counting the column-convex polyominoes by perimeter|journal= Discrete Mathematics|date= februar 1998|volume= 180|issue= 1–3|pages= 173–184|doi= 10.1016/S0012-365X(97)00114-3}}
* {{citat|last1= Gardner|first1= Martin|authorlink1= Martin Gardner|title= On the relation between mathematics and the ordered patterns of Op art|journal= [[Scientific American]]|date= julij 1965|volume= 213|issue= 1|pages= 100–104}}
* {{citat|last1= Gardner|first1= Martin|authorlink1= |title= Thoughts on the task of communication with intelligent organisms on other worlds|journal= Scientific American|date= avgust 1965|volume= 213|issue= 2|pages= 96–100}}
* {{citat|last1= Gardner|first1= Martin|authorlink1= |title= More about tiling the plane: the possibilities of polyominoes, polyiamonds and polyhexes|journal= Scientific American|date= avgust 1975|volume= 233|issue= 2|pages= 112–115}}
* {{citat|last1= Golomb|first1= Solomon Wolf|authorlink1= Solomon Wolf Golomb|title= Tiling with Polyominoes|journal= Journal of Combinatorial Theory|date= 1966|volume= 1|issue= 2|pages= 280–296|doi= 10.1016/S0021-9800(66)80033-9}}
* {{citat|last1= Golomb|first1= Solomon Wolf|authorlink1= |title= Tiling with Sets of Polyominoes|journal= Journal of Combinatorial Theory|date= 1970|volume= 9|issue= 1|pages= 60–71|doi= 10.1016/S0021-9800(70)80055-2}}
* {{citat|last1= Golomb|first1= Solomon Wolf|authorlink1= |title= Polyominoes|date= 1994|publisher= Princeton University Press|location= Princeton, New Jersey|isbn= 0-691-02444-8|edition=2.}}
* {{citat|last1= Grünbaum|first1= Branko|authorlink1= Branko Grünbaum|last2= Shephard|first2= Geoffrey Colin|authorlink2= Geoffrey Colin Shephard|title= Tilings and Patterns|location= New York|publisher= W. H. Freeman and Company|date= 1987|isbn= 0-7167-1193-1|cobiss= 39467777}}
* {{citat|last1= Guo|first1= Victor J. W.|last2= Zeng|first2= Jiang|title= The Number of Convex Polyominoes and the Generating Function of Jacobi Polynomials|date= 2004-03-16|arxiv= math/0403262}}
* {{citat|last1= Haselgrove|first1= Colin Brian|authorlink1= Colin Brian Haselgrove|last2= Haselgrove|first2= Jenifer|authorlink2= Jenifer Haselgrove|date= oktober 1960|title= A Computer Program for Pentominoes|journal= [[Eureka (revija Univerze v Cambridgeu)|Eureka]]|volume= 23|pages= 16–18}}
* {{citat|last1= Jelliss|first1= George Peter|url= http://www.mayhematics.com/d/db.htm|title= Dissection Problems in PFCS/FCR|date= 1988|accessdate= 2011-08-30|language= en}}
* {{citat|last1= Jensen|first1= Iwan|authorlink1= Iwan Jensen|last2= Guttmann|first2= Anthony John|authorlink2= Anthony John Guttmann|title= Statistics of lattice animals (polyominoes) and polygons|journal= [[Journal of Physics]]. A. Mathematical and General|date= 2000|volume= 33|issue= |pages= L257–L263|doi= 10.1088/0305-4470/33/29/102}}
* {{citat|last1= Jensen|first1= Iwan|date= februar 2001|title= Enumerations of Lattice Animals and Trees|journal= [[Journal of Statistical Physics]]|volume= 102|issue= 3–4|pages= 865–881|doi= 10.1023/A:1004855020556|arxiv= cond-mat/0007239}}
* {{citat|last1= Jensen|first1= Iwan|url= http://www.ms.unimelb.edu.au/~iwan/animals/Animals_ser.html|title= Series for lattice animals or polyominoes|date= 2009-04-11|accessdate= 2007-05-06|language= en|archive-date= 2007-06-12|archive-url= https://web.archive.org/web/20070612141716/http://www.ms.unimelb.edu.au/~iwan/animals/Animals_ser.html|url-status= dead}}
* {{citat|last1= Keating|first1= K.|last2= Vince|first2= A.|title= Isohedral Polyomino Tiling of the Plane|journal= Discrete &amp; Computational Geometry|date= 1999|volume= 21|issue= 4|pages= 615–630|doi=10.1007/PL00009442}}
* {{citat|last1= Klarner|first1= David Anthony|authorlink1= David Anthony Klarner|title= Some Results Concerning Polyominoes|journal= [[Fibonacci Quarterly]]|date= 1965|volume= 3|issue= 1|pages= 9–20|url= http://www.fq.math.ca/Scanned/3-1/klarner.pdf|format= PDF|accessdate= 2011-08-31}}
* {{citat|last1= Klarner |first1= David Anthony|last2= Göbel|first2= F.|title= Packing boxes with congruent figures|journal= [[Indagationes Mathematicae]]|date= 1969|volume= 31|issue= |pages= 465–472}}
* {{citat|last1= Klarner |first1= David Anthony|title= Packing a Rectangle with Congruent N-ominoes|journal= Journal of Combinatorial Theory|date= 1969|volume= 7|issue= 2|pages= 107-115|doi= 10.1016/S0021-9800(69)80044-X}}
* {{citat|last1= Klarner|first1= David Anthony|url= http://historical.ncstrl.org/litesite-data/stan/CS-TR-73-338.pdf|title= A Finite Basis Theorem Revisited|accessdate= 2007-05-12|date= februar 1973|format= PDF|publisher= Stanford University Technical Report STAN-CS-73–338|archive-date= 2007-10-23|archive-url= https://web.archive.org/web/20071023221204/http://historical.ncstrl.org/litesite-data/stan/CS-TR-73-338.pdf|url-status= dead}}
* {{citat|last1= Klarner|first1= David Anthony|last2= Rivest|first2= Ronald Linn|authorlink2= Ronald Rivest|title= A procedure for improving the upper bound for the number of ''n''-ominoes|journal= [[Canadian Journal of Mathematics]]|date= 1973|volume= 25|issue= |pages= 585–602|url= http://historical.ncstrl.org/litesite-data/stan/CS-TR-72-263.pdf|format= različica tehniškega poročila PDF|accessdate= 2007-05-11|archive-date= 2006-11-26|archive-url= https://web.archive.org/web/20061126083002/http://historical.ncstrl.org/litesite-data/stan/CS-TR-72-263.pdf|url-status= dead}}
* {{citat|last1= Leroux|first1= Pierre|last2= Rassart|first2= Etienne|title= Enumeration of Symmetry Classes of Parallelogram Polyominoes|date= 2000-03-21|url= http://www.math.cornell.edu/~rassart/pub/LerouxRassart.pdf}}
* {{citat|last1= Marshall|first1= William Rex|title= Packing Rectangles with Congruent Polyominoes|journal= Journal of Combinatorial Theory,  Series A|date= februar 1997|volume= 77|issue= 2|pages= 181–192|doi= 10.1006/jcta.1997.2730}}
* {{citat|last1= Martin|first1= George Edward|title= Polyominoes: A guide to puzzles and problems in tiling|date= 1996|edition= 2.|publisher= [[Matematična zveza Amerike]]|isbn= 0-88385-501-1}}
* {{citat|last1= Mireles|first1= Jorge Luis|url= http://geocities.com/jorgeluismireles/polypolyominoes/|title= Poly<sup>2</sup>ominoes|date= 2003-11-30|accessdate= 2015-08-27|language= en|archive-date= 2009-10-27|archive-url= https://web.archive.org/web/20091027093922/http://geocities.com/jorgeluismireles/polypolyominoes/|url-status= bot: unknown}}
* {{citat|last1= Moore|first1= Cristopher|authorlink1= Cristopher Moore|last2= Robson|first2= John Michael|title= Hard Tiling Problems with Simple Tiles|date= 2001|url= http://www.santafe.edu/media/workingpapers/00-03-019.pdf|language= en|accessdate= 2015-08-27|archive-date= 2013-06-17|archive-url= https://web.archive.org/web/20130617140921/http://www.santafe.edu/media/workingpapers/00-03-019.pdf|url-status= dead}}
* {{citat|last1= Niţică|first1= Viorel|contribution= Rep-tiles revisited|location= Providence, RI|mr= 2027179|pages= 205–217|publisher= Ameriška matematična zveza|title= MASS selecta|date= 2003}}
* {{citat|last1= Oliveira e Silva|first1= Tomás|url= http://www.ieeta.pt/%7Etos/animals/a44.html|title= Animal enumerations on the {4,4} Euclidean tiling|date= 2015-12-28|accessdate= 2007-05-06|language= en}}
* {{citat|last1= Petersen|first1= Ivars|title= Math Trek: Tiling with Polyominoes|date= 1999-09-25|journal= [[Science News]]|url= http://www.sciencenews.org/pages/sn_arc99/9_25_99/mathland.htm}}
* {{citat|last1= Picciotto|first1= Henri|title= Geometry Labs|date= 1999|publisher= MathEducationPage.org|url= http://books.google.com/books?id=7gTMKr7TT6gC&pg=PA208}}
* {{citat|last1= Potočnik|first1= Aleksander|authorlink1= Aleksander Potočnik|title= Polinomine|url= http://www.dmfa.si/Brihtnez/BrihtnezIndex.html|journal= Brihtnež|date= 2002|volume= 0|issue= 1|pages= 4–7|id= }}
* {{citat|last1= Rawsthorne|first1= Daniel A.|title= Tiling complexity of small ''n''-ominoes (''N'' < 10)|journal= Discrete Mathematics|date= 1988|volume= 70|issue= 1|pages= 71–75|doi=10.1016/0012-365X(88)90081-7}}
* {{citat|last1= Redelmeier|first1= D. Hugh|title= Counting polyominoes: yet another attack|journal= Discrete Mathematics|date= 1981|volume= 36|pages= 191–203|doi= 10.1016/0012-365X(81)90237-5}}
* {{citat|last1= Reid|first1= Michael|url= http://www.cflmath.com/~reid/Polyomino/rectifiable_data.html|title= List of known prime rectangles for various polyominoes|date= 2005-04-09|accessdate=2007-05-11|language= en}}
* {{citat|last1= Reid|first1= Michael|url= http://www.cflmath.com/~reid/Polyomino/rectifiable_bib.html|title= References for Rectifiable Polyominoes|date= 2011-09-24|accessdate= 2007-05-11|language= en}}
* {{citat|last1= Resta|first1= Giovanni|url= http://www.iread.it/Poly/|title= Polypolyominoes|date= 2009|accessdate= 2015-08-27|language=en }}
* {{citat|last1= Rhoads|first1= Glenn C.|title= Planar Tilings and the Search for an Aperiodic Prototile|date= 2003|publisher= doktorska disertacija, Univerza Rutgers}}
* {{citat|last1= Rhoads|first1= Glenn C.|title= Planar tilings by polyominoes, polyhexes, and polyiamonds|journal= [[Journal of Computational and Applied Mathematics]]|date= 2005|volume= 174|issue= 2|pages= 329–353|doi= 10.1016/j.cam.2004.05.002}}
* {{citat|last1= Stanley|first1= Richard Peter|authorlink1= Richar Peter Stanley|title= Enumerative Combinatorics, Vol. 2|date= 1999|publisher= Cambridge University Press|isbn= 0-521-56069-1|cobiss= 8643417|url= http://www-math.mit.edu/~rstan/ec/}}
* {{navedi enciklopedijo|editor-last1= Tavzes|editor-first1= Miloš|encyclopedia= Veliki slovar tujk|publisher= [[Cankarjeva založba]]|location= Ljubljana|date= 2002|isbn= 961-231-271-0|cobiss= 121003520}}
* {{citat|last1= Wilf|first= Herbert Saul|authorlink1= Herbert Wilf|title= Generatingfunctionology|edition= 2.|location= Boston, MA |publisher= Academic Press|date= 1994|isbn= 0-12-751956-4|zbl= 0831.05001|cobiss= 9026644}}
* {{citat|last1= Zucca|first1= Livio|url= http://userpages.monmouth.com/~colonel/rosp/triplep.html|title= Triple Pentominoes|date= 2014-11-11|accessdate= 2015-08-27|language= en}}
{{refend}}

== Zunanje povezave ==

{{kategorija v Zbirki|Polyominoes}}
* {{MathWorld|id=Polyomino|title=Polyomino}}
* [http://gfredericks.com/main/sandbox/polyominoes Aplikacija za interaktivno pokrivanje s poliominami] {{ikona en}}
* [http://www.eklhad.net/polyomino/ Pokrivanje končnega pravokotnika Karla Dahlkeja] {{ikona en}}
* [http://www-cs-faculty.stanford.edu/~knuth/programs.html#polyominoes Uporaba in opis Jensenove metode] {{ikona en}}
* [http://www.statslab.cam.ac.uk/~grg/books/hammfest/19-sgw.ps Članek z opisi sodobnih ocen (PS)] {{ikona en}}
* [http://www.mathpages.com/home/kmath039.htm MathPages – opombe na štetje poliomin z različnimi simetrijami] {{ikona en}}
* [http://www.mayhematics.com/d/db.htm Seznam razčlenitvenih problemov v ''Fairy Chess Review''] {{ikona en}}
* Schere, Karl, ''[http://demonstrations.wolfram.com/Tetrads/ Tetrads]'' [[Wolfram Demonstrations Project]] {{ikona en}}

{{-}}

{{poliforme}}

[[Kategorija:Poliforme]]
[[Kategorija:Razvedrilna matematika in uganke]]
[[Kategorija:Nerešeni matematični problemi]]
{{normativna kontrola}}