Jeu de taquin

Jeu de taquin is de Franse naam voor de schuifpuzzel of "15 puzzle". In de combinatoriek is het de naam van een operatie, aan Marcel Schützenberger toegeschreven, die een equivalentierelatie definieert op de verzameling van scheef-standaard Young-tableaus. Een "jeu de taquin"-verschuiving verschuift de getallen in een tableau op een gelijkaardige manier als in een schuifpuzzel.

Voorbeeld van een jeu de taquin-verschuiving

Gegeven een scheef-standaard Young-tableau $T$ met vorm $\lambda \setminus \mu$. Kies een lege cel $c$ die aan het tableau $T$ kan toegevoegd worden zodanig dat er opnieuw een (scheef) Young-tableau ontstaat. $c$ kan linksboven of rechtsonder aan $T$ worden toegevoegd. In het eerste geval verschuiven we het getal in de buurcel van $c$ naar $c.$ Als $c$ zowel een rechter- als een benedenbuurcel heeft, nemen we het kleinste van de twee getallen in die cellen. Op die manier blijft de eigenschap behouden dat het tableau strikt stijgende lijnen en kolommen moet hebben. Herhaal dit tot de nieuwe lege cel geen rechter- en benedenburen heeft. Deze cel wordt dan geschrapt. Het resulterende tableau is een nieuw standaard Young-tableau (al dan niet scheef), dat "jeu de taquin"-equivalent is met het oorspronkelijke tableau.

Als $c$ onderaan rechts aan $T$ wordt toegevoegd, wordt de bewerking andersom uitgevoerd. Het getal uit de linker- of bovenbuur wordt naar de lege cel verschoven; als de twee buren aanwezig zijn kiezen we het grootste van de twee getallen.