Polyomino

De 18 ensidiga pentominoerna , inklusive 6 spegelpar

De 35 fria hexominoerna , färgade enligt deras symmetri.

Den enda fria dominon .

En polyomino är en plan geometrisk figur som bildas genom att sammanfoga en eller flera lika stora kvadrater kant i kant. Det är en polyform vars celler är kvadrater. Det kan betraktas som en ändlig delmängd av den vanliga kvadratiska plattsättningen .

Polyominoer har använts i populära pussel sedan åtminstone 1907, och uppräkningen av pentominoer dateras till antiken. Många resultat med bitarna på 1 till 6 rutor publicerades först i Fairy Chess Review mellan åren 1937 till 1957, under namnet " dissektionsproblem ". Namnet polyomino uppfanns av Solomon W. Golomb 1953, och det populariserades av Martin Gardner i en november 1960 " Matematical Games "-kolumn i Scientific American .

Besläktade med polyominoer är polyiamanter , bildade av liksidiga trianglar ; polyhexer , bildade av regelbundna hexagoner ; och andra plana polyformer . Polyominoer har generaliserats till högre dimensioner genom att sammanfoga kuber för att bilda polykuber eller hyperkuber för att bilda polyhyperkuber.

Inom statistisk fysik tillämpas studiet av polyominoer och deras högre dimensionella analoger (som ofta kallas gitterdjur i denna litteratur) på problem inom fysik och kemi. Polyominoer har använts som modeller av grenade polymerer och perkolationskluster .

Liksom många pussel i rekreationsmatematiken väcker polyominoer många kombinatoriska problem. Det mest grundläggande är att räkna upp polyominoer av en given storlek. Ingen formel har hittats förutom speciella klasser av polyominoer. Ett antal uppskattningar är kända och det finns algoritmer för att beräkna dem.

Polyominoer med hål är obekväma för vissa ändamål, som till exempel kakelproblem. I vissa sammanhang är polyominoer med hål uteslutna, vilket endast tillåter helt enkelt sammankopplade polyominoer.

Uppräkning av polyominoer

Fria, ensidiga och fasta polyominoer

Det finns tre vanliga sätt att särskilja polyominoer för uppräkning:

fria polyominoer är distinkta när ingen är en stel transformation ( translation , rotation , reflektion eller glidreflektion ) av en annan (bitar som kan plockas upp och vändas över). Att översätta, rotera, reflektera eller glida reflekterande en fri polyomino ändrar inte dess form.
ensidiga polyominoer är distinkta när ingen är en translation eller rotation av en annan (bitar som inte kan vändas). Att översätta eller rotera en ensidig polyomino ändrar inte dess form.
fasta polyominoer är distinkta när ingen är en translation av en annan (bitar som varken kan vändas eller roteras). Att översätta en fast polyomino kommer inte att ändra dess form.

Följande tabell visar antalet polyominoer av olika typer med n celler.

n	namn	fri			ensidig	fast
n	namn	total	med hål	utan hål	ensidig	fast
1	monomino	1	0	1	1	1
2	domino	1	0	1	1	2
3	tromino	2	0	2	2	6
4	tetromino	5	0	5	7	19
5	pentomino	12	0	12	18	63
6	hexomino	35	0	35	60	216
7	heptomino	108	1	107	196	760
8	octomino	369	6	363	704	2,725
9	nonomino	1 285	37	1 248	2 500	9,910
10	decomino	4,655	195	4,460	9,189	36,446
11	undecomino	17 073	979	16 094	33,896	135,268
12	dodecomino	63 600	4,663	58,937	126,759	505,861
OEIS- sekvens		A000105	A001419	A000104	A000988	A001168

Från och med 2004 har Iwan Jensen räknat upp de fixerade polyominoerna upp till n = 56 – ungefär 6,915 × 10 ³¹ .

Fria polyominoer räknades upp 2007 upp till n = 28 av Tomás Oliveira e Silva, och 2012 upp till n = 45 av Toshihiro Shirakawa.

Symmetrier av polyominoer

Den dihedriska gruppen D ₄ är gruppen av symmetrier ( symmetrigrupp ) av en kvadrat. Denna grupp innehåller fyra rotationer och fyra reflektioner. Den genereras av alternerande reflektioner kring x -axeln och om en diagonal. En fri polyomino motsvarar högst 8 fasta polyominoer, som är dess bilder under symmetrierna av D ₄ . Dessa bilder är dock inte nödvändigtvis distinkta: ju mer symmetri en fri polyomino har, desto färre distinkta fasta motsvarigheter har den. Därför kan en fri polyomino som är invariant under vissa eller alla icke-triviala symmetrier av D ₄ motsvara endast 4, 2 eller 1 fasta polyominoer. Matematiskt är fria polyominoer ekvivalensklasser av fixerade polyominoer under gruppen D ₄ .

Polyominoer har följande möjliga symmetrier; det minsta antalet kvadrater som behövs i en polyomino med den symmetrin anges i varje fall:

8 fasta polyominoer för varje fri polyomino:
- ingen symmetri (4)
4 fasta polyominoer för varje fri polyomino:
- spegelsymmetri med avseende på en av rutnätslinjernas riktningar (4)
- spegelsymmetri med avseende på en diagonal linje (3)
- 2-faldig rotationssymmetri: C ₂ (4)
2 fasta polyominoer för varje fri polyomino:
- symmetri med avseende på båda rutnätslinjerna, och därmed också 2-faldig rotationssymmetri: D ₂ (2) (även känd som Klein-fyragruppen )
- symmetri med avseende på båda diagonala riktningarna, och därmed också 2-faldig rotationssymmetri: D ₂ (7)
- 4-faldig rotationssymmetri: C ₄ (8)
1 fast polyomino för varje fri polyomino:
- all symmetri av kvadraten: D ₄ (1).

På samma sätt beror antalet ensidiga polyominoer på polyominosymmetri enligt följande:

2 ensidiga polyominoer för varje fri polyomino:
- ingen symmetri
- 2-faldig rotationssymmetri: C ₂
- 4-faldig rotationssymmetri: C ₄
1 ensidig polyomino för varje fri polyomino:
- all symmetri av kvadraten: D ₄
- spegelsymmetri med avseende på en av rutnätslinjernas riktningar
- spegelsymmetri med avseende på en diagonal linje
- symmetri med avseende på båda rutnätsriktningarna, och därmed också 2-faldig rotationssymmetri: D ₂
- symmetri med avseende på båda diagonala riktningarna, och därmed också 2-faldig rotationssymmetri: D ₂ .

Följande tabell visar antalet polyominoer med n kvadrater, sorterade efter symmetrigrupper.

n	ingen	spegel 90°	spegel 45°	C ₂	D ₂ 90°	D ₂ 45°	C ₄	D ₄
1	0	0	0	0	0	0	0	1
2	0	0	0	0	1	0	0	0
3	0	0	1	0	1	0	0	0
4	1	1	0	1	1	0	0	1
5	5	2	2	1	1	0	0	1
6	20	6	2	5	2	0	0	0
7	84	9	7	4	3	1	0	0
8	316	23	5	18	4	1	1	1
9	1 196	38	26	19	4	0	0	2
10	4,461	90	22	73	8	1	0	0
11	16 750	147	91	73	10	2	0	0
12	62,878	341	79	278	15	3	3	3
OEIS- sekvens	A006749	A006746	A006748	A006747	A056877	A056878	A144553	A142886

Algoritmer för uppräkning av fasta polyominoer

Induktiva algoritmer

Varje polyomino av ordningen n +1 kan erhållas genom att lägga till en kvadrat till en polyomino av ordningen n . Detta leder till algoritmer för att generera polyominoer induktivt.

Enklast, givet en lista med polyominoer av ordning n , kan kvadrater läggas till bredvid varje polyomino i varje möjlig position, och den resulterande polyomino av ordning n +1 läggas till i listan om inte en dubblett av en som redan finns; finesser i ordningsföljden av uppräkningen och markering av intilliggande rutor som inte bör övervägas minskar antalet fall som behöver kontrolleras för dubbletter. Denna metod kan användas för att räkna upp antingen fria eller fixerade polyominoer.

En mer sofistikerad metod, beskriven av Redelmeier, har använts av många författare som ett sätt att inte bara räkna polyominoer (utan att kräva att alla polyominoer av ordning n lagras för att räkna upp de av ordning n+1), utan också bevisa övre gränser för deras antal. Grundtanken är att vi börjar med en enda ruta, och därifrån lägger vi till kvadrater rekursivt. Beroende på detaljerna kan det räknas varje n -omino n gånger, en gång från att börja från var och en av dess n rutor, eller kan ordnas så att den endast räknas en gång.

Den enklaste implementeringen innebär att lägga till en ruta i taget. Börja med en första ruta, numrera de intilliggande rutor, medurs från toppen, 1, 2, 3 och 4. Välj nu ett tal mellan 1 och 4 och lägg till en ruta på den platsen. Numrera de onumrerade intilliggande rutorna, börja med 5. Välj sedan ett tal som är större än det tidigare valda talet och lägg till den kvadraten. Fortsätt att välja ett nummer som är större än numret på den aktuella kvadraten, lägg till den kvadraten och numrera sedan de nya intilliggande kvadraterna. När n rutor har skapats har en n -omino skapats.

Denna metod säkerställer att varje fast polyomino räknas exakt n gånger, en gång för varje startruta. Den kan optimeras så att den bara räknar varje polyomino en gång, snarare än n gånger. Börja med den initiala kvadraten, förklara att den är den nedre vänstra kvadraten av polyomino. Numrera helt enkelt inte någon ruta som är på en lägre rad, eller till vänster om kvadraten på samma rad. Detta är versionen som beskrivs av Redelmeier.

Om man istället vill räkna fria polyominoer, kan man kontrollera symmetrierna efter att man skapat varje n -omino. Det är dock snabbare att generera symmetriska polyominoer separat (genom en variation av denna metod) och så bestämma antalet fria polyominoer med Burnsides lemma .

Transfer-matris-metod

Den modernaste algoritmen för att räkna upp de fasta polyominoerna upptäcktes av Iwan Jensen. En förbättring av Andrew Conways metod, den är exponentiellt snabbare än de tidigare metoderna (dock är dess körtid fortfarande exponentiell i n ).

Både Conways och Jensens versioner av transfer-matrismetoden går ut på att räkna antalet polyominoer som har en viss bredd. Att beräkna antalet för alla bredder ger det totala antalet polyominoer. Grundtanken bakom metoden är att möjliga början rader övervägs, och sedan att bestämma det minsta antal rutor som behövs för att slutföra polyomino av den givna bredden. I kombination med användningen av genereringsfunktioner kan denna teknik räkna många polyominoer samtidigt, vilket gör att den kan köras många gånger snabbare än metoder som måste generera varje polyomino.

Även om den har utmärkt körtid, är avvägningen att denna algoritm använder exponentiella mängder minne (många gigabyte minne behövs för n över 50), är mycket svårare att programmera än de andra metoderna och kan för närvarande inte användas för att räkna fria polyominoer.

Asymptotisk tillväxt av antalet polyominoer

Fasta polyominoer

Teoretiska argument och numeriska beräkningar stöder uppskattningen av antalet fasta polyominoer av storlek n

A_{n}\sim {\frac {c\lambda ^{n}}{n}}

där X = 4,0626 och c = 0,3169. Detta resultat är dock inte bevisat och värdena för λ och c är bara uppskattningar.

De kända teoretiska resultaten är inte alls lika specifika som denna uppskattning. Det har det bevisats

\lim _{n\rightarrow \infty }(A_{n})^{\frac {1}{n}}=\lambda

existerar. Med andra ord A _n exponentiellt . Den mest kända nedre gränsen för λ , som hittades 2016, är 4,00253. Den mest kända övre gränsen, inte förbättrad sedan 1970-talet, är λ < 4,65 .

För att fastställa en nedre gräns är en enkel men mycket effektiv metod sammanlänkning av polyominoer. Definiera den övre högra kvadraten så att den är kvadraten längst till höger i den översta raden av polyomino. Definiera den nedre vänstra fyrkanten på liknande sätt. Sedan kan den övre högra kvadraten på vilken polyomino som helst av storlek n fästas till den nedre vänstra kvadraten på vilken polyomino som helst av storlek m för att producera en unik ( n + m )-omino. Detta bevisar A _n A _m ≤ A _{n + m} . Med denna ekvation kan man visa λ ≥ ( A _n ) ^{1/ n} för alla n . Förfining av denna procedur kombinerad med data för _An ger den nedre gränsen som ges ovan.

Den övre gränsen uppnås genom att generalisera den induktiva metoden för att räkna upp polyominoer. Istället för att lägga till en ruta i taget, lägger man till ett kluster av rutor åt gången. Detta beskrivs ofta som att man lägger till kvistar . Genom att bevisa att varje n -omino är en sekvens av kvistar, och genom att bevisa gränser för kombinationerna av möjliga kvistar, får man en övre gräns för antalet n -ominoer. Till exempel, i algoritmen som beskrivs ovan måste vi vid varje steg välja ett större tal, och högst tre nya tal läggs till (eftersom högst tre onumrerade rutor ligger intill valfri numrerad kvadrat). Detta kan användas för att få en övre gräns på 6,75. Med hjälp av 2,8 miljoner kvistar fick Klarner och Rivest en övre gräns på 4,65, som därefter förbättrades av Barequet och Shalah till 4,5252.

Gratis polyominoer

Approximationer för antalet fasta polyominoer och fria polyominoer är relaterade på ett enkelt sätt. En fri polyomino utan symmetri (rotation eller reflektion) motsvarar 8 distinkta fasta polyominoer, och för stora n har de flesta n -ominoer inga symmetrier. Därför är antalet fasta n -ominoer ungefär 8 gånger antalet fria n -ominoer. Dessutom är denna approximation exponentiellt mer exakt när n ökar.

Specialklasser av polyominoer

Exakta formler är kända för att räkna upp polyominoer av speciella klasser, såsom klassen av konvexa polyominoer och klassen av riktade polyominoer.

Definitionen av en konvex polyomino skiljer sig från den vanliga definitionen av konvexitet , men liknar definitionen som används för det ortogonala konvexa skrovet . En polyomino sägs vara vertikal eller kolumn konvex om dess skärning med någon vertikal linje är konvex (med andra ord, varje kolumn har inga hål). På liknande sätt sägs en polyomino vara horisontell eller radkonvex om dess skärning med någon horisontell linje är konvex. En polyomino sägs vara konvex om den är rad och kolumn konvex.

En polyomino sägs vara riktad om den innehåller en kvadrat, känd som roten , så att varannan kvadrat kan nås genom rörelser upp eller åt höger en kvadrat, utan att lämna polyomino.

Riktade polyominoer, kolumn- (eller rad-) konvexa polyominoer och konvexa polyominoer har effektivt räknats upp av arean n , såväl som av några andra parametrar såsom omkrets, med hjälp av genererande funktioner .

En polyomino är likvärdig om dess area är lika med dess omkrets. En likvärdig polyomino måste tillverkas av ett jämnt antal rutor; varje jämnt tal större än 15 är möjligt. Till exempel är 16-omino i form av en 4 × 4 kvadrat och 18-omino i form av en 3 × 6 rektangel båda likvärdiga. För polyominoer med färre än 15 rutor överskrider omkretsen alltid arean.

Kakel med polyominoer

I rekreationsmatematik ställs ofta utmaningar för att belägga en föreskriven region, eller hela planet, med polyominoer, och relaterade problem undersöks i matematik och datavetenskap .

Kakelområden med uppsättningar av polyominoer

Pussel frågar vanligen efter att ett visst område sätts ihop med en given uppsättning polyominoer, till exempel de 12 pentominoerna. Golombs och Gardners böcker har många exempel. Ett typiskt pussel är att belägga en 6×10 rektangel med de tolv pentominoerna; de 2339 lösningarna på detta hittades 1960. Där flera kopior av polyominoerna i uppsättningen är tillåtna, definierar Golomb en hierarki av olika regioner som en uppsättning kan ha möjlighet att lägga till, såsom rektanglar, remsor och hela planet, och visar att huruvida polyominoer från en given uppsättning kan belägga planet är obestämbart , genom att mappa uppsättningar av Wang-plattor till uppsättningar av polyominoer.

Eftersom det allmänna problemet med att belägga områden i planet med uppsättningar av polyominoer är NP-komplett , blir plattsättning med fler än ett fåtal stycken snabbt svårlöst och därför krävs hjälp av en dator. Det traditionella tillvägagångssättet för att kakla ändliga områden av planet använder en teknik inom datavetenskap som kallas backtracking .

I Jigsaw Sudokus är ett kvadratiskt rutnät belagt med polynominoformade områden (sekvens A172477 i OEIS ).

Kakelområden med kopior av en enda polyomino

En annan klass av problem frågar sig om kopior av en given polyomino kan belägga en rektangel , och i så fall vilka rektanglar de kan belägga med. Dessa problem har studerats omfattande för särskilda polyominoer, och tabeller med resultat för individuella polyominoer finns tillgängliga. Klarner och Göbel visade att det för varje polyomino finns en ändlig uppsättning primtalsrektanglar som den bricker, så att alla andra rektanglar som den bricker kan beläggas med dessa primtalsrektanglar. Kamenetsky och Cooke visade hur olika osammanhängande (kallade "håliga") polyominoer kan belägga rektanglar.

Bortom rektanglar gav Golomb sin hierarki för enskilda polyominoer: en polyomino kan belägga en rektangel, en halv remsa, en böjd remsa, en förstorad kopia av sig själv, en kvadrant, en remsa, ett halvt plan, hela planet, vissa kombinationer , eller Ingen av dessa. Det finns vissa implikationer bland dessa, både uppenbara (till exempel om en polyomino belägger halvplanet så lägger den till hela planet) och mindre så (till exempel om en polyomino bricker en förstorad kopia av sig själv, så lägger den till kvadranten) . Polyominoer med order upp till 6 karakteriseras i denna hierarki (med statusen en hexomino, som senare visade sig lägga till en rektangel, olöst vid den tiden).

2001 visade Cristopher Moore och John Michael Robson att problemet med att kakla en polyomino med kopior av en annan är NP-komplett .

Kakelsättning av planet med kopior av en enda polyomino

De två icke-nominerade plattorna uppfyller inte Conway-kriteriet.

Att kakla planet med kopior av en enda polyomino har också diskuterats mycket. Det noterades 1965 att alla polyominoer upp till hexominoer och alla utom fyra heptominoer belägger planet. Det fastställdes sedan av David Bird att alla utom 26 octominoes belägger planet. Rawsthorne fann att alla utom 235 polyominoer av ordning 9, och sådana resultat har utökats till högre beställningar av Rhoads (till ordning 14) och andra. Polyominoer som plattsätter planet har klassificerats efter symmetrierna i deras plattsättningar och efter antalet aspekter (orientering) som plattorna förekommer i dem.

Studiet av vilka polyominoer som kan belägga planet har underlättats med Conway-kriteriet : förutom två nonominoer, bildar alla polyominoer upp till ordning 9 en lapp med minst en platta som uppfyller det, med högre ordnings undantag mer frekvent.

Flera polyominoer kan belägga större kopior av sig själva, och att upprepa denna process rekursivt ger en rep-tile- platting av planet. Till exempel, för varje positivt heltal $n$ , är det möjligt att kombinera $n 2$ kopior av L-tromino, L-tetromino eller P-pentomino till en enda större form som liknar den mindre polyomino som den bildades av.

Kakelsättning av en vanlig figur med olika polyominoer

En minimal kompatibilitetssiffra för T och W pentominoes .

Kompatibilitetsproblemet är att ta två eller flera polyominoer och hitta en figur som kan kaklas med varje . Polyomino-kompatibilitet har studerats flitigt sedan 1990-talet. Jorge Luis Mireles och Giovanni Resta har publicerat webbplatser med systematiska resultat, och Livio Zucca visar resultat för några komplicerade fall som tre olika pentominoer. Det allmänna problemet kan vara svårt. Den första kompatibilitetssiffran för L och X pentominoes publicerades 2005 och hade 80 brickor av varje slag. Många par av polyominoer har visat sig vara oförenliga genom systematisk utmattning. Ingen algoritm är känd för att avgöra om två godtyckliga polyominoer är kompatibla.

Polyominoer i pussel och spel

Utöver kakelproblemen som beskrivs ovan finns det matematikpussel för rekreation som kräver att vika en polyomino för att skapa andra former. Gardner föreslog flera enkla spel med en uppsättning gratis pentominoer och ett schackbräde. Vissa varianter av Sudoku- pusslet använder nonomino-formade områden på rutnätet. TV-spelet Tetris är baserat på de sju ensidiga tetrominoerna (stavade "Tetriminos" i spelet), och brädspelet Blokus använder alla gratis polyominoer upp till pentominoer.

Etymologi

Ordet polyomino och namnen på de olika ordningarna av polyomino är alla bakgrundsformationer från ordet domino , en vanlig spelpjäs som består av två rutor, med den första bokstaven d- fantasifullt tolkad som en version av prefixet di- som betyder "två ". ." Namnet domino för spelpjäsen tros komma från det prickiga maskeradplagget domino , från latinets dominus .

De flesta av de numeriska prefixen är grekiska. Polyominoer av ordningen 9 och 11 tar oftare de latinska prefixen nona- (nonomino) och undeca- (undecomino) än de grekiska prefixen ennea- (enneomino) och hendeca- (hendecomino). ^{[ varför? ]}

Se även

Perkolationsteori , den matematiska studien av slumpmässiga delmängder av heltalsnät. De ändligt anslutna komponenterna i dessa delmängder bildar polyominoer.
Young diagram , en speciell sorts polyomino som används i talteorin för att beskriva heltalspartitioner och i gruppteori och tillämpningar inom matematisk fysik för att beskriva representationer av den symmetriska gruppen.
Blokus , ett brädspel med polyominoer.
Squaregraph , en sorts oriktad graf inklusive som ett specialfall graferna för hörn och kanter på polyominoer.

Anteckningar

externa länkar

Polyformer
Polyominoer	Domino Tromino Tetromino Pentomino Hexomino Heptomino Octomino Nonomino Decomino
Högre dimensioner	Polyominoid Polykub
Andra	Polyabolo Polydrafter Polyhex Polyiamond Pseudo-polyomino Polystick
Spel och pussel	Blokus Soma kub Ormkub Tangram Hexastix Tantrix Tetris
WikiProject Portal