Jeu de taquin
 |
 |
Jeu de taquin (wörtlich: neckendes oder ärgerndes Spiel) ist der französische Name für das 15-Rätsel oder auch 15-Puzzle.
Im Bereich der Kombinatorik wird als jeu de taquin eine Konstruktion nach Marcel Schützenberger bezeichnet, welche eine Äquivalenzrelation auf der Menge von Schief-Standard-Young-Tableaux definiert. Ein Jeu-de-taquin-slide ist eine Transformation, die die Zahlen in einem Tableau ähnlich wie bei einem 15-Puzzle verschiebt. Zwei Tableaus sind jeu-de-taquin-äquivalent genau dann, wenn eines in das andere vermöge einer Folge solcher Verschiebungen überführt werden kann.
Definition eines Jeu-de-taquins
[Bearbeiten | Quelltext bearbeiten]Gegeben sei ein Schief-Standard-Young-Tableau T der Form . Wähle eine angrenzende leere Zelle c, die dazu hinzugefügt werden kann, das heißt, dass c mindestens einen Rand mit einer Zelle aus T gemein haben muss und außerdem zusammen mit wieder ein Schieftableau bildet. Es gibt zwei Möglichkeiten, Verschiebungen durchzuführen, je nachdem, ob c oben links oder unten rechts von T liegt. Nehmen wir ersteres an. Dann verschieben wir die Zahl ihrer Nachbarzelle nach c; wenn c sowohl rechts als auch links eine Zahl als Nachbarn hat, dann wählen wir die kleinste von beiden, wenn nicht, dann sei die Verschiebung vollständig. Das Tableau, das wir nach dieser Transformation erhalten, ist wieder ein Schief-Young-Tableau.
