polünoomiga

Polüomino on geomeetriline kujund, mida moodustavad ruutudest koosnevad osad, ühendatud külg-küljele. Iga ruut on võrdse suurusega ning kogu kujund on üksteisega külgsuunalises ühenduses, mis tähendab, et iga ruut on ühendatud vähemalt ühe teise ruuduga külje kaudu. Kujundeid kirjeldatakse nende moodustavate ruutude arvu järgi: monomino (1 ruut), domino (2 ruutu), tromino (3 ruutu), tetromino (4 ruutu), pentomino (5 ruutu) ja nii edasi. Eri suurustega kujundeid on igasuguseid ning need võivad tekkida erinevatest külg-ula ühendustest.

Klassifikatsioon. Peamised klassifikatsioonitüübid on vaba polüomino, ühepoolne polüomino ja kinnine (fix) polüomino. Vaba polüomino käsitleb kujundeid samaväärsena, kui neid saab pöörata või peegeldada. Ühepoolne polüomino arvestab pöördenäidud, kuid peegeldused võivad moodustada erinevaid kujundeid. Kinnine või fikseeritud polüomino võtab arvesse kõiki orientatsioone eraldi, nii et sama kujund erinevates suundades on eraldi juhtum.

Ajalugu ja nimetus. Termini “polüomino” lõi 1950ndail Solomon W. Golomb ning see valdkond sai 1960.‑ndatel populaarsust tänu tema raamatule Polyominoes (ilmunud 1965). Polüominoid on leidnud kasutust rekreatiivses matemaatikas, kombinaatorikas ja teoreetiliste probleemide uurimisel.

Rakendused ja uuringud. Polüominoid kasutatakse ruumiliste puslede ja katmismängude loomisel, tiling- ja packing-tehnikates ning katsete jaoks arendada meetodeid kujundite loendamiseks ja positsioonide otsimiseks. Pen-tüüpi komplektid (pentomino) on kuulsaid näiteid: tavaliselt on 12 vaba pentomino kujundit, mida on laialdaselt kasutatud katte- ja kombinatoorsetes probleemides.

Statistika ja kasv. Eelduslik kasvukasv free polüominoide puhul on eksponentsiaalne, ligikaudu mu ≈ 4,0626^n, kus n on ruutude arv kujundis; täpsed arvud on teada vaid väiksemate n-ide kohta. Polüominoide koguarvudes on oluline eristada “free”, “one-sided” ja “fixed” kategorisatsioon, mis kajastab orientatsiooni ja peegelduste mõju.