www.wikidata.de-de.nina.az

Polyomino Ein Kunstwort abgeleitet von Domino ist eine Fläche die aus n displaystyle n zusammenhängenden Quadraten beste

Polyomino

Ein Polyomino (Kunstwort, abgeleitet von Domino) ist eine Fläche, die aus zusammenhängenden Quadraten besteht.

Für kleine sind auch die Bezeichnungen Monomino (), Domino (), Tromino (), Tetromino (), Pentomino (), Hexomino (), Heptomino (), Oktomino (), Nonomino oder Enneomino (), Dekomino (), Undekomino (), Dodekomino () usw. üblich.

Definition Bearbeiten

Ein Polyomino oder -Mino ist eine Figur , die aus kongruenten Quadraten besteht, für die gilt

  1. je zwei Quadrate haben entweder keinen Punkt oder eine Ecke oder eine Kante gemeinsam,
  2. zu je zwei verschiedenen Quadraten und aus gibt es eine Folge von benachbarten Quadraten aus .

Dabei heißen zwei Quadrate benachbart, wenn die Menge ihrer gemeinsamen Punkte eine Seite ist. Folgende Beispiele stellen demnach keine Polyominos dar.

Für besondere Anwendungen wird zusätzlich gefordert:

Polyomino mit Loch

Darstellung über Zusammenhangsgraphen Bearbeiten

Jedem Polyomino lässt sich ein Zusammenhangsgraph zuordnen, indem man jedes Quadrat aus als Knoten und das Benachbartsein zweier Quadrate durch eine Kante wiedergibt. Nachfolgend wird dies anhand der 5 Tetrominos dargestellt.

Konstruktion Bearbeiten

die 5 Tetrominos

Bestimmung der Anzahlen Bearbeiten

Es gibt verschiedene Ansätze, die Anzahl der Polyominos zu bestimmen. Am häufigsten wird nur bis auf Kongruenz unterschieden. In praktischen Sachverhalten sind jedoch häufig nur orientierungserhaltende Bewegungen für das Zur-Deckung-Bringen zugelassen, also nur Drehungen und Verschiebungen und keine Achsenspiegelungen. Auch bei dem Spiel Tetris ist dies der Fall. Kongruente Polyominos, die eine unterschiedliche Orientierung besitzen, werden dabei als verschieden angesehen

nicht-orientierungserhaltende Bewegung
die 12 Pentominos
die 35 Hexominos

bezeichnet die Anzahl Polyominos, die sich bis auf Kongruenz aus Quadraten bilden lassen. ist die Anzahl unter Beachtung der Orientierung, d. h. zueinander spiegelbildliche (wie oben illustriert) werden als verschieden betrachtet. 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 ist von Interesse.

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 an abweichende Zahlen.

Rekursive Fortsetzung Bearbeiten

Algorithmus Bearbeiten

Man kann leicht ein rekursives Verfahren beschreiben, das es gestattet, aus der Kenntnis aller -Minos alle -Minos zu gewinnen. Es lässt sich zunächst zeigen, dass es zu einem -Mino ein -Mino und ein Quadrat gibt, so dass ist. Dadurch kann von der Kenntnis der Klassen der -Minos ausgegangen werden. Durch Anfügen eines Quadrates entsteht je ein Repräsentant der Klassen der -Minos. Auf diese Weise kann auch die Anzahl der Klassen bestimmt werden. Wir verfahren wie folgt.

Wir nummerieren die Klassen der -Minos durch und beginnen mit einem Repräsentanten der ersten Klasse, und betrachten systematisch alle Lagen eines Quadrates , die überhaupt zu einem -Mino führen können. Diese Lagen werden mit oder markiert, je nachdem, ob das entsprechende -Mino zu den bisherigen kongruent ist oder nicht. Nach gleicher Weise wird bei den nächsten Klassen der -Minos verfahren. Natürlich kann dabei ein -Mino entstehen, welches zu einem aus vorangegangenen Schritten kongruent ist. Solche werden mit einem Lagekästchen bezeichnet .

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

Beispiel Bearbeiten

Der rekursive Algorithmus soll bei der Ermittlung der Pentominos aus Tetrominos eingesetzt werden.

Computergestützt Bearbeiten

Auf der Grundlage dieses Verfahrens lassen sich die mit Computern bestimmen. Dabei lassen sich Polyominos durch eine Matrix mit 0 und 1 wie in folgendem Beispiel beschreiben.

wird zu

Hexominos Bearbeiten

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

Zusammengesetzte ähnliche Polyominos (Reptiles) Bearbeiten

Figur 1
Figur 2
Figur 3

Allgemeine Reptiles-Definitionen Bearbeiten

  • Ä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 die Anzahl der ähnlichen Teilfiguren, so wird die zusammengesetzte Figur rep--Figur genannt.

Anwendungsbeispiele zu Polyominos Bearbeiten

Im Folgenden sei . Unter den verschiedenen Arten von Polyominos gibt es rep--Figuren und rep--Figuren (Figuren 1, 2 und 3).

Verwendung Bearbeiten

Packungen Bearbeiten

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 Bearbeiten

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 (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 -Minos für als Spielmaterial verwendet werden. Auch die Spiele 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 (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. 2001 erschien das Spiel Rumis, welches dreidimensionale Steine (Polywürfel) verwendet.

Pädagogik Bearbeiten

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-Parkette genannt.

Verwandte Themen Bearbeiten

  • Polywürfel (auch Polykuben) – das dreidimensionale Pendant mit Würfeln

Literatur Bearbeiten

  • Solomon W. Golomb: Polyominoes. Puzzles, Patterns, Problems, and Packings. 2. erweiterte Auflage. Princeton University Press, Princeton 1994, ISBN 0-691-08573-0

Weblinks Bearbeiten

Commons: Polyomino – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise Bearbeiten

  1. Folge A000105 in OEIS
  2. Folge A000988 in OEIS
  3. Folge A001168 in OEIS
  4. Beispielsweise Folge A000104 in OEIS
  5. 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
  6. George E. Martin: Polyominoes: A Guide to Puzzles and Problems in Tiling, AMS/MAA, Washington 1991
  7. Übersicht Polyomino-Spiele bei Boardgamegeek
  8. Rezension von Rumis bei hall9000.de
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Ein Polyomino Kunstwort abgeleitet von Domino ist eine Flache die aus n displaystyle n zusammenhangenden Quadraten besteht Fur kleine n displaystyle n sind auch die Bezeichnungen Monomino n 1 displaystyle n 1 Domino n 2 displaystyle n 2 Tromino n 3 displaystyle n 3 Tetromino n 4 displaystyle n 4 Pentomino n 5 displaystyle n 5 Hexomino n 6 displaystyle n 6 Heptomino n 7 displaystyle n 7 Oktomino n 8 displaystyle n 8 Nonomino oder Enneomino n 9 displaystyle n 9 Dekomino n 10 displaystyle n 10 Undekomino n 11 displaystyle n 11 Dodekomino n 12 displaystyle n 12 usw ublich Inhaltsverzeichnis 1 Definition 1 1 Darstellung uber Zusammenhangsgraphen 2 Konstruktion 2 1 Bestimmung der Anzahlen 2 2 Rekursive Fortsetzung 2 2 1 Algorithmus 2 2 2 Beispiel 2 2 3 Computergestutzt 2 2 4 Hexominos 3 Zusammengesetzte ahnliche Polyominos Reptiles 3 1 Allgemeine Reptiles Definitionen 3 2 Anwendungsbeispiele zu Polyominos 4 Verwendung 4 1 Packungen 4 2 Spieleindustrie 4 3 Padagogik 5 Verwandte Themen 6 Literatur 7 Weblinks 8 EinzelnachweiseDefinition BearbeitenEin Polyomino oder n displaystyle n nbsp Mino ist eine Figur P displaystyle P nbsp die aus n 1 displaystyle n geq 1 nbsp kongruenten Quadraten besteht fur die gilt je zwei Quadrate haben entweder keinen Punkt oder eine Ecke oder eine Kante gemeinsam zu je zwei verschiedenen Quadraten Q 1 displaystyle Q 1 nbsp und Q displaystyle Q nbsp aus P displaystyle P nbsp gibt es eine Folge Q 1 Q 2 Q k 1 Q displaystyle Q 1 Q 2 ldots Q k 1 Q nbsp von benachbarten Quadraten aus P displaystyle P nbsp Dabei heissen zwei Quadrate benachbart wenn die Menge ihrer gemeinsamen Punkte eine Seite ist Folgende Beispiele stellen demnach keine Polyominos dar nbsp 1 ungultig nbsp 2 ungultig nbsp 3 ungultig nbsp 4 ungultigFur besondere Anwendungen wird zusatzlich gefordert P displaystyle P nbsp bildet eine einfach zusammenhangende Punktmenge nbsp Polyomino mit LochDarstellung uber Zusammenhangsgraphen Bearbeiten Jedem Polyomino P displaystyle P nbsp lasst sich ein Zusammenhangsgraph zuordnen indem man jedes Quadrat aus P displaystyle P nbsp als Knoten und das Benachbartsein zweier Quadrate durch eine Kante wiedergibt Nachfolgend wird dies anhand der 5 Tetrominos dargestellt nbsp nbsp nbsp nbsp nbsp Konstruktion Bearbeiten nbsp die 5 TetrominosBestimmung der Anzahlen Bearbeiten Es gibt verschiedene Ansatze die Anzahl der Polyominos zu bestimmen Am haufigsten wird nur bis auf Kongruenz unterschieden In praktischen Sachverhalten sind jedoch haufig nur orientierungserhaltende Bewegungen fur das Zur Deckung Bringen zugelassen also nur Drehungen und Verschiebungen und keine Achsenspiegelungen Auch bei dem Spiel Tetris ist dies der Fall Kongruente Polyominos die eine unterschiedliche Orientierung besitzen werden dabei als verschieden angesehen nbsp nbsp nicht orientierungserhaltende Bewegung nbsp die 12 Pentominos nbsp die 35 HexominosA n displaystyle A n nbsp bezeichnet die Anzahl Polyominos die sich bis auf Kongruenz aus n displaystyle n nbsp Quadraten bilden lassen A n displaystyle A n nbsp ist die Anzahl unter Beachtung der Orientierung d h zueinander spiegelbildliche wie oben illustriert werden als verschieden betrachtet A n displaystyle A n nbsp bezeichnet die Anzahl unter Beachtung der Orientierung und aller moglichen Lagen dabei werden sogar zwei zueinander gedrehte aber sonst gleiche Polyominos als verschieden angesehen Vor allem A n displaystyle A n nbsp ist von Interesse n displaystyle n nbsp A n displaystyle A n nbsp 1 A n displaystyle A n nbsp 2 A n displaystyle A n nbsp 3 1 1 1 12 1 1 23 2 2 64 5 7 195 12 18 636 35 60 2167 108 196 7608 369 704 2 7259 1 285 2 500 9 91010 4 655 9 189 36 44611 17 073 33 896 135 26812 63 600 126 759 505 86113 238 591 476 270 1 903 89014 901 971 1 802 312 7 204 87415 3 426 576 6 849 777 27 394 666Werden ausschliesslich einfach zusammenhangende Polyominos gezahlt so ergeben sich von n 7 displaystyle n 7 nbsp an abweichende Zahlen 4 Rekursive Fortsetzung Bearbeiten Algorithmus Bearbeiten Man kann leicht ein rekursives Verfahren beschreiben das es gestattet aus der Kenntnis aller n 1 displaystyle n 1 nbsp Minos n 2 displaystyle n geq 2 nbsp alle n displaystyle n nbsp Minos zu gewinnen Es lasst sich zunachst zeigen dass es zu einem n displaystyle n nbsp Mino P 2 displaystyle P 2 nbsp n 2 displaystyle n geq 2 nbsp ein n 1 displaystyle n 1 nbsp Mino P 1 displaystyle P 1 nbsp und ein Quadrat Q displaystyle Q nbsp gibt so dass P 2 P 1 Q displaystyle P 2 P 1 cup Q nbsp ist Dadurch kann von der Kenntnis der Klassen der n 1 displaystyle n 1 nbsp Minos ausgegangen werden Durch Anfugen eines Quadrates entsteht je ein Reprasentant der Klassen der n displaystyle n nbsp Minos Auf diese Weise kann auch die Anzahl A n displaystyle A n nbsp der Klassen bestimmt werden Wir verfahren wie folgt Wir nummerieren die Klassen der n 1 displaystyle n 1 nbsp Minos durch und beginnen mit einem Reprasentanten P displaystyle P nbsp der ersten Klasse und betrachten systematisch alle Lagen eines Quadrates Q displaystyle Q nbsp die uberhaupt zu einem n displaystyle n nbsp Mino P Q displaystyle P cup Q nbsp fuhren konnen Diese Lagen werden mit nbsp oder nbsp markiert je nachdem ob das entsprechende n displaystyle n nbsp Mino zu den bisherigen kongruent ist oder nicht Nach gleicher Weise wird bei den nachsten Klassen der n 1 displaystyle n 1 nbsp Minos verfahren Naturlich kann dabei ein n displaystyle n nbsp Mino entstehen welches zu einem aus vorangegangenen Schritten kongruent ist Solche werden mit einem Lagekastchen nbsp bezeichnet i 1 2 displaystyle i 1 2 ldots nbsp Nach endlich vielen Schritten bricht das Verfahren ab und es liefert einen Reprasentanten fur jede Klasse der n displaystyle n nbsp Minos Beispiel Bearbeiten Der rekursive Algorithmus soll bei der Ermittlung der Pentominos aus Tetrominos eingesetzt werden Computergestutzt Bearbeiten Auf der Grundlage dieses Verfahrens lassen sich die A n displaystyle A n nbsp mit Computern bestimmen Dabei lassen sich Polyominos durch eine Matrix mit 0 und 1 wie in folgendem Beispiel beschreiben nbsp wird zu 1 1 1 0 1 0 1 1 1 0 0 0 displaystyle begin pmatrix 1 amp 1 amp 1 amp 0 1 amp 0 amp 1 amp 1 1 amp 0 amp 0 amp 0 end pmatrix nbsp Hexominos Bearbeiten Eine Untergruppe von 11 der 35 Hexominos stellen geometrisch gesehen das Netz eines Wurfels dar da er durch 6 quadratische Flachen begrenzt wird Zusammengesetzte ahnliche Polyominos Reptiles Bearbeiten nbsp Figur 1 nbsp Figur 2 nbsp Figur 3Allgemeine Reptiles Definitionen Bearbeiten Ahnliche Figuren die sich luckenlos zu einer grosseren Figur die zu den kleineren Figuren ahnlich ist zusammensetzen lassen werden im Englischen als Reptiles Abkurzung fur replicating tiles bezeichnet Ist n displaystyle n nbsp die Anzahl der ahnlichen Teilfiguren so wird die zusammengesetzte Figur rep n displaystyle n nbsp Figur genannt Anwendungsbeispiele zu Polyominos Bearbeiten Im Folgenden sei k N displaystyle k in mathbb N nbsp Unter den verschiedenen Arten von Polyominos gibt es rep 4 k displaystyle 4 k nbsp Figuren und rep 16 k displaystyle 16 k nbsp Figuren Figuren 1 2 und 3 5 6 Verwendung BearbeitenPackungen Bearbeiten Welche notwendigen und hinreichenden Bedingungen bestehen fur die positiv ganzzahligen Seitenlangen eines Rechteckes damit dieses mit bestimmten Sorten von Polyominos gepackt werden kann Spieleindustrie Bearbeiten 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 Polywurfel z B BlockOut zuruckgreifen Ein Brettspiel das dem Computerspiel Tetris nahe kommt ist FITS 2009 von Reiner Knizia Es nahm sich das Computerspiel ausdrucklich zum Vorbild Weitere neuere Brettspiele sind das 2000 erschienene Blokus sowie Ubongo 2005 wo jeweils die verschiedenen grossen n displaystyle n nbsp Minos fur n 1 5 displaystyle n 1 5 nbsp als Spielmaterial verwendet werden Auch die Spiele Patchwork 2014 und Cottage Garden 2016 von Uwe Rosenberg sowie Die Baumeister von Arkadia 2006 von Rudiger Dorn NMBR 9 2017 von Peter Wichmann und Barenpark 2017 von Phil Walker Harding nutzen diese Formen als Legeteile Bei Ein Fest fur Odin 2016 von Uwe Rosenberg sind die Plattchen rechteckig angeordnet Auch dieses Spiel wird als Polyomino Spiel eingestuft 7 2001 erschien das Spiel Rumis welches dreidimensionale Steine Polywurfel verwendet 8 Padagogik Bearbeiten Die Bausteine finden in der Grundschule Verwendung und dienen der Verbesserung der raumlichen Vorstellung Ziel ist es zu einer vorgegebenen Menge von Bausteinen Figuren zu finden oder fur vorgegebene Figuren eine Zerlegung in die entsprechenden Bausteine Es ist nicht moglich aus allen 5 moglichen Tetronimos ein 5 4 Rechteck zu erstellen Es ist auch nicht moglich ohne Mehrfachverwendung eines Winkelstucks ein 4 4 Quadrat aus Tetrominos zu erstellen Die verwendeten Figuren werden wenn fur sie Tetrominos verwendet werden die den Buchstaben L T und Z ahnlich sind auch LTZ Parkette genannt Verwandte Themen BearbeitenPolywurfel auch Polykuben das dreidimensionale Pendant mit WurfelnLiteratur BearbeitenSolomon W Golomb Polyominoes Puzzles Patterns Problems and Packings 2 erweiterte Auflage Princeton University Press Princeton 1994 ISBN 0 691 08573 0Weblinks Bearbeiten nbsp Commons Polyomino Sammlung von Bildern Videos und Audiodateien Polyominos bei Wolfram Mathworld Gerard s Universal Polyomino Solver Puzzlespiel mit Polyominos 3D Spiel zur Fullung mit Polyominos 2D Memento vom 20 April 2008 im Internet Archive Ebene Figuren Vielecke Anwendung fur Kinder Memento vom 28 September 2007 im Internet Archive Einzelnachweise Bearbeiten Folge A000105 in OEIS Folge A000988 in OEIS Folge A001168 in OEIS Beispielsweise Folge A000104 in OEIS Claudi Alsina Roger B Nelsen Perlen der Mathematik 20 geometrische Figuren als Ausgangspunkte fur mathematische Erkundungsreisen Springer Spektrum Springer Verlag GmbH Berlin Heidelberg 2015 ISBN 978 3 662 45460 2 Seiten 51 bis 54 George E Martin Polyominoes A Guide to Puzzles and Problems in Tiling AMS MAA Washington 1991 Ubersicht Polyomino Spiele bei Boardgamegeek Rezension von Rumis bei hall9000 de Abgerufen von https de wikipedia org w index php title Polyomino amp oldid 239492472