Namespaces
Variants
Actions

Difference between revisions of "Jeu de taquin"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
Line 1: Line 1:
The French name of a puzzle game introduced in France by H.E. Lucas. It consists of fifteen wooden squares, numbered from one to fifteen, which can be moved in a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j110/j110030/j1100301.png" />-box. A single space is free, and must be used to restore the consecutive numbering of the smaller squares. This game is still on sale with some variations (a typical example is the  "puzzle"  program distributed with the Macintosh operating system).
+
{{TEX|done}}
 +
The French name of a puzzle game introduced in France by H.E. Lucas. It consists of fifteen wooden squares, numbered from one to fifteen, which can be moved in a $(4\times4)$-box. A single space is free, and must be used to restore the consecutive numbering of the smaller squares. This game is still on sale with some variations (a typical example is the  "puzzle"  program distributed with the Macintosh operating system).
  
 
By analogy, this same name has been given by M.-P. Schützenberger (cf. [[#References|[a4]]], [[#References|[a5]]]) to a graphical representation of the plactic, or Knuth, congruences.
 
By analogy, this same name has been given by M.-P. Schützenberger (cf. [[#References|[a4]]], [[#References|[a5]]]) to a graphical representation of the plactic, or Knuth, congruences.
Line 7: Line 8:
 
Further, A. Lascoux and Schützenberger have established that the equivalence relation generated by this set of relations is compatible with concatenation. The quotient [[Monoid|monoid]] (which is in bijection with the set of semi-standard tableaux) is known as the plactic monoid. They have also given the fundamental properties of this monoid, in [[#References|[a1]]].
 
Further, A. Lascoux and Schützenberger have established that the equivalence relation generated by this set of relations is compatible with concatenation. The quotient [[Monoid|monoid]] (which is in bijection with the set of semi-standard tableaux) is known as the plactic monoid. They have also given the fundamental properties of this monoid, in [[#References|[a1]]].
  
The plactic (or Knuth) congruences are the following: Let the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j110/j110030/j1100302.png" /> be totally ordered and suppose that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j110/j110030/j1100303.png" />. Then
+
The plactic (or Knuth) congruences are the following: Let the alphabet $X$ be totally ordered and suppose that $a<b<c$. Then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j110/j110030/j1100304.png" /></td> </tr></table>
+
$$bca\equiv bac,acb\equiv cab,$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j110/j110030/j1100305.png" /></td> </tr></table>
+
$$aba\equiv baa,bba\equiv bab.$$
  
 
This equivalence can be transferred to (semi-standard) skew Young tableaux (cf. [[Skew Young tableau|Skew Young tableau]]) in the following way. Two skew Young tableaux are equivalent if and only if one can be obtained from the other by a succession of local transformations corresponding, respectively, to the four plactic congruences:
 
This equivalence can be transferred to (semi-standard) skew Young tableaux (cf. [[Skew Young tableau|Skew Young tableau]]) in the following way. Two skew Young tableaux are equivalent if and only if one can be obtained from the other by a succession of local transformations corresponding, respectively, to the four plactic congruences:
Line 21: Line 22:
 
Under this equivalence relation each class of skew Young tableaux contains exactly one Young tableau. This statement is in fact equivalent to Knuth's theorem. This game of transformation of tableaux is what is called jeu de taquin.
 
Under this equivalence relation each class of skew Young tableaux contains exactly one Young tableau. This statement is in fact equivalent to Knuth's theorem. This game of transformation of tableaux is what is called jeu de taquin.
  
It can be used to provide an alternative to the original Schensted insertion algorithm as generalized by Knuth. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j110/j110030/j1100306.png" /> be a word. Consider any skew Young tableau such that, reading its entries from left to right and from bottom to top, one obtains precisely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j110/j110030/j1100307.png" />. Then apply jeu de taquin transformations to that tableau a Young tableau is obtained. This last tableau depends only on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j110/j110030/j1100308.png" />, but not on the choices of starting tableau and of transformations. It is exactly the first tableau of the pair associated to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j110/j110030/j1100309.png" />.
+
It can be used to provide an alternative to the original Schensted insertion algorithm as generalized by Knuth. Let $w$ be a word. Consider any skew Young tableau such that, reading its entries from left to right and from bottom to top, one obtains precisely $w$. Then apply jeu de taquin transformations to that tableau a Young tableau is obtained. This last tableau depends only on $w$, but not on the choices of starting tableau and of transformations. It is exactly the first tableau of the pair associated to $w$.
  
For example, start with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/j/j110/j110030/j11003010.png" />. One can produce the following sequence of transformations. Note that the starting tableau has the  "reading property"  mentioned above.
+
For example, start with $w=abcba$. One can produce the following sequence of transformations. Note that the starting tableau has the  "reading property"  mentioned above.
  
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/j110030b.gif" />
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/j110030b.gif" />

Revision as of 15:07, 8 August 2014

The French name of a puzzle game introduced in France by H.E. Lucas. It consists of fifteen wooden squares, numbered from one to fifteen, which can be moved in a $(4\times4)$-box. A single space is free, and must be used to restore the consecutive numbering of the smaller squares. This game is still on sale with some variations (a typical example is the "puzzle" program distributed with the Macintosh operating system).

By analogy, this same name has been given by M.-P. Schützenberger (cf. [a4], [a5]) to a graphical representation of the plactic, or Knuth, congruences.

The Robinson–Schensted construction (cf. Robinson–Schensted correspondence) establishes a bijection between a permutation and a pair of standard Young tableaux (cf. Young tableau and [a2]). It is a fundamental tool in the combinatorics of representations of symmetric groups (cf. [a3]). This construction has been extended to words (i.e. allowing repetitions) by D. Knuth. In the latter case, the first tableau is no longer standard, but semi-standard (the entries are increasing along the columns and non-decreasing along the rows). Knuth has also shown that two words correspond to the same semi-standard tableau if and only if it is possible to obtain one from the other by a succession of certain commutations of letters.

Further, A. Lascoux and Schützenberger have established that the equivalence relation generated by this set of relations is compatible with concatenation. The quotient monoid (which is in bijection with the set of semi-standard tableaux) is known as the plactic monoid. They have also given the fundamental properties of this monoid, in [a1].

The plactic (or Knuth) congruences are the following: Let the alphabet $X$ be totally ordered and suppose that $a<b<c$. Then

$$bca\equiv bac,acb\equiv cab,$$

$$aba\equiv baa,bba\equiv bab.$$

This equivalence can be transferred to (semi-standard) skew Young tableaux (cf. Skew Young tableau) in the following way. Two skew Young tableaux are equivalent if and only if one can be obtained from the other by a succession of local transformations corresponding, respectively, to the four plactic congruences:

Figure: j110030a

Under this equivalence relation each class of skew Young tableaux contains exactly one Young tableau. This statement is in fact equivalent to Knuth's theorem. This game of transformation of tableaux is what is called jeu de taquin.

It can be used to provide an alternative to the original Schensted insertion algorithm as generalized by Knuth. Let $w$ be a word. Consider any skew Young tableau such that, reading its entries from left to right and from bottom to top, one obtains precisely $w$. Then apply jeu de taquin transformations to that tableau a Young tableau is obtained. This last tableau depends only on $w$, but not on the choices of starting tableau and of transformations. It is exactly the first tableau of the pair associated to $w$.

For example, start with $w=abcba$. One can produce the following sequence of transformations. Note that the starting tableau has the "reading property" mentioned above.

Figure: j110030b

References

[a1] A. Lascoux, M.-P. Schützenberger, "Le monoïde plaxique" , Non Commutative Structures in Algebra and Geometric Combinatorics, Arco Felice (1978) , Quaderni Ricerca Sci. , 109 , Consiglio Naz. Ricerche (1981) pp. 129–156
[a2] D. Knuth, "The art of computer programming" , 3 , Addison-Wesley (1973)
[a3] I.G. Macdonald, "Symmetric functions and Hall polynomials" , Clarendon Press (1995) (Edition: Second)
[a4] M.-P. Schützenberger, "Sur une construction de Gilbert de B. Robinson" , Algèbre (1971/2) , Sém. P. Dubreuil 25e année , 1: 8 , Secrétariat Math. Univ. Paris (1973)
[a5] M.-P. Schützenberger, "La correspondance de Robinson" , Combinatoire et Représentations du Groupe Symétrique, Strasbourg (1976) , Lecture Notes in Mathematics , 579 , Springer (1977) pp. 59–135
How to Cite This Entry:
Jeu de taquin. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Jeu_de_taquin&oldid=18760
This article was adapted from an original article by J. Désarménien (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article