In mathematics, the Robinson-Schensted-Knuth correspondence, also referred to as the RSK correspondence or RSK algorithm, is a combinatorial bijection between generalized permutations (as 2 lined arrays) and pairs of semi-standard Young Tableaux (SSYT). It is a generalization of the Robinson-Schensted algorithm.
The Robinson-Schensted algorithm, which establishes a bijective mapping between permutations and pairs of Young Tableaux, both having shape :
where is a permutation of order and are Young Tableau of shape .
A generalized permutation or two-line array is defined by:
- if and then
By extending the Robinson-Schensted algorithm to generalized permutations we can obtain one-to-one mappings from these types of permutations to ordered pairs, , where and are SSYT of the same shape.
The Robinson-Schensted-Knuth correspondence
The Robinson-Schensted-Knuth (RSK) algorithm works almost exactly like the Robinson-Schensted algorithm, the only difference being that RSK takes a generalized permutation as input. Stanley  uses this moniker. The basic operation consists of an insertion operation defined as of a positive integer into a SSYT .
Let be a matrix with non-negative elements of dimension . Let be a generalized permutation associated with , defined as:
where in addition to the 2 rules specified in the definition of a generalized permutaion needs to satisfy:
- For each , there must be values of for which .
It is easy to see that there is a bijective mapping from to .
If we apply the RSK algorithm on the permutation we get the following theorem called the Robinson-Schensted-Knuth correspondence theorem.
Theorem 1: There is a one-one correspondence between matrices (and by implication permutations ) and the ordered pairs , where and have the same shape. In addition, each integer occurs exactly times in and each integer occurs exactly times in .
Combinatorial properties of RSK correspondence
RSK and permutation matrices
If is a permutation matrix then RSK outputs standard Young Tableaux (SYT), of the same shape . Conversely, if are SYT having the same shape , then the corresponding matrix is a permutation matrix. As a result of this property by simply comparing the cardinalities of the two sets on the two sides of the bijective mapping we get the following corollary:
Corollary 1: For each we have where means varies over all partitions of and is the number of standard Young tableaux of shape .
By examining the structure of the Robinson-Schensted-K algorithm we can prove the following theorem:
Theorem 2: If the permutation corresponds to a triple , then the inverse permutation, , corresponds to .
This leads to the following surprising corollary that links the number of involutions on with the number of tableaux that can be formed from (An involution is a permutation that is its own inverse):
Corollary 2: The number of tableaux that can be formed from is equal to the number of involutions on .
Proof: If is an involution corresponding to , then corresponds to ; hence . Conversely, if is any permutation corresponding to , then also corresponds to ; hence . So there is a one-one correspondence between involutions and tableax
The number of involutions on is given by the recurrence:
Where . By solving this recurrence we can get the number of involutions on ,
Symmetry of RSK
Let be a matrix with non-negative entries. Suppose the RSK algorithm maps to then the RSK algorithm maps to , where is the transpose of .
- Let be an matrix with non-negative entries, then if and only if where is mapped to by the RSK algorithm.
- Let and let the RSK algorithm map the matrix to the pair , where is an SSYT of shape . Let where the and . Then the map establishes a bijection between symmetric matrices with row() and SSYT's of type .
Applications of the RSK correspondence
Knuth proved a number of important results that involve symmetric functions that can be derived from the RSK correspondence.
where are schur functions.
Fix partitions , then
where and denote the Kostka numbers and is the number of matrices , with non-negative elements, with row row() and column() .
- ^ a b c d Stanley, Richard P., Enumerative Combinatorics, Volume2. Cambridge University Press. ISBN 0-521-55309-1, 0-521-56069-1. Page 316-380
- ^ a b Knuth, Donald E., Permutations, matrices, and generalized Young tableaux. Pacific J. Math. Volume 34, Number 3 (1970), 709-727. Available at http://projecteuclid.org/DPubS?verb=Display&version=1.0&service=UI&handle=euclid.pjm/1102971948&page=record
- ^ a b Knuth, Donald E., The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley, 1973. Page 54-58