Two Important Results
In this article and the next, we will find a combinatorial way of computing the Littlewood-Richardson coefficient.
The key result we have so far is that given any word w there is a unique SSYT T (called the rectification of w) such that its word w(T) is Knuth-equivalent to w. This is related to the RSK construction as follows: recall that we obtain a 2-row array then define a pair of SSYT of the same shape via:
- and is obtained from by appending so that it has the same shape as
- let .
In particular and since we get:
Observation. is Knuth-equivalent to the word In other words, is the rectification of
Theorem 1. Suppose, in the RSK construction, the pair of SSYT of the same shape gives us the two-row matrix Now let be any SSYT and define the construction:
- let and ;
- for each of , let , and be obtained from by attaching the new square of to it, and filling in
The resulting is a skew SSYT whose rectification is
Suppose we have the matrix and the initial SSYT . This gives:
The rectification of is , which is consistent with our claim.
Let Add symbols which are strictly smaller than all (E.g. we can add a large constant to all existing labels). The RSK construction for
gives us a pair of SSYT. By the above observation, the first term of this pair is T; let the second term be U. Hence we get RSK correspondences:
The second correspondence is given in the conditions, while the third follows from
and the definition of By the symmetry theorem, swapping the two SSYT corresponds to swapping the two rows of the matrix and sorting the columns lexicographically so we get RSK correspondences:
Again by our observation above, the left matrix satisfies
some order of
By the lemma here, dropping the m smallest terms still gives us Knuth-equivalent words. On the LHS, this gives the skew SSYT On the RHS, this gives some order of From the first RSK correspondence, is the rectification of that same order of Hence and we are done. ♦
Theorem 2. Let be partitions. Suppose is an SSYT of shape and is an SSYT of shape . Then there is a bijection between:
- pairs of SSYT of shapes respectively, such that
- skew SSYT of shape such that its rectification is
Recall that is the rectification of the skew SSYT obtained by putting below and above.
is well-defined only when for all ; otherwise, the second set is empty; it will follow from the proof that the first set is empty too.
Let be of shapes respectively such that The RSK correspondence for gives us a two-row matrix:
Let be the SSYT obtained from by inserting and be the skew SSYT obtained by putting in the new empty boxes. By construction we have so has shape By theorem 1, the rectification of is
Conversely, suppose we are given skew of shape such that Let be the SSYT obtained from by attaching an SSYT of shape and entries smaller than those of
Then corresponds via RSK to a two-row matrix:
where are from and are from By RSK, the first columns correspond to a pair of SSYT of shape The remaining columns correspond to a pair since is the rectification of . Hence has shape Finally we have which gives as desired. ♦
Our main interest is in the following.
Corollary. For each SSYT of shape , the number of skew SSYT of shape such that is dependent only on , and independent of the choice of
Denote this number by . Recall that the skew Schur function
over all skew SSYT of shape
Let be the rectification of By the corollary, if has shape there are exactly possibilities for Hence,
over all partitions and SSYT of shape
So and our is precisely the Littlewood-Richardson coefficient, and we get a combinatorial interpretation:
Summary. For any SSYT of shape is the number of skew SSYT of shape whose rectification is