Jeu de taquin

Jeu de taquin (literally teasing or ärgerndes game ) is the French name for the 15 - puzzle or 15 - puzzle.

In the area of ​​combinatorics is called jeu de taquin a design by Marcel Schützenberger, which defines an equivalence relation on the set of skew -standard Young tableaux. A jeu de taquin -slide is a transformation that moves the numbers in a table similar to a 15 - puzzle. Two panels are jeu -de- taquin - equivalent if and only if one can be transformed into the other by virtue of a sequence of such shifts.

Definition of a jeu-de - taquins

Given a skew standard Young tableau T of shape. Choose an adjacent empty cell c, which can be added to it, which means that c is at least one edge with a cell from T have common needs and also forms again a skew tableau with. There are two ways to perform shifts, depending on whether c is top left or bottom right of t. Suppose the former. Then we move the number of its neighboring cell to c; if c has both right and left a number as neighbors, we choose the smallest of the two, if not, then the shift is complete. The panel, which we obtained after this transformation is again a skew Young tableau.