Jeu de taquin

Jeu de taquin is de Franse naam voor de schuifpuzzel. Het is in de combinatoriek de naam van een operatie, aan Marcel Schützenberger toegeschreven, die een equivalentierelatie definieert op de verzameling van young-tableaus. Een jeu de taquin-verschuiving zorgt ervoor dat de getallen in een young-tableau op dezelfde manier als in een schuifpuzzel worden verschoven.

Gegeven een young-tableau ${\displaystyle T}$ met vorm ${\displaystyle \lambda \setminus \mu }$. Kies een lege cel ${\displaystyle c}$ die aan het tableau ${\displaystyle T}$ kan worden toegevoegd zodat er een opnieuw young-tableau ontstaat. ${\displaystyle c}$ kan linksboven of rechtsonder aan ${\displaystyle T}$ worden toegevoegd. In het eerste geval verschuiven we het getal in de buurcel van ${\displaystyle c}$ naar ${\displaystyle c}$. Als ${\displaystyle 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 rijen 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 young-tableau, dat jeu de taquin-equivalent is met het oorspronkelijke tableau.

Als ${\displaystyle c}$ onderaan rechts aan ${\displaystyle 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.