RobinsonSchenstedKnuth correspondence¶
AUTHORS:
 Travis Scrimshaw (20121207): Initial version
 Chaman Agrawal (20190624): Refactoring on the Rule class
Introduction¶
The RobinsonSchenstedKnuth (RSK) correspondence is most naturally stated as a bijection between generalized permutations (also known as twoline arrays, biwords, …) and pairs of semistandard Young tableaux \((P, Q)\) of identical shape.
The basic operation in the RSK correspondence is a row insertion \(P \leftarrow k\) (where \(P\) is a given semistandard Young tableau, and \(k\) is an integer). Different insertion algorithms have been implemented for the RSK correspondence and can be specified as an argument in the function call.
EXAMPLES:
We can perform RSK and its inverse map 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) # RSK of a biword
[[[1, 2, 2], [2]], [[1, 3, 3], [2]]]
sage: RSK([2,3,2,1,2,3]) # RobinsonSchensted of a word
[[[1, 2, 2, 3], [2], [3]], [[1, 2, 5, 6], [3], [4]]]
sage: RSK([2,3,2,1,2,3], insertion=RSK.rules.EG) # EdelmanGreene
[[[1, 2, 3], [2, 3], [3]], [[1, 2, 6], [3, 5], [4]]]
sage: m = RSK_inverse(p, q, 'matrix'); m # output as matrix
[0 1]
[1 0]
[0 2]
sage: RSK(m) # RSK of a matrix
[[[1, 2, 2], [2]], [[1, 3, 3], [2]]]
Insertions currently available¶
The following insertion algorithms for RSK correspondence are currently available:
 RSK insertion (
RuleRSK
)  EdelmanGreene insertion (
RuleEG
), an algorithm defined in [EG1987] Definition 6.20 (where it is referred to as CoxeterKnuth insertion).  Hecke RSK algorithm (
RuleHecke
) , defined using the Hecke insertion studied in [BKSTY06] (but using rows instead of columns).  Dual RSK insertion (
RuleDualRSK
).  CoRSK insertion (
RuleCoRSK
), defined in [GR2018v5sol].
Implementing your own insertion rule¶
The functions RSK()
and RSK_inverse()
are written so that it
is easy to implement insertion algorithms you come across in your research.
To implement your own insertion algorithm, you first need to import the base class for a rule:
sage: from sage.combinat.rsk import Rule
Using the Rule
class as parent class for your insertion rule,
first implement the insertion and the reverse insertion algorithm
for RSK()
and RSK_inverse()
respectively (as methods
forward_rule
and backward_rule
). If your insertion algorithm
uses the same forward and backward rules as RuleRSK
, differing
only in how an entry is inserted into a row, then this is not
necessary, and it suffices to merely implement the
insertion
and reverse_insertion
methods.
For more information, see Rule
.
REFERENCES:
[Knu1970]  (1, 2) Donald E. Knuth. Permutations, matrices, and generalized Young tableaux. Pacific J. Math. Volume 34, Number 3 (1970), pp. 709727. http://projecteuclid.org/euclid.pjm/1102971948 
[EG1987]  (1, 2, 3, 4) Paul Edelman, Curtis Greene. Balanced Tableaux. Advances in Mathematics 63 (1987), pp. 4299. https://doi.org/10.1016/00018708(87)900636 
[BKSTY06]  (1, 2, 3) A. Buch, A. Kresch, M. Shimozono, H. Tamvakis, and A. Yong. Stable Grothendieck polynomials and \(K\)theoretic factor sequences. Math. Ann. 340 Issue 2, (2008), pp. 359–382. arXiv math/0601514v1. 
[GR2018v5sol]  (1, 2, 3) Darij Grinberg, Victor Reiner. Hopf Algebras In Combinatorics, arXiv 1409.8356v5, available with solutions at https://arxiv.org/src/1409.8356v5/anc/HopfCombv73withsolutions.pdf 

class
sage.combinat.rsk.
InsertionRules
¶ Bases:
object
Catalog of rules for RSKlike insertion algorithms.

dualRSK
¶ alias of
RuleDualRSK


sage.combinat.rsk.
RSK
(obj1=None, obj2=None, insertion=<class 'sage.combinat.rsk.RuleRSK'>, check_standard=False, **options)¶ Perform the RobinsonSchenstedKnuth (RSK) correspondence.
The RobinsonSchenstedKnuth (RSK) correspondence (also known as the RSK algorithm) is most naturally stated as a bijection between generalized permutations (also known as twoline arrays, biwords, …) and pairs of semistandard 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 semistandard 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\) (we start counting the rows at \(0\)) 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.
A generalized permutation (or biword) is a list \(((j_0, k_0), (j_1, k_1), \ldots, (j_{\ell1}, k_{\ell1}))\) of pairs such that the letters \(j_0, j_1, \ldots, j_{\ell1}\) are weakly increasing (that is, \(j_0 \leq j_1 \leq \cdots \leq j_{\ell1}\)), whereas the letters \(k_i\) satisfy \(k_i \leq k_{i+1}\) whenever \(j_i = j_{i+1}\). The \(\ell\)tuple \((j_0, j_1, \ldots, j_{\ell1})\) is called the top line of this generalized permutation, whereas the \(\ell\)tuple \((k_0, k_1, \ldots, k_{\ell1})\) is called its bottom line.
Now the RSK algorithm, applied to a generalized permutation \(p = ((j_0, k_0), (j_1, k_1), \ldots, (j_{\ell1}, k_{\ell1}))\) (encoded as a lexicographically sorted list of pairs) starts by initializing two semistandard 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 a new box with entry \(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 RobinsonSchenstedKnuth correspondence.
This correspondence has been introduced in [Knu1970], where it has been referred to as “Construction A”.
For more information, see Chapter 7 in [StaEC2].
We also note that integer matrices are in bijection with generalized permutations. Furthermore, we can convert any word \(w\) (and, in particular, any permutation) to a generalized permutation by considering the top row 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 RobinsonSchenstedKnuth insertion.INPUT:
obj1, obj2
– can be one of the following: a word in an ordered alphabet (in this case,
obj1
is said word, andobj2
isNone
)  an integer matrix
 two lists of equal length representing a generalized permutation (namely, the lists \((j_0, j_1, \ldots, j_{\ell1})\) and \((k_0, k_1, \ldots, k_{\ell1})\) represent the generalized permutation \(((j_0, k_0), (j_1, k_1), \ldots, (j_{\ell1}, k_{\ell1}))\))
 any object which has a method
_rsk_iter()
which returns an iterator over the object represented as generalized permutation or a pair of lists (in this case,obj1
is said object, andobj2
isNone
).
 a word in an ordered alphabet (in this case,
insertion
– (default:RSK.rules.RSK
) the following types of insertion are currently supported:RSK.rules.RSK
(or'RSK'
) – RobinsonSchenstedKnuth insertion (RuleRSK
)RSK.rules.EG
(or'EG'
) – EdelmanGreene insertion (only for reduced words of permutations/elements of a type \(A\) Coxeter group) (RuleEG
)RSK.rules.Hecke
(or'hecke'
) – Hecke insertion (only guaranteed for generalized permutations whose top row is strictly increasing) (RuleHecke
)RSK.rules.dualRSK
(or'dualRSK'
) – Dual RSK insertion (only for strict biwords) (RuleDualRSK
)RSK.rules.coRSK
(or'coRSK'
) – CoRSK insertion (only for strict cobiwords) (RuleCoRSK
)
check_standard
– (default:False
) check if either of the resulting tableaux is a standard tableau, and if so, typecast it as such
For precise information about constraints on the input and output, as well as the definition of the algorithm (if it is not standard RSK), see the particular
Rule
class.EXAMPLES:
If we only input one row, it is understood that the top row should be \((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]]]
We can provide 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]]]
We can provide a matrix:
sage: RSK(matrix([[0,1],[2,1]])) [[[1, 1, 2], [2]], [[1, 2, 2], [2]]]
We can also provide something looking like a matrix:
sage: RSK([[0,1],[2,1]]) [[[1, 1, 2], [2]], [[1, 2, 2], [2]]]
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 as inputs, so to compose withRSK()
, 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]]

sage.combinat.rsk.
RSK_inverse
(p, q, output='array', insertion=<class 'sage.combinat.rsk.RuleRSK'>)¶ Return the generalized permutation corresponding to the pair of tableaux \((p, q)\) under the inverse of the RobinsonSchenstedKnuth correspondence.
For more information on the bijection, see
RSK()
.INPUT:
p
,q
– two semistandard tableaux of the same shape, or (in the case when Hecke insertion is used) an increasing tableau and a setvalued tableau of the same shape (see the note below for the format of the setvalued tableau)output
– (default:'array'
) ifq
is semistandard:'array'
– as a twoline array (i.e. generalized permutation or biword)'matrix'
– as an integer matrix
and if
q
is standard, we can also 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.rules.RSK
) the insertion algorithm used in the bijection. Currently the following are supported:RSK.rules.RSK
(or'RSK'
) – RobinsonSchenstedKnuth insertion (RuleRSK
)RSK.rules.EG
(or'EG'
) – EdelmanGreene insertion (only for reduced words of permutations/elements of a type \(A\) Coxeter group) (RuleEG
)RSK.rules.Hecke
(or'hecke'
) – Hecke insertion (only guaranteed for generalized permutations whose top row is strictly increasing) (RuleHecke
)RSK.rules.dualRSK
(or'dualRSK'
) – Dual RSK insertion (only for strict biwords) (RuleDualRSK
)RSK.rules.coRSK
(or'coRSK'
) – CoRSK insertion (only for strict cobiwords) (RuleCoRSK
)
For precise information about constraints on the input and output, see the particular
Rule
class.Note
In the case of Hecke insertion, the input variable
q
should be a setvalued tableau, encoded as a tableau whose entries are strictly increasing tuples of positive integers. Each such tuple encodes the set of its entries.EXAMPLES:
If both
p
andq
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 Hecke insertion:
sage: w = [5, 4, 3, 1, 4, 2, 5, 5] sage: pq = RSK(w, insertion=RSK.rules.Hecke) sage: RSK_inverse(*pq, insertion=RSK.rules.Hecke, output='list') [5, 4, 3, 1, 4, 2, 5, 5]
Note
The constructor of
Tableau
accepts not only semistandard tableaux, but also arbitrary lists that are fillings of a partition diagram. (And such lists are used, e.g., for the setvalued tableauq
that is passed toRSK_inverse(p, q, insertion='hecke')
.) The user is responsible for ensuring that the tableaux passed toRSK_inverse
are of the right types (semistandard, standard, increasing, setvalued as needed).

class
sage.combinat.rsk.
Rule
¶ Bases:
sage.structure.unique_representation.UniqueRepresentation
Generic base class for an insertion rule for RSK correspondence.
An instance of this class should implement a method
insertion()
(which can be applied to a letterj
and a listr
, and modifiesr
in place by “bumping”j
into it appropriately; it then returns the bumpedout entry orNone
if no such entry exists) and a methodreverse_insertion()
(which does the same but for reverse bumping). It may also implement_backward_format_output()
and_forward_format_output()
if the RSK correspondence should return something other than (semi)standard tableaux (in the forward direction) and matrices or biwords (in the backward direction). Theto_pairs()
method should also be overridden if the input for the (forward) RSK correspondence is not the usual kind of biwords (i.e., pairs of two \(n\)tuples \([a_1, a_2, \ldots, a_n]\) and \([b_1, b_2, \ldots, b_n]\) satisfying \((a_1, b_1) \leq (a_2, b_2) \leq \cdots \leq (a_n, b_n)\) in lexicographic order). Finally, itforward_rule()
andbackward_rule()
have to be overridden if the overall structure of the RSK correspondence differs from that of classical RSK (see, e.g., the case of Hecke insertion, in which a letter bumped into a row may change a different row).
backward_rule
(p, q, output)¶ Return the generalized permutation obtained by applying reverse insertion to a pair of tableaux
(p, q)
.INPUT:
p
,q
– two tableaux of the same shape.output
– (default:'array'
) ifq
is semistandard:'array'
– as a twoline array (i.e. generalized permutation or biword)'matrix'
– as an integer matrix
and if
q
is standard, we can also have the output:'word'
– as a word
and additionally if
p
is standard, we can also have the output:'permutation'
– as a permutation
EXAMPLES:
sage: from sage.combinat.rsk import RuleRSK sage: t1 = Tableau([[1, 3, 4], [2], [3]]) sage: t2 = Tableau([[1, 2, 4], [3], [5]]) sage: RuleRSK().backward_rule(t1, t2, 'array') [[1, 2, 3, 4, 5], [3, 3, 2, 4, 1]] sage: t1 = Tableau([[1, 1, 1, 3, 7]]) sage: t2 = Tableau([[1, 2, 3, 4, 5]]) sage: RuleRSK().backward_rule(t1, t2, 'array') [[1, 2, 3, 4, 5], [1, 1, 1, 3, 7]] sage: t1 = Tableau([[1, 3], [3], [6], [7]]) sage: t2 = Tableau([[1, 4], [2], [3], [5]]) sage: RuleRSK().backward_rule(t1, t2, 'array') [[1, 2, 3, 4, 5], [7, 6, 3, 3, 1]]

forward_rule
(obj1, obj2, check_standard=False, check=True)¶ Return a pair of tableaux obtained by applying forward insertion to the generalized permutation
[obj1, obj2]
.INPUT:
obj1, obj2
– can be one of the following ways to represent a generalized permutation (or, equivalently, biword): two lists
obj1
andobj2
of equal length, to be interpreted as the top row and the bottom row of the biword;  a matrix
obj1
of nonnegative integers, to be interpreted as the generalized permutation in matrix form (in this case,obj2
isNone
);  a word
obj1
in an ordered alphabet, to be interpreted as the bottom row of the biword (in this case,obj2
isNone
; the top row of the biword is understood to be \((1, 2, \ldots, n)\) by default);  any object
obj1
which has a method_rsk_iter()
, as long as this method returns an iterator yielding pairs of numbers, which then are interperted as top entries and bottom entries in the biword (in this case,obj2
isNone
).
 two lists
check_standard
– (default:False
) check if either of the resulting tableaux is a standard tableau, and if so, typecast it as suchcheck
– (default:True
) whether to check thatobj1
andobj2
actually define a valid biword.
EXAMPLES:
sage: from sage.combinat.rsk import RuleRSK sage: RuleRSK().forward_rule([3,3,2,4,1], None) [[[1, 3, 4], [2], [3]], [[1, 2, 4], [3], [5]]] sage: RuleRSK().forward_rule([1, 1, 1, 3, 7], None) [[[1, 1, 1, 3, 7]], [[1, 2, 3, 4, 5]]] sage: RuleRSK().forward_rule([7, 6, 3, 3, 1], None) [[[1, 3], [3], [6], [7]], [[1, 4], [2], [3], [5]]]

to_pairs
(obj1=None, obj2=None, check=True)¶ Given a valid input for the RSK algorithm, such as two \(n\)tuples
obj1
\(= [a_1, a_2, \ldots, a_n]\) andobj2
\(= [b_1, b_2, \ldots, b_n]\) forming a biword (i.e., satisfying \(a_1 \leq a_2 \leq \cdots \leq a_n\), and if \(a_i = a_{i+1}\), then \(b_i \leq b_{i+1}\)), or a matrix (“generalized permutation”), or a single word, return the array \([(a_1, b_1), (a_2, b_2), \ldots, (a_n, b_n)]\).INPUT:
obj1, obj2
– anything representing a biword (see the doc offorward_rule()
for the encodings accepted).check
– (default:True
) whether to check thatobj1
andobj2
actually define a valid biword.
EXAMPLES:
sage: from sage.combinat.rsk import Rule sage: list(Rule().to_pairs([1, 2, 2, 2], [2, 1, 1, 2])) [(1, 2), (2, 1), (2, 1), (2, 2)] sage: m = Matrix(ZZ, 3, 2, [0,1,1,0,0,2]) ; m [0 1] [1 0] [0 2] sage: list(Rule().to_pairs(m)) [(1, 2), (2, 1), (3, 2), (3, 2)]


class
sage.combinat.rsk.
RuleCoRSK
¶ Bases:
sage.combinat.rsk.RuleRSK
A rule modeling the CoRSK insertion.
CoRSK insertion differs from classical RSK insertion in the following ways:
 The input (in terms of biwords) is no longer a biword, but rather a strict cobiword – i.e., a pair of two lists \([a_1, a_2, \ldots, a_n]\) and \([b_1, b_2, \ldots, b_n]\) that satisfy the strict inequalities \((a_1, b_1) \widetilde{<} (a_2, b_2) \widetilde{<} \cdots \widetilde{<} (a_n, b_n)\), where the binary relation \(\widetilde{<}\) on pairs of integers is defined by having \((u_1, v_1) \widetilde{<} (u_2, v_2)\) if and only if either \(u_1 < u_2\) or (\(u_1 = u_2\) and \(v_1 > v_2\)). In terms of matrices, this means that the input is not an arbitrary matrix with nonnegative integer entries, but rather a \(\{0, 1\}\)matrix (i.e., a matrix whose entries are \(0\)’s and \(1\)’s).
 The output still consists of two tableaux \((P, Q)\) of equal shapes, but rather than both of them being semistandard, now \(Q\) is rowstrict (i.e., its transpose is semistandard) while \(P\) is semistandard.
Bumping proceeds in the same way as for RSK insertion.
The RSK and CoRSK algorithms agree for permutation matrices.
For more information, see Section A.4 in [Ful1997] (specifically, construction (1d)) or the second solution to Exercise 2.7.12(a) in [GR2018v5sol].
EXAMPLES:
sage: RSK([1,2,5,3,1], insertion = RSK.rules.coRSK) [[[1, 1, 3], [2], [5]], [[1, 2, 3], [4], [5]]] sage: RSK(Word([2,3,3,2,1,3,2,3]), insertion = RSK.rules.coRSK) [[[1, 2, 2, 3, 3], [2, 3], [3]], [[1, 2, 3, 6, 8], [4, 7], [5]]] sage: RSK(Word([3,3,2,4,1]), insertion = RSK.rules.coRSK) [[[1, 3, 4], [2], [3]], [[1, 2, 4], [3], [5]]] sage: from sage.combinat.rsk import to_matrix sage: RSK(to_matrix([1, 1, 3, 3, 4], [3, 2, 2, 1, 3]), insertion = RSK.rules.coRSK) [[[1, 2, 3], [2], [3]], [[1, 3, 4], [1], [3]]]
Using coRSK insertion with a \(\{0, 1\}\)matrix:
sage: RSK(matrix([[0,1],[1,0]]), insertion = RSK.rules.coRSK) [[[1], [2]], [[1], [2]]]
We can also give it something looking like a matrix:
sage: RSK([[0,1],[1,0]], insertion = RSK.rules.coRSK) [[[1], [2]], [[1], [2]]]
We can also use the inverse correspondence:
sage: RSK_inverse(*RSK([1, 2, 2, 2], [2, 3, 2, 1], ....: insertion=RSK.rules.coRSK),insertion=RSK.rules.coRSK) [[1, 2, 2, 2], [2, 3, 2, 1]] sage: P,Q = RSK([1, 2, 2, 2], [2, 3, 2, 1],insertion=RSK.rules.coRSK) sage: RSK_inverse(P, Q, insertion=RSK.rules.coRSK) [[1, 2, 2, 2], [2, 3, 2, 1]]
When applied to two standard tableaux, backwards coRSK insertion behaves identically to the usual backwards RSK insertion:
sage: t1 = Tableau([[1, 2, 5], [3], [4]]) sage: t2 = Tableau([[1, 2, 3], [4], [5]]) sage: RSK_inverse(t1, t2, insertion=RSK.rules.coRSK) [[1, 2, 3, 4, 5], [1, 4, 5, 3, 2]] sage: RSK_inverse(t1, t2, 'word', insertion=RSK.rules.coRSK) word: 14532 sage: RSK_inverse(t1, t2, 'matrix', insertion=RSK.rules.coRSK) [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', insertion=RSK.rules.coRSK) [1, 4, 5, 3, 2] sage: RSK_inverse(t1, t1, 'permutation', insertion=RSK.rules.coRSK) [1, 4, 3, 2, 5] sage: RSK_inverse(t2, t2, 'permutation', insertion=RSK.rules.coRSK) [1, 2, 5, 4, 3] sage: RSK_inverse(t2, t1, 'permutation', insertion=RSK.rules.coRSK) [1, 5, 4, 2, 3]
For coRSK, the first tableau is semistandard while the second tableau is transpose semistandard:
sage: p = Tableau([[1,2,2],[5]]); q = Tableau([[1,2,4],[3]]) sage: ret = RSK_inverse(p, q, insertion=RSK.rules.coRSK); ret [[1, 2, 3, 4], [1, 5, 2, 2]] sage: RSK_inverse(p, q, 'word', insertion=RSK.rules.coRSK) word: 1522

backward_rule
(p, q, output)¶ Return the strict cobiword obtained by applying reverse coRSK insertion to a pair of tableaux
(p, q)
.INPUT:
p
,q
– two tableaux of the same shape.output
– (default:'array'
) ifq
is rowstrict:'array'
– as a twoline array (i.e. strict cobiword)'matrix'
– as a \(\{0, 1\}\)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
EXAMPLES:
sage: from sage.combinat.rsk import RuleCoRSK sage: t1 = Tableau([[1, 1, 2], [2, 3], [4]]) sage: t2 = Tableau([[1, 4, 5], [1, 4], [2]]) sage: RuleCoRSK().backward_rule(t1, t2, 'array') [[1, 1, 2, 4, 4, 5], [4, 2, 1, 3, 1, 2]]

to_pairs
(obj1=None, obj2=None, check=True)¶ Given a valid input for the coRSK algorithm, such as two \(n\)tuples
obj1
\(= [a_1, a_2, \ldots, a_n]\) andobj2
\(= [b_1, b_2, \ldots, b_n]\) forming a strict cobiword (i.e., satisfying \(a_1 \leq a_2 \leq \cdots \leq a_n\), and if \(a_i = a_{i+1}\), then \(b_i > b_{i+1}\)), or a \(\{0, 1\}\)matrix (“rook placement”), or a single word, return the array \([(a_1, b_1), (a_2, b_2), \ldots, (a_n, b_n)]\).INPUT:
obj1, obj2
– anything representing a strict cobiword (see the doc offorward_rule()
for the encodings accepted).check
– (default:True
) whether to check thatobj1
andobj2
actually define a valid strict cobiword.
EXAMPLES:
sage: from sage.combinat.rsk import RuleCoRSK sage: list(RuleCoRSK().to_pairs([1, 2, 2, 2], [2, 3, 2, 1])) [(1, 2), (2, 3), (2, 2), (2, 1)] sage: RuleCoRSK().to_pairs([1, 2, 2, 2], [1, 2, 3, 3]) Traceback (most recent call last): ... ValueError: invalid strict cobiword sage: m = Matrix(ZZ, 3, 2, [0,1,1,1,0,1]) ; m [0 1] [1 1] [0 1] sage: list(RuleCoRSK().to_pairs(m)) [(1, 2), (2, 2), (2, 1), (3, 2)] sage: m = Matrix(ZZ, 3, 2, [0,1,1,0,0,2]) ; m [0 1] [1 0] [0 2] sage: RuleCoRSK().to_pairs(m) Traceback (most recent call last): ... ValueError: coRSK requires a {0, 1}matrix

class
sage.combinat.rsk.
RuleDualRSK
¶ Bases:
sage.combinat.rsk.Rule
A rule modeling the Dual RSK insertion.
Dual RSK insertion differs from classical RSK insertion in the following ways:
 The input (in terms of biwords) is no longer an arbitrary biword, but rather a strict biword (i.e., a pair of two lists \([a_1, a_2, \ldots, a_n]\) and \([b_1, b_2, \ldots, b_n]\) that satisfy the strict inequalities \((a_1, b_1) < (a_2, b_2) < \cdots < (a_n, b_n)\) in the lexicographic order). In terms of matrices, this means that the input is not an arbitrary matrix with nonnegative integer entries, but rather a \(\{0, 1\}\)matrix (i.e., a matrix whose entries are \(0\)’s and \(1\)’s).
 The output still consists of two tableaux \((P, Q)\) of equal shapes, but rather than both of them being semistandard, now \(P\) is rowstrict (i.e., its transpose is semistandard) while \(Q\) is semistandard.
 The main difference is in the way bumping works. Namely, when a number \(k_i\) is inserted into the \(i\)th row of \(P\), it bumps out the first integer greater or equal to \(k_i\) in this row (rather than greater than \(k_i\)).
The RSK and dual RSK algorithms agree for permutation matrices.
For more information, see Chapter 7, Section 14 in [StaEC2] (where dual RSK is called \(\mathrm{RSK}^{\ast}\)) or the third solution to Exercise 2.7.12(a) in [GR2018v5sol].
EXAMPLES:
sage: RSK([3,3,2,4,1], insertion=RSK.rules.dualRSK) [[[1, 4], [2], [3], [3]], [[1, 4], [2], [3], [5]]] sage: RSK(Word([3,3,2,4,1]), insertion=RSK.rules.dualRSK) [[[1, 4], [2], [3], [3]], [[1, 4], [2], [3], [5]]] sage: RSK(Word([2,3,3,2,1,3,2,3]), insertion=RSK.rules.dualRSK) [[[1, 2, 3], [2, 3], [2, 3], [3]], [[1, 2, 8], [3, 6], [4, 7], [5]]]
Using dual RSK insertion with a strict biword:
sage: RSK([1,1,2,4,4,5],[2,4,1,1,3,2], insertion=RSK.rules.dualRSK) [[[1, 2], [1, 3], [2, 4]], [[1, 1], [2, 4], [4, 5]]] sage: RSK([1,1,2,3,3,4,5],[1,3,2,1,3,3,2], insertion=RSK.rules.dualRSK) [[[1, 2, 3], [1, 2], [3], [3]], [[1, 1, 3], [2, 4], [3], [5]]] sage: RSK([1, 2, 2, 2], [2, 1, 2, 4], insertion=RSK.rules.dualRSK) [[[1, 2, 4], [2]], [[1, 2, 2], [2]]] sage: RSK(Word([1,1,3,4,4]), [1,4,2,1,3], insertion=RSK.rules.dualRSK) [[[1, 2, 3], [1], [4]], [[1, 1, 4], [3], [4]]] sage: RSK([1,3,3,4,4], Word([6,1,2,1,7]), insertion=RSK.rules.dualRSK) [[[1, 2, 7], [1], [6]], [[1, 3, 4], [3], [4]]]
Using dual RSK insertion with a \(\{0, 1\}\)matrix:
sage: RSK(matrix([[0,1],[1,1]]), insertion=RSK.rules.dualRSK) [[[1, 2], [2]], [[1, 2], [2]]]
We can also give it something looking like a matrix:
sage: RSK([[0,1],[1,1]], insertion=RSK.rules.dualRSK) [[[1, 2], [2]], [[1, 2], [2]]]
Let us now call the inverse correspondence:
sage: RSK_inverse(*RSK([1, 2, 2, 2], [2, 1, 2, 3], ....: insertion=RSK.rules.dualRSK),insertion=RSK.rules.dualRSK) [[1, 2, 2, 2], [2, 1, 2, 3]] sage: P,Q = RSK([1, 2, 2, 2], [2, 1, 2, 3],insertion=RSK.rules.dualRSK) sage: RSK_inverse(P, Q, insertion=RSK.rules.dualRSK) [[1, 2, 2, 2], [2, 1, 2, 3]]
When applied to two standard tableaux, reverse dual RSK insertion behaves identically to the usual reverse RSK insertion:
sage: t1 = Tableau([[1, 2, 5], [3], [4]]) sage: t2 = Tableau([[1, 2, 3], [4], [5]]) sage: RSK_inverse(t1, t2, insertion=RSK.rules.dualRSK) [[1, 2, 3, 4, 5], [1, 4, 5, 3, 2]] sage: RSK_inverse(t1, t2, 'word', insertion=RSK.rules.dualRSK) word: 14532 sage: RSK_inverse(t1, t2, 'matrix', insertion=RSK.rules.dualRSK) [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', insertion=RSK.rules.dualRSK) [1, 4, 5, 3, 2] sage: RSK_inverse(t1, t1, 'permutation', insertion=RSK.rules.dualRSK) [1, 4, 3, 2, 5] sage: RSK_inverse(t2, t2, 'permutation', insertion=RSK.rules.dualRSK) [1, 2, 5, 4, 3] sage: RSK_inverse(t2, t1, 'permutation', insertion=RSK.rules.dualRSK) [1, 5, 4, 2, 3]
Let us check that forward and backward dual RSK are mutually inverse when the first tableau is merely transpose semistandard:
sage: p = Tableau([[1,2,2],[1]]); q = Tableau([[1,2,4],[3]]) sage: ret = RSK_inverse(p, q, insertion=RSK.rules.dualRSK); ret [[1, 2, 3, 4], [1, 2, 1, 2]] sage: RSK_inverse(p, q, 'word', insertion=RSK.rules.dualRSK) word: 1212
In general for dual RSK:
sage: p = Tableau([[1,1,2],[1]]); q = Tableau([[1,3,3],[2]]) sage: RSK_inverse(p, q, insertion=RSK.rules.dualRSK) [[1, 2, 3, 3], [1, 1, 1, 2]] sage: RSK_inverse(p, q, 'matrix', insertion=RSK.rules.dualRSK) [1 0] [1 0] [1 1]

insertion
(j, r)¶ Insert the letter
j
from the second row of the biword into the row \(r\) using dual RSK insertion, if there is bumping to be done.The row \(r\) is modified in place. The bumpedout entry, if it exists, is returned.
Warning
This method only changes \(r\) if bumping occurs. Appending \(j\) to the end of the row should be done by the caller.
EXAMPLES:
sage: from sage.combinat.rsk import RuleDualRSK sage: r = [1, 3, 4, 5] sage: j = RuleDualRSK().insertion(4, r); j 4 sage: r [1, 3, 4, 5] sage: r = [1, 2, 3, 6, 7] sage: j = RuleDualRSK().insertion(4, r); j 6 sage: r [1, 2, 3, 4, 7] sage: r = [1, 3] sage: j = RuleDualRSK().insertion(4, r); j is None True sage: r [1, 3]

reverse_insertion
(x, row)¶ Reverse bump the row
row
of the current insertion tableau with the numberx
using dual RSK insertion.The row
row
is modified in place. The bumpedout entry is returned.EXAMPLES:
sage: from sage.combinat.rsk import RuleDualRSK sage: r = [1, 2, 4, 6, 7] sage: x = RuleDualRSK().reverse_insertion(6, r); r [1, 2, 4, 6, 7] sage: x 6 sage: r = [1, 2, 4, 5, 7] sage: x = RuleDualRSK().reverse_insertion(6, r); r [1, 2, 4, 6, 7] sage: x 5

to_pairs
(obj1=None, obj2=None, check=True)¶ Given a valid input for the dual RSK algorithm, such as two \(n\)tuples
obj1
\(= [a_1, a_2, \ldots, a_n]\) andobj2
\(= [b_1, b_2, \ldots, b_n]\) forming a strict biword (i.e., satisfying \(a_1 \leq a_2 \leq \cdots \leq a_n\), and if \(a_i = a_{i+1}\), then \(b_i < b_{i+1}\)) or a \(\{0, 1\}\)matrix (“rook placement”), or a single word, return the array \([(a_1, b_1), (a_2, b_2), \ldots, (a_n, b_n)]\).INPUT:
obj1, obj2
– anything representing a strict biword (see the doc offorward_rule()
for the encodings accepted).check
– (default:True
) whether to check thatobj1
andobj2
actually define a valid strict biword.
EXAMPLES:
sage: from sage.combinat.rsk import RuleDualRSK sage: list(RuleDualRSK().to_pairs([1, 2, 2, 2], [2, 1, 2, 3])) [(1, 2), (2, 1), (2, 2), (2, 3)] sage: RuleDualRSK().to_pairs([1, 2, 2, 2], [1, 2, 3, 3]) Traceback (most recent call last): ... ValueError: invalid strict biword sage: m = Matrix(ZZ, 3, 2, [0,1,1,1,0,1]) ; m [0 1] [1 1] [0 1] sage: list(RuleDualRSK().to_pairs(m)) [(1, 2), (2, 1), (2, 2), (3, 2)] sage: m = Matrix(ZZ, 3, 2, [0,1,1,0,0,2]) ; m [0 1] [1 0] [0 2] sage: RuleDualRSK().to_pairs(m) Traceback (most recent call last): ... ValueError: dual RSK requires a {0, 1}matrix

class
sage.combinat.rsk.
RuleEG
¶ Bases:
sage.combinat.rsk.Rule
A rule modeling EdelmanGreene insertion.
For a reduced word of a permutation (i.e., an element of a type \(A\) Coxeter group), one can use EdelmanGreene insertion, an algorithm defined in [EG1987] Definition 6.20 (where it is referred to as CoxeterKnuth insertion). The EdelmanGreene insertion is similar to the standard row insertion except that (using the notations in the documentation of
RSK()
) if \(k_i\) and \(k_i + 1\) both exist in row \(i\), we only set \(k_{i+1} = k_i + 1\) and continue.EXAMPLES:
Let us reproduce figure 6.4 in [EG1987]:
sage: RSK([2,3,2,1,2,3], insertion=RSK.rules.EG) [[[1, 2, 3], [2, 3], [3]], [[1, 2, 6], [3, 5], [4]]]
Some more examples:
sage: a = [2, 1, 2, 3, 2] sage: pq = RSK(a, insertion=RSK.rules.EG); pq [[[1, 2, 3], [2, 3]], [[1, 3, 4], [2, 5]]] sage: RSK(RSK_inverse(*pq, insertion=RSK.rules.EG, output='matrix'), ....: insertion=RSK.rules.EG) [[[1, 2, 3], [2, 3]], [[1, 3, 4], [2, 5]]] sage: RSK_inverse(*pq, insertion=RSK.rules.EG) [[1, 2, 3, 4, 5], [2, 1, 2, 3, 2]]
The RSK algorithm (
RSK()
) built using the EdelmanGreene insertion ruleRuleEG
is a bijection from reduced words of permutations/elements of a type \(A\) Coxeter group to pairs consisting of an increasing tableau and a standard tableau of the same shape (see [EG1987] Theorem 6.25). The inverse of this bijection is obtained usingRSK_inverse()
. If the optional parameteroutput = 'permutation'
is set inRSK_inverse()
, then the function returns not the reduced word itself but the permutation (of smallest possible size) whose reduced word it is (although the order of the letters is reverse to the usual Sage convention):sage: w = RSK_inverse(*pq, insertion=RSK.rules.EG, output='permutation'); w [4, 3, 1, 2] sage: list(reversed(a)) in w.reduced_words() True

insertion
(j, r)¶ Insert the letter
j
from the second row of the biword into the row \(r\) using EdelmanGreene insertion, if there is bumping to be done.The row \(r\) is modified in place. The bumpedout entry, if it exists, is returned.
Warning
This method only changes \(r\) if bumping occurs. Appending \(j\) to the end of the row should be done by the caller.
EXAMPLES:
sage: from sage.combinat.rsk import RuleEG sage: qr, r = [1,2,3,4,5], [3,3,2,4,8] sage: j = RuleEG().insertion(9, r) sage: j is None True sage: qr, r = [1,2,3,4,5], [2,3,4,5,8] sage: j = RuleEG().insertion(3, r); r [2, 3, 4, 5, 8] sage: j 4 sage: qr, r = [1,2,3,4,5], [2,3,5,5,8] sage: j = RuleEG().insertion(3, r); r [2, 3, 3, 5, 8] sage: j 5

reverse_insertion
(x, row)¶ Reverse bump the row
row
of the current insertion tableau with the numberx
.The row
row
is modified in place. The bumpedout entry is returned.EXAMPLES:
sage: from sage.combinat.rsk import RuleEG sage: r = [1,1,1,2,3,3] sage: x = RuleEG().reverse_insertion(3, r); r [1, 1, 1, 2, 3, 3] sage: x 2


class
sage.combinat.rsk.
RuleHecke
¶ Bases:
sage.combinat.rsk.Rule
A rule modeling the Hecke insertion algorithm.
The Hecke RSK algorithm is similar to the classical RSK algorithm, but is defined using the Hecke insertion introduced in in [BKSTY06] (but using rows instead of columns). It is not clear in what generality it works; thus, following [BKSTY06], we shall assume that our biword \(p\) has top row \((1, 2, \ldots, n)\) (or, at least, has its top row strictly increasing).
The Hecke RSK algorithm returns a pair of an increasing tableau and a setvalued standard tableau. If \(p = ((j_0, k_0), (j_1, k_1), \ldots, (j_{\ell1}, k_{\ell1}))\), then the algorithm recursively constructs pairs \((P_0, Q_0), (P_1, Q_1), \ldots, (P_\ell, Q_\ell)\) of tableaux. The construction of \(P_{t+1}\) and \(Q_{t+1}\) from \(P_t\), \(Q_t\), \(j_t\) and \(k_t\) proceeds as follows: Set \(i = j_t\), \(x = k_t\), \(P = P_t\) and \(Q = Q_t\). We are going to insert \(x\) into the increasing tableau \(P\) and update the setvalued “recording tableau” \(Q\) accordingly. As in the classical RSK algorithm, we first insert \(x\) into row \(1\) of \(P\), then into row \(2\) of the resulting tableau, and so on, until the construction terminates. The details are different: Suppose we are inserting \(x\) into row \(R\) of \(P\). If (Case 1) there exists an entry \(y\) in row \(R\) such that \(x < y\), then let \(y\) be the minimal such entry. We replace this entry \(y\) with \(x\) if the result is still an increasing tableau; in either subcase, we then continue recursively, inserting \(y\) into the next row of \(P\). If, on the other hand, (Case 2) no such \(y\) exists, then we append \(x\) to the end of \(R\) if the result is an increasing tableau (Subcase 2.1), and otherwise (Subcase 2.2) do nothing. Furthermore, in Subcase 2.1, we add the box that we have just filled with \(x\) in \(P\) to the shape of \(Q\), and fill it with the oneelement set \(\{i\}\). In Subcase 2.2, we find the bottommost box of the column containing the rightmost box of row \(R\), and add \(i\) to the entry of \(Q\) in this box (this entry is a set, since \(Q\) is setvalued). In either subcase, we terminate the recursion, and set \(P_{t+1} = P\) and \(Q_{t+1} = Q\).
Notice that setvalued tableaux are encoded as tableaux whose entries are tuples of positive integers; each such tuple is strictly increasing and encodes a set (namely, the set of its entries).
EXAMPLES:
As an example of Hecke insertion, we reproduce Example 2.1 in arXiv 0801.1319v2:
sage: w = [5, 4, 1, 3, 4, 2, 5, 1, 2, 1, 4, 2, 4] sage: P,Q = RSK(w, insertion=RSK.rules.Hecke); [P,Q] [[[1, 2, 4, 5], [2, 4, 5], [3, 5], [4], [5]], [[(1,), (4,), (5,), (7,)], [(2,), (9,), (11, 13)], [(3,), (12,)], [(6,)], [(8, 10)]]] sage: wp = RSK_inverse(P, Q, insertion=RSK.rules.Hecke, ....: output='list'); wp [5, 4, 1, 3, 4, 2, 5, 1, 2, 1, 4, 2, 4] sage: wp == w True

backward_rule
(p, q, output)¶ Return the generalized permutation obtained by applying reverse Hecke insertion to a pair of tableaux
(p, q)
.INPUT:
p
,q
– two tableaux of the same shape.output
– (default:'array'
) ifq
is semistandard:
'array'
– as a twoline array (i.e. generalized permutation or biword)
and if
q
is standard setvalued, we can have the output:'word'
– as a word'list'
– as a list
EXAMPLES:
sage: from sage.combinat.rsk import RuleHecke sage: t1 = Tableau([[1, 4], [2], [3]]) sage: t2 = Tableau([[(1, 2), (4,)], [(3,)], [(5,)]]) sage: RuleHecke().backward_rule(t1, t2, 'array') [[1, 2, 3, 4, 5], [3, 3, 2, 4, 1]] sage: t1 = Tableau([[1, 4], [2, 3]]) sage: t2 = Tableau([[(1, 2), (4,)], [(3,)], [(5,)]]) sage: RuleHecke().backward_rule(t1, t2, 'array') Traceback (most recent call last): ... ValueError: p(=[[1, 4], [2, 3]]) and q(=[[(1, 2), (4,)], [(3,)], [(5,)]]) must have the same shape

forward_rule
(obj1, obj2, check_standard=False)¶ Return a pair of tableaux obtained by applying Hecke insertion to the generalized permutation
[obj1, obj2]
.INPUT:
obj1, obj2
– can be one of the following ways to represent a generalized permutation (or, equivalently, biword): two lists
obj1
andobj2
of equal length, to be interpreted as the top row and the bottom row of the biword;  a word
obj1
in an ordered alphabet, to be interpreted as the bottom row of the biword (in this case,obj2
isNone
; the top row of the biword is understood to be \((1, 2, \ldots, n)\) by default);
 two lists
check_standard
– (default:False
) check if either of the resulting tableaux is a standard tableau, and if so, typecast it as such
EXAMPLES:
sage: from sage.combinat.rsk import RuleHecke sage: p, q = RuleHecke().forward_rule([3,3,2,4,1], None);p [[1, 4], [2], [3]] sage: q [[(1, 2), (4,)], [(3,)], [(5,)]] sage: isinstance(p, SemistandardTableau) True sage: isinstance(q, Tableau) True

insertion
(j, ir, r, p)¶ Insert the letter
j
from the second row of the biword into the row \(r\) of the increasing tableau \(p\) using Hecke insertion, provided that \(r\) is the \(ir\)th row of \(p\), and provided that there is bumping to be done.The row \(r\) is modified in place. The bumpedout entry, if it exists, is returned.
Warning
This method only changes \(r\) if bumping occurs. Appending \(j\) to the end of the row should be done by the caller.
EXAMPLES:
sage: from sage.combinat.rsk import RuleHecke sage: from bisect import bisect_right sage: p, q, r = [], [], [3,3,8,8,8,9] sage: j, ir = 8, 1 sage: j1 = RuleHecke().insertion(j, ir, r, p) sage: j1 == r[bisect_right(r, j)] True

reverse_insertion
(i, x, row, p)¶ Reverse bump the row
row
of the current insertion tableaup
with the numberx
, provided thatrow
is the \(i\)th row of \(p\).The row
row
is modified in place. The bumpedout entry is returned.EXAMPLES:
sage: from sage.combinat.rsk import RuleHecke sage: from bisect import bisect_left sage: r = [2,3,3,4,8,9] sage: x, i, p = 9, 1, [1, 2] sage: x1 = RuleHecke().reverse_insertion(i, x, r, p) sage: x1 == r[bisect_left(r,x)  1] True


class
sage.combinat.rsk.
RuleRSK
¶ Bases:
sage.combinat.rsk.Rule
A rule modeling the classical RobinsonSchenstedKnuth insertion.
See
RSK()
for the definition of this operation.EXAMPLES:
sage: RSK([1, 2, 2, 2], [2, 1, 1, 2], insertion=RSK.rules.RSK) [[[1, 1, 2], [2]], [[1, 2, 2], [2]]] sage: p = Tableau([[1,2,2],[2]]); q = Tableau([[1,3,3],[2]]) sage: RSK_inverse(p, q, insertion=RSK.rules.RSK) [[1, 2, 3, 3], [2, 1, 2, 2]]
It is worth noting that in case of
RSK_inverse
withoutput = 'permutation'
RuleRSK
returns an object of classPermutation
.
insertion
(j, r)¶ Insert the letter
j
from the second row of the biword into the row \(r\) using classical Schensted insertion, if there is bumping to be done.The row \(r\) is modified in place. The bumpedout entry, if it exists, is returned.
Warning
This method only changes \(r\) if bumping occurs. Appending \(j\) to the end of the row should be done by the caller.
EXAMPLES:
sage: from sage.combinat.rsk import RuleRSK sage: qr, r = [1,2,3,4,5], [3,3,2,4,8] sage: j = RuleRSK().insertion(9, r) sage: j is None True sage: qr, r = [1,2,3,4,5], [3,3,2,4,8] sage: j = RuleRSK().insertion(3, r) sage: j 4

reverse_insertion
(x, row)¶ Reverse bump the row
row
of the current insertion tableau with the numberx
.The row
row
is modified in place. The bumpedout entry is returned.EXAMPLES:
sage: from sage.combinat.rsk import RuleRSK sage: r = [2,3,3,4,8] sage: x = RuleRSK().reverse_insertion(4, r); r [2, 3, 4, 4, 8] sage: x 3


sage.combinat.rsk.
robinson_schensted_knuth
(obj1=None, obj2=None, insertion=<class 'sage.combinat.rsk.RuleRSK'>, check_standard=False, **options)¶ Perform the RobinsonSchenstedKnuth (RSK) correspondence.
The RobinsonSchenstedKnuth (RSK) correspondence (also known as the RSK algorithm) is most naturally stated as a bijection between generalized permutations (also known as twoline arrays, biwords, …) and pairs of semistandard 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 semistandard 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\) (we start counting the rows at \(0\)) 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.
A generalized permutation (or biword) is a list \(((j_0, k_0), (j_1, k_1), \ldots, (j_{\ell1}, k_{\ell1}))\) of pairs such that the letters \(j_0, j_1, \ldots, j_{\ell1}\) are weakly increasing (that is, \(j_0 \leq j_1 \leq \cdots \leq j_{\ell1}\)), whereas the letters \(k_i\) satisfy \(k_i \leq k_{i+1}\) whenever \(j_i = j_{i+1}\). The \(\ell\)tuple \((j_0, j_1, \ldots, j_{\ell1})\) is called the top line of this generalized permutation, whereas the \(\ell\)tuple \((k_0, k_1, \ldots, k_{\ell1})\) is called its bottom line.
Now the RSK algorithm, applied to a generalized permutation \(p = ((j_0, k_0), (j_1, k_1), \ldots, (j_{\ell1}, k_{\ell1}))\) (encoded as a lexicographically sorted list of pairs) starts by initializing two semistandard 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 a new box with entry \(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 RobinsonSchenstedKnuth correspondence.
This correspondence has been introduced in [Knu1970], where it has been referred to as “Construction A”.
For more information, see Chapter 7 in [StaEC2].
We also note that integer matrices are in bijection with generalized permutations. Furthermore, we can convert any word \(w\) (and, in particular, any permutation) to a generalized permutation by considering the top row 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 RobinsonSchenstedKnuth insertion.INPUT:
obj1, obj2
– can be one of the following: a word in an ordered alphabet (in this case,
obj1
is said word, andobj2
isNone
)  an integer matrix
 two lists of equal length representing a generalized permutation (namely, the lists \((j_0, j_1, \ldots, j_{\ell1})\) and \((k_0, k_1, \ldots, k_{\ell1})\) represent the generalized permutation \(((j_0, k_0), (j_1, k_1), \ldots, (j_{\ell1}, k_{\ell1}))\))
 any object which has a method
_rsk_iter()
which returns an iterator over the object represented as generalized permutation or a pair of lists (in this case,obj1
is said object, andobj2
isNone
).
 a word in an ordered alphabet (in this case,
insertion
– (default:RSK.rules.RSK
) the following types of insertion are currently supported:RSK.rules.RSK
(or'RSK'
) – RobinsonSchenstedKnuth insertion (RuleRSK
)RSK.rules.EG
(or'EG'
) – EdelmanGreene insertion (only for reduced words of permutations/elements of a type \(A\) Coxeter group) (RuleEG
)RSK.rules.Hecke
(or'hecke'
) – Hecke insertion (only guaranteed for generalized permutations whose top row is strictly increasing) (RuleHecke
)RSK.rules.dualRSK
(or'dualRSK'
) – Dual RSK insertion (only for strict biwords) (RuleDualRSK
)RSK.rules.coRSK
(or'coRSK'
) – CoRSK insertion (only for strict cobiwords) (RuleCoRSK
)
check_standard
– (default:False
) check if either of the resulting tableaux is a standard tableau, and if so, typecast it as such
For precise information about constraints on the input and output, as well as the definition of the algorithm (if it is not standard RSK), see the particular
Rule
class.EXAMPLES:
If we only input one row, it is understood that the top row should be \((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]]]
We can provide 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]]]
We can provide a matrix:
sage: RSK(matrix([[0,1],[2,1]])) [[[1, 1, 2], [2]], [[1, 2, 2], [2]]]
We can also provide something looking like a matrix:
sage: RSK([[0,1],[2,1]]) [[[1, 1, 2], [2]], [[1, 2, 2], [2]]]
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 as inputs, so to compose withRSK()
, 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]]

sage.combinat.rsk.
robinson_schensted_knuth_inverse
(p, q, output='array', insertion=<class 'sage.combinat.rsk.RuleRSK'>)¶ Return the generalized permutation corresponding to the pair of tableaux \((p, q)\) under the inverse of the RobinsonSchenstedKnuth correspondence.
For more information on the bijection, see
RSK()
.INPUT:
p
,q
– two semistandard tableaux of the same shape, or (in the case when Hecke insertion is used) an increasing tableau and a setvalued tableau of the same shape (see the note below for the format of the setvalued tableau)output
– (default:'array'
) ifq
is semistandard:'array'
– as a twoline array (i.e. generalized permutation or biword)'matrix'
– as an integer matrix
and if
q
is standard, we can also 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.rules.RSK
) the insertion algorithm used in the bijection. Currently the following are supported:RSK.rules.RSK
(or'RSK'
) – RobinsonSchenstedKnuth insertion (RuleRSK
)RSK.rules.EG
(or'EG'
) – EdelmanGreene insertion (only for reduced words of permutations/elements of a type \(A\) Coxeter group) (RuleEG
)RSK.rules.Hecke
(or'hecke'
) – Hecke insertion (only guaranteed for generalized permutations whose top row is strictly increasing) (RuleHecke
)RSK.rules.dualRSK
(or'dualRSK'
) – Dual RSK insertion (only for strict biwords) (RuleDualRSK
)RSK.rules.coRSK
(or'coRSK'
) – CoRSK insertion (only for strict cobiwords) (RuleCoRSK
)
For precise information about constraints on the input and output, see the particular
Rule
class.Note
In the case of Hecke insertion, the input variable
q
should be a setvalued tableau, encoded as a tableau whose entries are strictly increasing tuples of positive integers. Each such tuple encodes the set of its entries.EXAMPLES:
If both
p
andq
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 Hecke insertion:
sage: w = [5, 4, 3, 1, 4, 2, 5, 5] sage: pq = RSK(w, insertion=RSK.rules.Hecke) sage: RSK_inverse(*pq, insertion=RSK.rules.Hecke, output='list') [5, 4, 3, 1, 4, 2, 5, 5]
Note
The constructor of
Tableau
accepts not only semistandard tableaux, but also arbitrary lists that are fillings of a partition diagram. (And such lists are used, e.g., for the setvalued tableauq
that is passed toRSK_inverse(p, q, insertion='hecke')
.) The user is responsible for ensuring that the tableaux passed toRSK_inverse
are of the right types (semistandard, standard, increasing, setvalued as needed).

sage.combinat.rsk.
to_matrix
(t, b)¶ Return the integer matrix corresponding to a twoline array.
INPUT:
t
– the top row of the arrayb
– the bottom row 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]