Robinson-Schensted-Knuth correspondence¶

AUTHORS:

• Travis Scrimshaw (2012-12-07): Initial version

EXAMPLES:

We can perform RSK and the inverse on a variety of objects:

sage: p = Tableau([[1,2,2],[2]]); q = Tableau([[1,3,3],[2]])
sage: gp = RSK_inverse(p, q); gp
[[1, 2, 3, 3], [2, 1, 2, 2]]
sage: RSK(*gp)
[[[1, 2, 2], [2]], [[1, 3, 3], [2]]]
sage: m = RSK_inverse(p, q, 'matrix'); m
[0 1]
[1 0]
[0 2]
sage: RSK(m)
[[[1, 2, 2], [2]], [[1, 3, 3], [2]]]


TESTS:

Check that it is a correspondence between all types of input and the input is preserved:

sage: t1 = Tableau([[1, 2, 5], [3], [4]])
sage: t2 = Tableau([[1, 2, 3], [4], [5]])
sage: gp = RSK_inverse(t1, t2); gp
[[1, 2, 3, 4, 5], [1, 4, 5, 3, 2]]
sage: w = RSK_inverse(t1, t2, 'word'); w
word: 14532
sage: m = RSK_inverse(t1, t2, 'matrix'); m
[1 0 0 0 0]
[0 0 0 1 0]
[0 0 0 0 1]
[0 0 1 0 0]
[0 1 0 0 0]
sage: p = RSK_inverse(t1, t2, 'permutation'); p
[1, 4, 5, 3, 2]
sage: t1
[[1, 2, 5], [3], [4]]
sage: t2
[[1, 2, 3], [4], [5]]
sage: RSK(*gp) == [t1, t2]
True
sage: RSK(w) == [t1, t2]
True
sage: RSK(m) == [t1, t2]
True
sage: RSK(p) == [t1, t2]
True
sage: gp
[[1, 2, 3, 4, 5], [1, 4, 5, 3, 2]]
sage: w
word: 14532
sage: m
[1 0 0 0 0]
[0 0 0 1 0]
[0 0 0 0 1]
[0 0 1 0 0]
[0 1 0 0 0]
sage: p
[1, 4, 5, 3, 2]


REFERENCES:

 [Knu1970] (1, 2) Donald E. Knuth. Permutations, matrices, and generalized Young tableaux. Pacific J. Math. Volume 34, Number 3 (1970), pp. 709-727. http://projecteuclid.org/euclid.pjm/1102971948
 [EG1987] (1, 2, 3, 4) Paul Edelman, Curtis Greene. Balanced Tableaux. Advances in Mathematics 63 (1987), pp. 42-99. http://www.sciencedirect.com/science/article/pii/0001870887900636
sage.combinat.rsk.RSK(obj1=None, obj2=None, insertion='RSK', check_standard=False, **options)

Perform the Robinson-Schensted-Knuth (RSK) correspondence.

The Robinson-Schensted-Knuth (RSK) correspondence is most naturally stated as a bijection between generalized permutations (also known as two-line arrays, biwords, ...) and pairs of semi-standard Young tableaux $$(P, Q)$$ of identical shape. The tableau $$P$$ is known as the insertion tableau and $$Q$$ is known as the recording tableau.

The basic operation is known as row insertion $$P \leftarrow k$$ (where $$P$$ is a given semi-standard Young tableau, and $$k$$ is an integer). Row insertion is a recursive algorithm which starts by setting $$k_0 = k$$, and in its $$i$$-th step inserts the number $$k_i$$ into the $$i$$-th row of $$P$$ by replacing the first integer greater than $$k_i$$ in the row by $$k_i$$ and defines $$k_{i+1}$$ as the integer that has been replaced. If no integer greater than $$k_i$$ exists in the $$i$$-th row, then $$k_i$$ is simply appended to the row and the algorithm terminates at this point.

Now the RSK algorithm starts by initializing two semi-standard tableaux $$P_0$$ and $$Q_0$$ as empty tableaux. For each nonnegative integer $$t$$ starting at $$0$$, take the pair $$(j_t, k_t)$$ from $$p$$ and set $$P_{t+1} = P_t \leftarrow k_t$$, and define $$Q_{t+1}$$ by adding a new box filled with $$j_t$$ to the tableau $$Q_t$$ at the same location the row insertion on $$P_t$$ ended (that is to say, adding $$j_t$$ such that $$P_{t+1}$$ and $$Q_{t+1}$$ have the same shape). The iterative process stops when $$t$$ reaches the size of $$p$$, and the pair $$(P_t, Q_t)$$ at this point is the image of $$p$$ under the Robinson-Schensted-Knuth correspondence.

This correspondence has been introduced in [Knu1970], where it has been referred to as “Construction A”.

For more information, see Chapter 7 in [Sta1999].

We also note that integer matrices are in bijection with generalized permutations. In addition, we can also convert any word $$w$$ (and any permutation) to a generalized permutation by considering the top line to be $$(1, 2, \ldots, n)$$ where $$n$$ is the length of $$w$$.

The optional argument insertion allows to specify an alternative insertion procedure to be used instead of the standard Robinson-Schensted-Knuth insertion. If the input is a reduced word of a permutation (i.e., a type $$A$$ Coxeter element), one can set insertion to 'EG', which gives Edelman-Greene insertion, an algorithm defined in [EG1987] Definition 6.20 (where it is referred to as Coxeter-Knuth insertion). The Edelman-Greene insertion is similar to the standard row insertion except that if $$k_i$$ and $$k_i + 1$$ both exist in row $$i$$, we only set $$k_{i+1} = k_i + 1$$ and continue.

INPUT:

• obj1, obj2 – Can be one of the following:
• A word in an ordered alphabet
• An integer matrix
• Two lists of equal length representing a generalized permutation
• Any object which has a method _rsk_iter() which returns an iterator over the object represented as generalized permutation or a pair of lists.
• insertion – (Default: 'RSK') The following types of insertion are currently supported:
• 'RSK' – Robinson-Schensted-Knuth
• 'EG' – Edelman-Greene (only for reduced words of permutations/type $$A$$ Coxeter elements)
• check_standard – (Default: False) Check if either of the resulting tableaux should be standard tableau.

EXAMPLES:

If we only give one line, we treat the top line as being $$(1, 2, \ldots, n)$$:

sage: RSK([3,3,2,4,1])
[[[1, 3, 4], [2], [3]], [[1, 2, 4], [3], [5]]]
sage: RSK(Word([3,3,2,4,1]))
[[[1, 3, 4], [2], [3]], [[1, 2, 4], [3], [5]]]
sage: RSK(Word([2,3,3,2,1,3,2,3]))
[[[1, 2, 2, 3, 3], [2, 3], [3]], [[1, 2, 3, 6, 8], [4, 7], [5]]]


With a generalized permutation:

sage: RSK([1, 2, 2, 2], [2, 1, 1, 2])
[[[1, 1, 2], [2]], [[1, 2, 2], [2]]]
sage: RSK(Word([1,1,3,4,4]), [1,4,2,1,3])
[[[1, 1, 3], [2], [4]], [[1, 1, 4], [3], [4]]]
sage: RSK([1,3,3,4,4], Word([6,2,2,1,7]))
[[[1, 2, 7], [2], [6]], [[1, 3, 4], [3], [4]]]


If we give it a matrix:

sage: RSK(matrix([[0,1],[2,1]]))
[[[1, 1, 2], [2]], [[1, 2, 2], [2]]]


We can also give it something looking like a matrix:

sage: RSK([[0,1],[2,1]])
[[[1, 1, 2], [2]], [[1, 2, 2], [2]]]


There are also variations of the insertion algorithm in RSK, and currently only Edelman-Greene insertion is supported:

sage: RSK([2,1,2,3,2], insertion='EG')
[[[1, 2, 3], [2, 3]], [[1, 3, 4], [2, 5]]]


We reproduce figure 6.4 in [EG1987]:

sage: RSK([2,3,2,1,2,3], insertion='EG')
[[[1, 2, 3], [2, 3], [3]], [[1, 2, 6], [3, 5], [4]]]


There is also RSK_inverse() which performs the inverse of the bijection on a pair of semistandard tableaux. We note that the inverse function takes 2 separate tableaux inputs, so to compose with RSK(), we need to use the python * on the output:

sage: RSK_inverse(*RSK([1, 2, 2, 2], [2, 1, 1, 2]))
[[1, 2, 2, 2], [2, 1, 1, 2]]
sage: P,Q = RSK([1, 2, 2, 2], [2, 1, 1, 2])
sage: RSK_inverse(P, Q)
[[1, 2, 2, 2], [2, 1, 1, 2]]


TESTS:

Empty objects:

sage: RSK(Permutation([]))
[[], []]
sage: RSK(Word([]))
[[], []]
sage: RSK(matrix([[]]))
[[], []]
sage: RSK([], [])
[[], []]
sage: RSK([[]])
[[], []]
sage: RSK(Word([]), insertion='EG')
[[], []]

sage.combinat.rsk.RSK_inverse(p, q, output='array', insertion='RSK')

Return the generalized permutation corresponding to the pair of tableaux $$(p,q)$$ under the inverse of the Robinson-Schensted-Knuth algorithm.

For more information on the bijeciton, see RSK().

INPUT:

• p, q – Two semi-standard tableaux of the same shape

• output – (Default: 'array') if q is semi-standard:

• 'array' – as a two-line array (i.e. generalized permutation or biword)
• 'matrix' – as an integer matrix

and if q is standard, we can have the output:

• 'word' – as a word

and additionally if p is standard, we can also have the output:

• 'permutation' – as a permutation
• insertion – (Default: RSK) The insertion algorithm used in the bijection. Currently only 'RSK' and 'EG' (Edelman-Greene) are supported.

EXAMPLES:

If both p and q are standard:

sage: t1 = Tableau([[1, 2, 5], [3], [4]])
sage: t2 = Tableau([[1, 2, 3], [4], [5]])
sage: RSK_inverse(t1, t2)
[[1, 2, 3, 4, 5], [1, 4, 5, 3, 2]]
sage: RSK_inverse(t1, t2, 'word')
word: 14532
sage: RSK_inverse(t1, t2, 'matrix')
[1 0 0 0 0]
[0 0 0 1 0]
[0 0 0 0 1]
[0 0 1 0 0]
[0 1 0 0 0]
sage: RSK_inverse(t1, t2, 'permutation')
[1, 4, 5, 3, 2]
sage: RSK_inverse(t1, t1, 'permutation')
[1, 4, 3, 2, 5]
sage: RSK_inverse(t2, t2, 'permutation')
[1, 2, 5, 4, 3]
sage: RSK_inverse(t2, t1, 'permutation')
[1, 5, 4, 2, 3]


If the first tableau is semistandard:

sage: p = Tableau([[1,2,2],[3]]); q = Tableau([[1,2,4],[3]])
sage: ret = RSK_inverse(p, q); ret
[[1, 2, 3, 4], [1, 3, 2, 2]]
sage: RSK_inverse(p, q, 'word')
word: 1322


In general:

sage: p = Tableau([[1,2,2],[2]]); q = Tableau([[1,3,3],[2]])
sage: RSK_inverse(p, q)
[[1, 2, 3, 3], [2, 1, 2, 2]]
sage: RSK_inverse(p, q, 'matrix')
[0 1]
[1 0]
[0 2]


Using the Edelman-Greene insertion:

sage: pq = RSK([2,1,2,3,2], insertion='RSK'); pq
[[[1, 2, 2], [2, 3]], [[1, 3, 4], [2, 5]]]
sage: RSK_inverse(*pq, insertion='EG')
[2, 1, 2, 3, 2]


Note

Currently the constructor of Tableau accept as input lists that are not even tableaux but only filling of a partition diagram. This feature should not be used with RSK_inverse.

TESTS:

From empty tableaux:

sage: RSK_inverse(Tableau([]), Tableau([]))
[[], []]


Check that RSK_inverse() is the inverse of RSK() on the different types of inputs/outputs:

sage: f = lambda p: RSK_inverse(*RSK(p), output='permutation')
sage: all(p == f(p) for n in range(7) for p in Permutations(n))
True
sage: all(RSK_inverse(*RSK(w), output='word') == w for n in range(4) for w in Words(5, n))
True
sage: from sage.combinat.integer_matrices import IntegerMatrices
sage: M = IntegerMatrices([1,2,2,1], [3,1,1,1])
sage: all(RSK_inverse(*RSK(m), output='matrix') == m for m in M)
True

sage: n = ZZ.random_element(200)
sage: p = Permutations(n).random_element()
sage: is_fine = True if p == f(p) else p ; is_fine
True


Same for Edelman-Greene (but we are checking only the reduced words that can be obtained using the reduced_word() method from permutations):

sage: g = lambda w: RSK_inverse(*RSK(w, insertion='EG'), insertion='EG', output='permutation')
sage: all(p.reduced_word() == g(p.reduced_word()) for n in range(7) for p in Permutations(n))
True

sage: n = ZZ.random_element(200)
sage: p = Permutations(n).random_element()
sage: is_fine = True if p == f(p) else p ; is_fine
True


Both tableaux must be of the same shape:

sage: RSK_inverse(Tableau([[1,2,3]]), Tableau([[1,2]]))
Traceback (most recent call last):
...
ValueError: p(=[[1, 2, 3]]) and q(=[[1, 2]]) must have the same shape

sage.combinat.rsk.robinson_schensted_knuth(obj1=None, obj2=None, insertion='RSK', check_standard=False, **options)

Perform the Robinson-Schensted-Knuth (RSK) correspondence.

The Robinson-Schensted-Knuth (RSK) correspondence is most naturally stated as a bijection between generalized permutations (also known as two-line arrays, biwords, ...) and pairs of semi-standard Young tableaux $$(P, Q)$$ of identical shape. The tableau $$P$$ is known as the insertion tableau and $$Q$$ is known as the recording tableau.

The basic operation is known as row insertion $$P \leftarrow k$$ (where $$P$$ is a given semi-standard Young tableau, and $$k$$ is an integer). Row insertion is a recursive algorithm which starts by setting $$k_0 = k$$, and in its $$i$$-th step inserts the number $$k_i$$ into the $$i$$-th row of $$P$$ by replacing the first integer greater than $$k_i$$ in the row by $$k_i$$ and defines $$k_{i+1}$$ as the integer that has been replaced. If no integer greater than $$k_i$$ exists in the $$i$$-th row, then $$k_i$$ is simply appended to the row and the algorithm terminates at this point.

Now the RSK algorithm starts by initializing two semi-standard tableaux $$P_0$$ and $$Q_0$$ as empty tableaux. For each nonnegative integer $$t$$ starting at $$0$$, take the pair $$(j_t, k_t)$$ from $$p$$ and set $$P_{t+1} = P_t \leftarrow k_t$$, and define $$Q_{t+1}$$ by adding a new box filled with $$j_t$$ to the tableau $$Q_t$$ at the same location the row insertion on $$P_t$$ ended (that is to say, adding $$j_t$$ such that $$P_{t+1}$$ and $$Q_{t+1}$$ have the same shape). The iterative process stops when $$t$$ reaches the size of $$p$$, and the pair $$(P_t, Q_t)$$ at this point is the image of $$p$$ under the Robinson-Schensted-Knuth correspondence.

This correspondence has been introduced in [Knu1970], where it has been referred to as “Construction A”.

For more information, see Chapter 7 in [Sta1999].

We also note that integer matrices are in bijection with generalized permutations. In addition, we can also convert any word $$w$$ (and any permutation) to a generalized permutation by considering the top line to be $$(1, 2, \ldots, n)$$ where $$n$$ is the length of $$w$$.

The optional argument insertion allows to specify an alternative insertion procedure to be used instead of the standard Robinson-Schensted-Knuth insertion. If the input is a reduced word of a permutation (i.e., a type $$A$$ Coxeter element), one can set insertion to 'EG', which gives Edelman-Greene insertion, an algorithm defined in [EG1987] Definition 6.20 (where it is referred to as Coxeter-Knuth insertion). The Edelman-Greene insertion is similar to the standard row insertion except that if $$k_i$$ and $$k_i + 1$$ both exist in row $$i$$, we only set $$k_{i+1} = k_i + 1$$ and continue.

INPUT:

• obj1, obj2 – Can be one of the following:
• A word in an ordered alphabet
• An integer matrix
• Two lists of equal length representing a generalized permutation
• Any object which has a method _rsk_iter() which returns an iterator over the object represented as generalized permutation or a pair of lists.
• insertion – (Default: 'RSK') The following types of insertion are currently supported:
• 'RSK' – Robinson-Schensted-Knuth
• 'EG' – Edelman-Greene (only for reduced words of permutations/type $$A$$ Coxeter elements)
• check_standard – (Default: False) Check if either of the resulting tableaux should be standard tableau.

EXAMPLES:

If we only give one line, we treat the top line as being $$(1, 2, \ldots, n)$$:

sage: RSK([3,3,2,4,1])
[[[1, 3, 4], [2], [3]], [[1, 2, 4], [3], [5]]]
sage: RSK(Word([3,3,2,4,1]))
[[[1, 3, 4], [2], [3]], [[1, 2, 4], [3], [5]]]
sage: RSK(Word([2,3,3,2,1,3,2,3]))
[[[1, 2, 2, 3, 3], [2, 3], [3]], [[1, 2, 3, 6, 8], [4, 7], [5]]]


With a generalized permutation:

sage: RSK([1, 2, 2, 2], [2, 1, 1, 2])
[[[1, 1, 2], [2]], [[1, 2, 2], [2]]]
sage: RSK(Word([1,1,3,4,4]), [1,4,2,1,3])
[[[1, 1, 3], [2], [4]], [[1, 1, 4], [3], [4]]]
sage: RSK([1,3,3,4,4], Word([6,2,2,1,7]))
[[[1, 2, 7], [2], [6]], [[1, 3, 4], [3], [4]]]


If we give it a matrix:

sage: RSK(matrix([[0,1],[2,1]]))
[[[1, 1, 2], [2]], [[1, 2, 2], [2]]]


We can also give it something looking like a matrix:

sage: RSK([[0,1],[2,1]])
[[[1, 1, 2], [2]], [[1, 2, 2], [2]]]


There are also variations of the insertion algorithm in RSK, and currently only Edelman-Greene insertion is supported:

sage: RSK([2,1,2,3,2], insertion='EG')
[[[1, 2, 3], [2, 3]], [[1, 3, 4], [2, 5]]]


We reproduce figure 6.4 in [EG1987]:

sage: RSK([2,3,2,1,2,3], insertion='EG')
[[[1, 2, 3], [2, 3], [3]], [[1, 2, 6], [3, 5], [4]]]


There is also RSK_inverse() which performs the inverse of the bijection on a pair of semistandard tableaux. We note that the inverse function takes 2 separate tableaux inputs, so to compose with RSK(), we need to use the python * on the output:

sage: RSK_inverse(*RSK([1, 2, 2, 2], [2, 1, 1, 2]))
[[1, 2, 2, 2], [2, 1, 1, 2]]
sage: P,Q = RSK([1, 2, 2, 2], [2, 1, 1, 2])
sage: RSK_inverse(P, Q)
[[1, 2, 2, 2], [2, 1, 1, 2]]


TESTS:

Empty objects:

sage: RSK(Permutation([]))
[[], []]
sage: RSK(Word([]))
[[], []]
sage: RSK(matrix([[]]))
[[], []]
sage: RSK([], [])
[[], []]
sage: RSK([[]])
[[], []]
sage: RSK(Word([]), insertion='EG')
[[], []]

sage.combinat.rsk.robinson_schensted_knuth_inverse(p, q, output='array', insertion='RSK')

Return the generalized permutation corresponding to the pair of tableaux $$(p,q)$$ under the inverse of the Robinson-Schensted-Knuth algorithm.

For more information on the bijeciton, see RSK().

INPUT:

• p, q – Two semi-standard tableaux of the same shape

• output – (Default: 'array') if q is semi-standard:

• 'array' – as a two-line array (i.e. generalized permutation or biword)
• 'matrix' – as an integer matrix

and if q is standard, we can have the output:

• 'word' – as a word

and additionally if p is standard, we can also have the output:

• 'permutation' – as a permutation
• insertion – (Default: RSK) The insertion algorithm used in the bijection. Currently only 'RSK' and 'EG' (Edelman-Greene) are supported.

EXAMPLES:

If both p and q are standard:

sage: t1 = Tableau([[1, 2, 5], [3], [4]])
sage: t2 = Tableau([[1, 2, 3], [4], [5]])
sage: RSK_inverse(t1, t2)
[[1, 2, 3, 4, 5], [1, 4, 5, 3, 2]]
sage: RSK_inverse(t1, t2, 'word')
word: 14532
sage: RSK_inverse(t1, t2, 'matrix')
[1 0 0 0 0]
[0 0 0 1 0]
[0 0 0 0 1]
[0 0 1 0 0]
[0 1 0 0 0]
sage: RSK_inverse(t1, t2, 'permutation')
[1, 4, 5, 3, 2]
sage: RSK_inverse(t1, t1, 'permutation')
[1, 4, 3, 2, 5]
sage: RSK_inverse(t2, t2, 'permutation')
[1, 2, 5, 4, 3]
sage: RSK_inverse(t2, t1, 'permutation')
[1, 5, 4, 2, 3]


If the first tableau is semistandard:

sage: p = Tableau([[1,2,2],[3]]); q = Tableau([[1,2,4],[3]])
sage: ret = RSK_inverse(p, q); ret
[[1, 2, 3, 4], [1, 3, 2, 2]]
sage: RSK_inverse(p, q, 'word')
word: 1322


In general:

sage: p = Tableau([[1,2,2],[2]]); q = Tableau([[1,3,3],[2]])
sage: RSK_inverse(p, q)
[[1, 2, 3, 3], [2, 1, 2, 2]]
sage: RSK_inverse(p, q, 'matrix')
[0 1]
[1 0]
[0 2]


Using the Edelman-Greene insertion:

sage: pq = RSK([2,1,2,3,2], insertion='RSK'); pq
[[[1, 2, 2], [2, 3]], [[1, 3, 4], [2, 5]]]
sage: RSK_inverse(*pq, insertion='EG')
[2, 1, 2, 3, 2]


Note

Currently the constructor of Tableau accept as input lists that are not even tableaux but only filling of a partition diagram. This feature should not be used with RSK_inverse.

TESTS:

From empty tableaux:

sage: RSK_inverse(Tableau([]), Tableau([]))
[[], []]


Check that RSK_inverse() is the inverse of RSK() on the different types of inputs/outputs:

sage: f = lambda p: RSK_inverse(*RSK(p), output='permutation')
sage: all(p == f(p) for n in range(7) for p in Permutations(n))
True
sage: all(RSK_inverse(*RSK(w), output='word') == w for n in range(4) for w in Words(5, n))
True
sage: from sage.combinat.integer_matrices import IntegerMatrices
sage: M = IntegerMatrices([1,2,2,1], [3,1,1,1])
sage: all(RSK_inverse(*RSK(m), output='matrix') == m for m in M)
True

sage: n = ZZ.random_element(200)
sage: p = Permutations(n).random_element()
sage: is_fine = True if p == f(p) else p ; is_fine
True


Same for Edelman-Greene (but we are checking only the reduced words that can be obtained using the reduced_word() method from permutations):

sage: g = lambda w: RSK_inverse(*RSK(w, insertion='EG'), insertion='EG', output='permutation')
sage: all(p.reduced_word() == g(p.reduced_word()) for n in range(7) for p in Permutations(n))
True

sage: n = ZZ.random_element(200)
sage: p = Permutations(n).random_element()
sage: is_fine = True if p == f(p) else p ; is_fine
True


Both tableaux must be of the same shape:

sage: RSK_inverse(Tableau([[1,2,3]]), Tableau([[1,2]]))
Traceback (most recent call last):
...
ValueError: p(=[[1, 2, 3]]) and q(=[[1, 2]]) must have the same shape

sage.combinat.rsk.to_matrix(t, b)

Return the integer matrix corresponding to a two-line array.

INPUT:

• t – The top line of the array
• b – The bottom line of the array

OUTPUT:

An $$m \times n$$-matrix (where $$m$$ and $$n$$ are the maximum entries in $$t$$ and $$b$$ respectively) whose $$(i, j)$$-th entry, for any $$i$$ and $$j$$, is the number of all positions $$k$$ satisfying $$t_k = i$$ and $$b_k = j$$.

EXAMPLES:

sage: from sage.combinat.rsk import to_matrix
sage: to_matrix([1, 1, 3, 3, 4], [2, 3, 1, 1, 3])
[0 1 1]
[0 0 0]
[2 0 0]
[0 0 1]


Previous topic

$$q$$-Bernoulli Numbers

Next topic

Sidon sets and their generalizations, Sidon $$g$$-sets