Robinson-Schensted correspondence for symmetric group:S3

From Groupprops
Jump to: navigation, search
This article gives specific information, namely, Robinson-Schensted correspondence, about a particular group, namely: symmetric group:S3.
View Robinson-Schensted correspondence for particular groups | View other specific information about symmetric group:S3

This article describes the Robinson-Schensted correspondence in detail for symmetric group:S3.

Summary

Permutation (one-line notation) Partition (Young diagram) Position tableau Shape tableau
123 1 + 1 + 1 \begin{pmatrix}1 \\ 2 \\ 3 \\\end{pmatrix} \begin{pmatrix} 1 \\ 2 \\ 3 \\\end{pmatrix}
213 2 + 1 \begin{pmatrix}1 & 2 \\ 3 & \\\end{pmatrix} \begin{pmatrix}1 & 2 \\ 3 & \\\end{pmatrix}
132 2 + 1 \begin{pmatrix}1 & 3 \\ 2 & \\\end{pmatrix} \begin{pmatrix} 1 & 3 \\ 2 & \\\end{pmatrix}
231 2 + 1 \begin{pmatrix}1 & 2 \\ 3 & \\\end{pmatrix} \begin{pmatrix} 1 & 3 \\ 2 & \\\end{pmatrix}
312 2 + 1 \begin{pmatrix}1 & 3 \\ 2 & \\\end{pmatrix} \begin{pmatrix} 1 & 2 \\ 3 & \\\end{pmatrix}
321 3 \begin{pmatrix} 1 & 2 & 3 \\\end{pmatrix} \begin{pmatrix} 1 & 2 & 3 \\\end{pmatrix}

The rest of the article describes in detail how to obtain the position and shape tableaux for each permutation.

Identity permutation

The identity permutation on \{ 1,2,3 \} is given by the one-line notation 123. Here is how the position and shape tableau are constructed, letter by letter:

Position of letter read Value of letter read String read so far New position tableau New shape tableau Explanation
1 1 1 \begin{pmatrix} 1 \end{pmatrix} \begin{pmatrix} 1 \end{pmatrix} Both tableaux are originally empty. On reading the letter 1, the position tableau simply adds a box with 1. Since this is the first letter read, the shape tableau also adds a 1.
2 2 12 \begin{pmatrix}1 \\ 2 \\\end{pmatrix} \begin{pmatrix} 1 \\ 2 \\\end{pmatrix} Since the newly read letter 2 is greater than 1, it goes to the bottom of the first column. Since the newly added box to the Young diagram is at the bottom of the first column, the shape tableau also sees a 2 there.
3 3 123 \begin{pmatrix}1 \\ 2 \\ 3 \\\end{pmatrix} \begin{pmatrix}1 \\ 2 \\ 3 \\\end{pmatrix} Since the newly read letter 3 is greater than 2 (the largest entry in the first column), it goes to the bottom of the first column. Since the newly added box to the Young diagram is at the bottom of the first column, the shape tableau also sees a 3 there.

Transposition (1,2)

In one-line notation, this transposition is written as 213. Here is how the position and shape tableaux are constructed, letter by letter:

Position of letter read Value of letter read String read so far New position tableau New shape tableau Explanation
1 2 2 \begin{pmatrix} 2 \end{pmatrix} \begin{pmatrix} 1 \end{pmatrix} Both tableaux are originally empty. On reading the letter 2, the position tableau simply adds a box with 2. Since this is the first letter read, the shape tableau adds a 1.
2 1 21 \begin{pmatrix}1 & 2 \\\end{pmatrix} \begin{pmatrix} 1 & 2 \\\end{pmatrix} Since the newly read letter 1 is smaller than 2, it bumps the 2 off the first column. The 2 now settles into a fresh second column. Since the second new box has been added in the second column, this is indicated in the shape tableau.
3 3 213 \begin{pmatrix}1 & 2 \\ 3 \\\end{pmatrix} \begin{pmatrix}1 & 2 \\ 3 \\\end{pmatrix} Since the newly read letter 3 is greater than 1 (the largest entry in the first column), it goes to the bottom of the first column. Since the newly added box to the Young diagram is at the bottom of the first column, the shape tableau also sees a 3 there.

Transposition (2,3)

In one-line notation, the transposition is written as 132. Here is how the position and shape tableaux are constructed, letter by letter:

Position of letter read Value of letter read String read so far New position tableau New shape tableau Explanation
1 1 1 \begin{pmatrix} 1 \end{pmatrix} \begin{pmatrix} 1 \end{pmatrix} Both tableaux are originally empty. On reading the letter 1, the position tableau simply adds a box with 1. Since this is the first letter read, the shape tableau also adds a 1.
2 3 13 \begin{pmatrix}1 \\ 3 \\\end{pmatrix} \begin{pmatrix} 1 \\ 2 \\\end{pmatrix} Since the newly read letter 3 is larger than 1, it goes to the bottom of the position tableau. Correspondingly, the shape tableau adds a 2 at the place where the Young diagram was expanded.
3 2 132 \begin{pmatrix}1 & 3 \\ 2 \\\end{pmatrix} \begin{pmatrix}1 & 3 \\ 2 \\\end{pmatrix} Since the newly read letter 2 is smaller than 3 but bigger than 1, it bumps the 3 into the second coumn (newly created).

3-cycle (1,2,3)

In one-line notation, the 3-cycle is written as 231. Here is how the position and shape tableaux are constructed, letter by letter:

Position of letter read Value of letter read String read so far New position tableau New shape tableau Explanation
1 2 2 \begin{pmatrix} 2 \end{pmatrix} \begin{pmatrix} 1 \end{pmatrix} Both tableaux are originally empty. On reading the letter 2, the position tableau simply adds a box with 2. Since this is the first letter read, the shape tableau adds a 1.
2 3 23 \begin{pmatrix}2 \\ 3 \\\end{pmatrix} \begin{pmatrix} 1 \\ 2 \\\end{pmatrix} Since the newly read letter 3 is bigger than 2, it goes at the bottom of the first column. Since this is the second letter added, a 2 goes in the same place in the shape tableau to indicate the location of growth.
3 1 231 \begin{pmatrix}1 & 2 \\ 3 \\\end{pmatrix} \begin{pmatrix}1 & 3 \\ 2 \\\end{pmatrix} Since the newly read letter 1 is less than 2, it bumps the 2 off into a (newly created) second column. The new location of growth is thus the second column, and that's where a new box for the letter 3 is added in the shape tableau.

3-cycle (1,3,2)

In one-line notation, the 3-cycle is written as 312. Here is how the position and shape tableaux are constructed, letter by letter:

Position of letter read Value of letter read String read so far New position tableau New shape tableau Explanation
1 3 3 \begin{pmatrix} 3 \end{pmatrix} \begin{pmatrix} 1 \end{pmatrix} Both tableaux are originally empty. On reading the letter 3, the position tableau simply adds a box with 3. Since this is the first letter read, the shape tableau adds a 1.
2 1 31 \begin{pmatrix} 1 & 3 \\\end{pmatrix} \begin{pmatrix} 1 & 2 \\\end{pmatrix} The newly read 1 bumps off the 3 in the position tableau to a newly created second column. To indicate this change in shape, the shape tableau puts a 2 there.
3 2 312 \begin{pmatrix} 1 & 3 \\ 2 \\\end{pmatrix} \begin{pmatrix} 1 & 2 \\3\\\end{pmatrix} Since 2 is greater than 1 (the first column's unique entry) it goes to the bottom of the first column in the position tableau. The shape tableau adds a 3 to indicate the location of growth.

Transposition (1,3)

In one-line notation, the transposition is written as 321. Here is how the position and shape tableaux are constructed, letter by letter:

Position of letter read Value of letter read String read so far New position tableau New shape tableau Explanation
1 3 3 \begin{pmatrix} 3 \end{pmatrix} \begin{pmatrix} 1 \end{pmatrix} Both tableaux are originally empty. On reading the letter 3, the position tableau simply adds a box with 3. Since this is the first letter read, the shape tableau adds a 1.
2 2 32 \begin{pmatrix} 2 & 3 \end{pmatrix} \begin{pmatrix} 1 & 2 \end{pmatrix} The newly read 2 bumps off the 3 into the second column in the position tableau. The shape tableau adds a 2 to register the location of growth.
3 1 321 \begin{pmatrix} 1 & 2 & 3 \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 \end{pmatrix} The newly read 1 bumps the 2 to the second column, which in turn bumps the 3 into the third column. The shape column adds a 3 to register the location of growth.