Robinson-Schensted algorithm
Encyclopedia
In mathematics
, the Robinson–Schensted correspondence is a bijective
correspondence between permutation
s and pairs of standard Young tableaux of the same shape. It has various descriptions, all of which are of algorithmic nature, it has many remarkable properties, and it has applications in combinatorics
and other areas such as representation theory
. The correspondence has been generalized in numerous ways, notably by Knuth to what is known as the Robinson–Schensted–Knuth correspondence
, and a further generalization to picture
s by Zelevinsky.
The simplest description of the correspondence is using the Schensted algorithm , a procedure that constructs one tableau by successively inserting the values of the permutation according to a specific rule, while the other tableau records the evolution of the shape during construction. The correspondence had been described, in a rather different form, much earlier by Robinson , in an attempt to prove the Littlewood–Richardson rule
. The correspondence is often referred to as the Robinson–Schensted algorithm, although the procedure used by Robinson is radically different from the Schensted–algorithm, and almost entirely forgotten.
Other methods of defining the correspondence include a nondeterministic algorithm
in terms of jeu de taquin
.
The bijective nature of the correspondence relates it to the enumerative
identity:
where
denotes the set of partition
s of
(or of Young diagrams with n squares), and denotes the number of standard Young tableaux of shape .
where
, and proceeds by constructing sequentially a sequence of (intermediate) ordered pairs of Young tableaux of the same shape:
where
are empty tableaux. The output tableaux are 
and 
. Once 
is constructed, one forms 
by inserting 
into 
, and then 
by adding an entry i to 
in the square added to the shape by the insertion (so that 
and 
have equal shapes for all i). Because of the more passive role of the tableaux 
, the final one 
, which is part of the output and from which the previous 
are easily read off, is called the recording tableau; by contrast the tableaux 
are called insertion tableaux.
is called Schensted insertion or row-insertion (to distinguish it from a variant procedure called column-insertion). Its simplest form is defined in terms of "incomplete standard tableaux": like standard tableaux they have distinct entries, forming increasing rows and columns, but some values (still to be inserted) may be absent as entries. The procedure takes as arguments such a tableau 
and a value 
not present as entry of 
; it produces as output a new tableau denoted and a square 
by which its shape has grown. The value 
appears in the first row of , either having been added at the end (if no entries larger than 
were present), or otherwise replacing the first entry 
in the first row of 
. In the former case 
is the square where 
is added, and the insertion is completed; in the latter case the replaced entry 
is similarly inserted into the second row of 
, and so on, until at some step the first case applies (which certainly happens if an empty row of 
is reached).
More formally, the following pseudocode
describes the row-insertion of a new value
into 
.
The shape of
grows by exactly one square, namely 
.
, is not obvious from this procedure (entries in the same column are never even compared). It can however be seen as follows. At all times except immediately after step 4, the square 
is either empty in 
or holds a value greater than 
; step 5 re-establishes this property because 
now is the square immediately below the one that originally contained 
in 
. Thus the effect of the replacement in step 4 on the value 
is to make it smaller; in particular it cannot become greater than its right or lower neighbours. On the other hand the new value is not less than its left neighbour (if present) either, as is ensured by the comparison that just made step 2 terminate. Finally to see that the new value is larger than its upper neighbour 
if present, observe that 
holds after step 5, and that decreasing 
in step 2 only decreases the corresponding value 
.
The algorithm produces a pair of standard Young tableaux.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the Robinson–Schensted correspondence is a bijective
Bijection
A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
correspondence between permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
s and pairs of standard Young tableaux of the same shape. It has various descriptions, all of which are of algorithmic nature, it has many remarkable properties, and it has applications in combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
and other areas such as representation theory
Representation theory
Representation theory is a branch of mathematics that studies abstract algebraic structures by representing their elements as linear transformations of vector spaces, and studiesmodules over these abstract algebraic structures...
. The correspondence has been generalized in numerous ways, notably by Knuth to what is known as the Robinson–Schensted–Knuth correspondence
Robinson–Schensted–Knuth correspondence
In mathematics, the Robinson–Schensted–Knuth correspondence, also referred to as the RSK correspondence or RSK algorithm, is a combinatorial bijection between matrices with non-negative integer entries and pairs of semistandard Young tableaux of equal shape, whose size equals the sum of the...
, and a further generalization to picture
Picture (mathematics)
In combinatorial mathematics, a picture is a bijection between skew diagrams satisfying certain properties, introduced by in a generalization of the Robinson–Schensted correspondence and the Littlewood–Richardson rule....
s by Zelevinsky.
The simplest description of the correspondence is using the Schensted algorithm , a procedure that constructs one tableau by successively inserting the values of the permutation according to a specific rule, while the other tableau records the evolution of the shape during construction. The correspondence had been described, in a rather different form, much earlier by Robinson , in an attempt to prove the Littlewood–Richardson rule
Littlewood–Richardson rule
In mathematics, the Littlewood–Richardson rule is a combinatorial description of the coefficients that arise when decomposing a product of two Schur functions as a linear combination of other Schur functions. These coefficients are natural numbers, which the Littlewood–Richardson rule describes as...
. The correspondence is often referred to as the Robinson–Schensted algorithm, although the procedure used by Robinson is radically different from the Schensted–algorithm, and almost entirely forgotten.
Other methods of defining the correspondence include a nondeterministic algorithm
Nondeterministic algorithm
In computer science, a nondeterministic algorithm is an algorithm that can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run. A concurrent algorithm can perform differently on different...
in terms of jeu de taquin
Jeu de taquin
In the mathematical field of combinatorics, jeu de taquin is a construction due to which defines an equivalence relation on the set of skew standard Young tableaux. A jeu de taquin slide is a transformation where the numbers in a tableau are moved around in a way similar to how the pieces in the...
.
The bijective nature of the correspondence relates it to the enumerative
Enumerative combinatorics
Enumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations...
identity:
where
denotes the set of partitionPartition (number theory)
In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered to be the same partition; if order matters then the sum becomes a...
s of
(or of Young diagrams with n squares), and denotes the number of standard Young tableaux of shape .The Schensted algorithm
The Schensted algorithm starts from the permutation σ written in two-line notationwhere
, and proceeds by constructing sequentially a sequence of (intermediate) ordered pairs of Young tableaux of the same shape:where
are empty tableaux. The output tableaux are and . Once is constructed, one forms by inserting into , and then by adding an entry i to in the square added to the shape by the insertion (so that and have equal shapes for all i). Because of the more passive role of the tableaux , the final one , which is part of the output and from which the previous are easily read off, is called the recording tableau; by contrast the tableaux are called insertion tableaux.Insertion
The basic procedure used to insert each is called Schensted insertion or row-insertion (to distinguish it from a variant procedure called column-insertion). Its simplest form is defined in terms of "incomplete standard tableaux": like standard tableaux they have distinct entries, forming increasing rows and columns, but some values (still to be inserted) may be absent as entries. The procedure takes as arguments such a tableau and a value not present as entry of ; it produces as output a new tableau denoted and a square by which its shape has grown. The value appears in the first row of , either having been added at the end (if no entries larger than were present), or otherwise replacing the first entry in the first row of . In the former case is the square where is added, and the insertion is completed; in the latter case the replaced entry is similarly inserted into the second row of , and so on, until at some step the first case applies (which certainly happens if an empty row of is reached).More formally, the following pseudocode
Pseudocode
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
describes the row-insertion of a new value
into .
- Set
and 
to one more than the length of the first row of 
. - While
and 
, decrease 
by 1. (Now 
is the first square in row 
with either an entry larger than 
in 
, or no entry at all.) - If the square
is empty in 
, terminate after adding 
to 
in square 
and setting 
. - Swap the values
and 
. (This inserts the old 
into row 
, and saves the value it replaces for insertion into the next row.) - Increase
by 1 and return to step 2.
The shape of
grows by exactly one square, namely .Correctness
The fact that has increasing rows and columns, if the same holds for, is not obvious from this procedure (entries in the same column are never even compared). It can however be seen as follows. At all times except immediately after step 4, the square is either empty in or holds a value greater than ; step 5 re-establishes this property because now is the square immediately below the one that originally contained in . Thus the effect of the replacement in step 4 on the value is to make it smaller; in particular it cannot become greater than its right or lower neighbours. On the other hand the new value is not less than its left neighbour (if present) either, as is ensured by the comparison that just made step 2 terminate. Finally to see that the new value is larger than its upper neighbour if present, observe that holds after step 5, and that decreasing in step 2 only decreases the corresponding value .Constructing the tableaux
The full Schensted algorithm applied to a permutation proceeds as follows.- Set both and to the empty tableau
- For
increasing from 1 to 
compute and the square by the insertion procedure; then replace by and add the entry to the tableau in the square . - Terminate, returning the pair
.
The algorithm produces a pair of standard Young tableaux.
Invertibility of the construction
It can be seen that given any pair of standard Young tableaux of the same shape, there is an inverse procedure that produces a permutation that will give rise to by the Schensted algorithm. It essentially consists of tracing steps of the algorithm backwards, each time using an entry of to find the square where the inverse insertion should start, moving the corresponding entry of to the preceding row, and continuing upwards through the rows until an entry of the first row is replaced, which is the value inserted at the corresponding step of the construction algorithm. These two inverse algorithms define a bijective correspondence between permutations of n on one side, and pairs of standard Young tableaux of equal shape and containing n squares on the other side.Properties
One of the most fundamental properties, but not evident from the algorithmic construction, is symmetry:- If the Robinson–Schensted correspondence associates tableaux to a permutation σ, then it associates to the inverse permutation σ−1.