polünoomidest

Polünoomidest on plane kujundid, mis koosnevad piiridega ühendatud ühesuurustest ruutudest. Iga kujund sisaldab n ruutu (n≥1) ja ruudud on omavahel ühendatud serva kaudu. Kujundeid hinnatakse vastavalt sellele, kas pööramised ja peegeldused loetakse ühtseteks: free polüominoid (arvestatakse pööramisi ja peegeldusi koos), one-sided (arvestatakse pööramised, kuid mitte peegeldused) või fixed (ainult translatsioon).

Termini “polüomino” lõi Solomon Golomb 1950-ndatel; mõiste on saanud populaarseks combinatorics’i ja puslede valdkonnas. Kõige tuntumad alamhulgad on domino (2 ruutu), tromino (3), tetromino (4) ja pentomino (5). Tetromino’ide näidetena on T-, L-, I- ja O-kujulised kujundid, mis on tuntud ka Tetris-mängus.

Uurimise ja rakenduste valdkond: polüominoide kasutatakse tiling’ute (katmise) probleemides, pusledes ja arvutuslikus kombinatoorikas. Pentomino-pusle on ajalooliselt kuulus ülesanne, kus tuleb katet täita konkreetse alaga iga pentomino’iga täpselt ühe korra.

Statistika: väikeste n puhul on kõigi kujundite arv täielikult loetav; üldine kasv on eksponentsiaalne. Kasvu konstant μ on hinnanguliselt umbes 4,0626, sõltuvalt sellest, kas peegeldused loetakse sama kujundina. Polüominoide uuritakse endiselt aktiivselt; nende probleemid ja lahendused ühendavad geomeetriat, kombinatoorikat ja tehisintellekti.