imported>Ambross07: Linkfix mit AWB

2026-01-05T10:08:20Z

Linkfix mit AWB

Neue Seite

Ein '''Polyomino''' (Kunstwort, abgeleitet von [[Domino]]) ist eine Fläche, die aus <math>n</math> zusammenhängenden [[Quadrat (Geometrie)|Quadraten]] besteht.

Für kleine <math>n</math> sind auch die Bezeichnungen
'''Monomino''' (<math>n=1</math>),
'''Domino''' (<math>n=2</math>),
'''Tromino''' (<math>n=3</math>),
'''Tetromino''' (<math>n=4</math>),
'''Pentomino''' (<math>n=5</math>),
'''Hexomino''' (<math>n=6</math>),
'''Heptomino''' (<math>n=7</math>),
'''Oktomino''' (<math>n=8</math>),
'''Nonomino''' oder '''Enneomino''' (<math>n=9</math>),
'''Dekomino''' (<math>n=10</math>),
'''Undekomino''' (<math>n=11</math>),
'''Dodekomino''' (<math>n=12</math>)
usw. üblich.

== Definition ==
Ein Polyomino oder <math>n</math>-Mino ist eine Figur <math>P</math>, die aus <math>n \geq 1</math> [[Kongruenz (Geometrie)|kongruenten]] Quadraten besteht, für die gilt
# je zwei Quadrate haben entweder keinen Punkt oder eine Ecke oder eine Kante gemeinsam,
# zu je zwei verschiedenen Quadraten <math>Q_1</math> und <math>Q^*</math> aus <math>P</math> gibt es eine Folge <math>Q_1 Q_2 \ldots Q_{k-1} Q^*</math> von benachbarten Quadraten aus <math>P</math>.
Dabei heißen zwei Quadrate benachbart, wenn die Menge ihrer gemeinsamen Punkte eine Seite ist. Folgende Beispiele stellen demnach keine Polyominos dar.
<gallery heights="50" widths="80">
polyo1.svg|1. ungültig
polyo2.svg|2. ungültig
polyo3.svg|3. ungültig
polyo4.svg|4. ungültig
</gallery>

Für besondere Anwendungen wird zusätzlich gefordert:
* <math>P</math> bildet eine [[einfach zusammenhängend]]e Punktmenge.
[[Datei:polyo5.svg|gerahmt|ohne|Polyomino mit Loch]]

=== Darstellung über Zusammenhangsgraphen ===
Jedem Polyomino <math>P</math> lässt sich ein [[Zusammenhang (Graphentheorie)|Zusammenhangsgraph]] zuordnen, indem man jedes Quadrat aus <math>P</math> als Knoten und das Benachbartsein zweier Quadrate durch eine Kante wiedergibt. Nachfolgend wird dies anhand der 5 Tetrominos dargestellt.
<gallery mode="nolines">
tetromino zusammenhangsgraph i.svg
tetromino zusammenhangsgraph l.svg
tetromino zusammenhangsgraph t.svg
tetromino zusammenhangsgraph z.svg
tetromino zusammenhangsgraph o.svg
</gallery>

== Konstruktion ==
[[Datei:Tetrominos.svg|mini|Die 5 ''Tetrominos'']]

=== Bestimmung der Anzahlen ===
Es gibt verschiedene Ansätze, die Anzahl der Polyominos zu bestimmen. Am häufigsten wird nur bis auf [[Kongruenz (Geometrie)|Kongruenz]] unterschieden. In praktischen Sachverhalten sind jedoch häufig nur [[Orientierung (Mathematik)|orientierungserhaltende]] Bewegungen für das ''Zur-Deckung-Bringen'' zugelassen, also nur Drehungen und Verschiebungen und keine [[Spiegelung (Geometrie)|Achsenspiegelungen]]. Auch bei dem Spiel [[Tetris]] ist dies der Fall. Kongruente Polyominos, die eine unterschiedliche Orientierung besitzen, werden dabei als verschieden angesehen
{{Doppeltes Bild|links|polyooe1.svg|220|polyooe2.svg|220|nicht-orientierungserhaltende Bewegung}}
{{absatz|links}}
[[Datei:Pentaminos1.png|mini|Die 12 ''Pentominos'']]
[[Datei:Hexominoes.svg|mini|Die 35 ''Hexominos'']]

<math>A(n)</math> bezeichnet die Anzahl Polyominos, die sich bis auf Kongruenz aus <math>n</math> Quadraten bilden lassen. <math>A'(n)</math> ist die Anzahl unter Beachtung der Orientierung, d. h. zueinander spiegelbildliche (wie oben illustriert) werden als verschieden betrachtet. <math>A''(n)</math> bezeichnet die Anzahl unter Beachtung der Orientierung und aller möglichen Lagen, dabei werden sogar zwei zueinander gedrehte, aber sonst gleiche Polyominos als verschieden angesehen. Vor allem <math>A(n)</math> ist von Interesse.
{| class="wikitable" style="text-align:right;"
!<math>n</math> || <math>A(n)</math><ref>{{OEIS|A000105}}</ref> || <math>A'(n)</math><ref>{{OEIS|A000988}}</ref> || <math>A''(n)</math><ref>{{OEIS|A001168}}</ref>
|-
| 1 || 1 || 1 || 1
|-
| 2 || 1 || 1 || 2
|-
| 3 || 2 || 2 || 6
|-
| 4 || 5 || 7 || 19
|-
| 5 || 12 || 18 || 63
|-
| 6 || 35 || 60 || 216
|-
| 7 || 108 || 196 || 760
|-
| 8 || 369 || 704 || 2.725
|-
| 9 || 1.285 || 2.500 || 9.910
|-
| 10 || 4.655 || 9.189 || 36.446
|-
| 11 || 17.073 || 33.896 || 135.268
|-
| 12 || 63.600 || 126.759 || 505.861
|-
| 13 || 238.591 || 476.270 || 1.903 890
|-
| 14 || 901.971 || 1.802.312 || 7.204.874
|-
| 15 || 3.426.576 || 6.849.777 || 27.394.666
|}

Werden ausschließlich einfach zusammenhängende Polyominos gezählt, so ergeben sich von <math>n=7</math> an abweichende Zahlen.<ref>Beispielsweise {{OEIS|A000104}}</ref>

=== Rekursive Fortsetzung ===
==== Algorithmus ====
Man kann leicht ein rekursives Verfahren beschreiben, das es gestattet, aus der Kenntnis aller <math>n-1</math>-Minos <math>(n \geq 2)</math> alle <math>n</math>-Minos zu gewinnen. Es lässt sich zunächst zeigen, dass es zu einem <math>n</math>-Mino <math>P_2</math> <math>(n \geq 2)</math> ein <math>n-1</math>-Mino <math>P_1</math> und ein Quadrat <math>Q</math> gibt, so dass <math>P_2 = P_1 \cup Q</math> ist. Dadurch kann von der Kenntnis der Klassen der <math>n-1</math>-Minos ausgegangen werden. Durch Anfügen eines Quadrates entsteht je ein Repräsentant der Klassen der <math>n</math>-Minos. Auf diese Weise kann auch die Anzahl <math>A(n)</math> der Klassen bestimmt werden. Wir verfahren wie folgt.

Wir nummerieren die Klassen der <math>n-1</math>-Minos durch und beginnen mit einem Repräsentanten <math>P</math> der ersten Klasse und betrachten systematisch alle Lagen eines Quadrates <math>Q</math>, die überhaupt zu einem <math>n</math>-Mino <math>P \cup Q</math> führen können. Diese Lagen werden mit [[Datei:rechteck strich.svg|20px]] oder [[Datei:rechteck punkt.svg|20px]] markiert, je nachdem, ob das entsprechende <math>n</math>-Mino zu den bisherigen kongruent ist oder nicht. Nach gleicher Weise wird bei den nächsten Klassen der <math>n-1</math>-Minos verfahren. Natürlich kann dabei ein <math>n</math>-Mino entstehen, welches zu einem aus vorangegangenen Schritten kongruent ist. Solche werden mit einem Lagekästchen [[Datei:rechteck lage.svg|20px]] bezeichnet <math>(i=1,2,\ldots)</math>.

Nach endlich vielen Schritten bricht das Verfahren ab und es liefert einen Repräsentanten für jede Klasse der <math>n</math>-Minos.

==== Beispiel ====
Der rekursive [[Algorithmus]] soll bei der Ermittlung der Pentominos aus Tetrominos eingesetzt werden.

==== Computergestützt ====
Auf der Grundlage dieses Verfahrens lassen sich die <math>A(n)</math> mit Computern bestimmen. Dabei lassen sich Polyominos durch eine [[Matrix (Mathematik)|Matrix]] mit 0 und 1 wie in folgendem Beispiel beschreiben.

[[Datei:heptomino transform.svg|x60px]] wird zu <math>\begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix}</math>

==== Hexominos ====

Eine Untergruppe von 11 der 35 Hexominos stellen geometrisch gesehen das [[Würfelnetz|Netz eines Würfels]] dar, da er durch 6 quadratische Flächen begrenzt wird.

== Zusammengesetzte ähnliche Polyominos (Reptiles) ==
[[Datei:L-Tromino rep-4.svg|mini|hochkant=0.3|''Figur 1'']]
[[Datei:L-Tetromino rep-4.svg|mini|hochkant=0.3|''Figur 2'']]
[[Datei:T-Tetromino rep-16.svg|mini|hochkant=0.3|''Figur 3'']]
=== Allgemeine Reptiles-Definitionen ===
* Ähnliche Figuren, die sich lückenlos zu einer größeren Figur, die zu den kleineren Figuren ähnlich ist, zusammensetzen lassen, werden im Englischen als ''Reptiles'' (Abkürzung für ''replicating tiles'') bezeichnet.
* Ist <math>n</math> die Anzahl der ähnlichen Teilfiguren, so wird die zusammengesetzte Figur ''rep-<math>n</math>-Figur'' genannt.

=== Anwendungsbeispiele zu Polyominos ===
Im Folgenden sei <math>k\in\N</math>. Unter den verschiedenen Arten von Polyominos gibt es rep-<math>4^k</math>-Figuren und rep-<math>16^k</math>-Figuren ''(Figuren 1, 2 und 3)''.<ref>Claudi Alsina, Roger B. Nelsen: ''Perlen der Mathematik - 20 geometrische Figuren als Ausgangspunkte für mathematische Erkundungsreisen'', [[Springer Spektrum]], Springer-Verlag GmbH [[Berlin]] [[Heidelberg]] 2015, ISBN 978-3-662-45460-2, Seiten 51 bis 54</ref><ref>George E. Martin: ''Polyominoes: A Guide to Puzzles and Problems in Tiling'', [[American Mathematical Society|AMS]]/[[Mathematical Association of America|MAA]], [[Washington, D.C.|Washington]] 1991</ref>

== Verwendung ==
=== Packungen ===
Welche notwendigen und hinreichenden Bedingungen bestehen für die positiv ganzzahligen Seitenlängen eines Rechteckes, damit dieses mit bestimmten Sorten von Polyominos gepackt werden kann.

=== Spieleindustrie ===
Die Spiele [[Domino]] und [[Pentomino]] (Begriff stammt vom amerikanischen Mathematiker [[Solomon W. Golomb]]) sind weit verbreitet. Tetrominos kommen unter anderen in dem vom russischen Programmierer [[Alexei Paschitnow]] 1985 entwickelten Computerspiel ''[[Tetris]]'' zum Einsatz, wobei komplexere Versionen dieses Spiels auch auf andere Polyominos – ggf. [[Polywürfel]], z. B. [[BlockOut]] – zurückgreifen. Ein Brettspiel, das dem Computerspiel ''Tetris'' nahe kommt, ist ''[[Fits|FITS]]'' (2009) von [[Reiner Knizia]]. Es nahm sich das Computerspiel ausdrücklich zum Vorbild. Weitere neuere Brettspiele sind das 2000 erschienene ''[[Blokus]]'' sowie ''[[Ubongo]]'' (2005), wo jeweils die verschiedenen großen <math>n</math>-Minos für <math>n=1,...,5</math> als Spielmaterial verwendet werden. Auch die Spiele ''[[Patchwork (Spiel)|Patchwork]]'' (2014) und ''[[Cottage Garden]]'' (2016) von [[Uwe Rosenberg]] sowie ''[[Die Baumeister von Arkadia]]'' (2006) von [[Rüdiger Dorn]], ''[[NMBR 9]]'' (2017) von [[Peter Wichmann]] und ''[[Bärenpark (Spiel)|Bärenpark]]'' (2017) von [[Phil Walker-Harding]] nutzen diese Formen als Legeteile. Bei ''[[Ein Fest für Odin]]'' (2016) von Uwe Rosenberg sind die Plättchen rechteckig angeordnet. Auch dieses Spiel wird als Polyomino-Spiel eingestuft.<ref>[https://boardgamegeek.com/boardgamefamily/24571/polyominoes Übersicht Polyomino-Spiele] bei Boardgamegeek</ref> 2001 erschien das Spiel ''[[Rumis]]'', welches dreidimensionale Steine (Polywürfel) verwendet.<ref>[http://www.hall9000.de/rezi.pl?spiel=rumis_neu Rezension] von Rumis bei hall9000.de</ref>

=== Pädagogik ===
Die Bausteine finden in der Grundschule Verwendung und dienen der Verbesserung der räumlichen Vorstellung. Ziel ist es, zu einer vorgegebenen Menge von Bausteinen Figuren zu finden oder für vorgegebene Figuren eine Zerlegung in die entsprechenden Bausteine.

Es ist nicht möglich, aus allen 5 möglichen Tetronimos ein 5×4 Rechteck zu erstellen. Es ist auch nicht möglich, ohne Mehrfachverwendung eines Winkelstücks, ein 4×4 Quadrat aus Tetrominos zu erstellen. Die verwendeten Figuren werden, wenn für sie Tetrominos verwendet werden, die den Buchstaben L, T und Z ähnlich sind, auch LTZ-[[Parkettierung|Parkette]] genannt.

== Verwandte Themen ==
* [[Polywürfel]] (auch Polykuben) – das dreidimensionale Pendant mit Würfeln

== Literatur ==
* [[Solomon W. Golomb]]: ''Polyominoes. Puzzles, Patterns, Problems, and Packings''. 2. erweiterte Auflage. Princeton University Press, Princeton 1994, ISBN 0-691-08573-0

== Weblinks ==
{{Commonscat|Polyominoes|Polyomino}}
* [http://mathworld.wolfram.com/Polyomino.html Polyominos bei Wolfram Mathworld]
* [http://www.xs4all.nl/~gp/PolyominoSolver/Polyomino.html Gerard's Universal Polyomino Solver]
* [http://www.mathematik.ch/anwendungenmath/wuerfelpuzzle/ Puzzlespiel mit Polyominos 3D]
* {{Webarchiv |url=http://home.quicknet.nl/mw/prive/wil.laan/puzzle/large.html |text=Spiel zur Füllung mit Polyominos 2D |wayback=20080420070009}}
* {{Webarchiv |url=http://www.uni-landau.de/rasch/Geometrie/Vorlesungen/V5_Ebene_Figuren_Polygone.pdf |text=Ebene Figuren – Vielecke (Anwendung für Kinder) |wayback=20070928070946}}

== Einzelnachweise ==
<references />

[[Kategorie:Geometrische Figur]]
[[Kategorie:Diskrete Mathematik]]

Polyomino - Versionsgeschichte

imported>Ambross07: Linkfix mit AWB