Our next task is as follows:
- Given partition
and vector
, count the number of semistandard Young tableaux with shape
and type
(i.e.
occurs
times).
Proposition. The number of SSYT with shape
and type
remains invariant when we permute the
‘s around.
Proof
Since each permutation is a product of transpositions of the form it suffices to prove invariance under
This is via the Bender-Knuth involution.
Given an SSYT with entries labelled
and
entries labelled
, we first pair up vertical elements labelled
and
and leave them untouched. For the other elements, we consider each row which has
copies of
followed by
copies of
Now replace them by
copies of
followed by
copies of
The rows remain weakly increasing, but are the columns still strictly increasing? The only problem which may occur is when an is replaced by
(or vice versa) and this is equal to the entry below (or above). But we have already excluded all such cases by pairing
and
earlier. ♦
Hence we might as well sort the entries of and assume it is a partition.
Definition. Given partitions
, the Kostka number
is the number of SSYT of the shape
and type
Clearly if
.
More on Kostka Numbers
As an example, take and
. Since
, this is in fact an SYT and there are two possibilities.
On the other hand, if and
, no such tableau exists. Hence
Lemma 1. If
, then
, i.e. for each
we have:
Also
.
Proof
Consider a positive integer ; since each column is strictly increasing, each of
must occur in the first
rows, so the number of boxes
is at least the number of these integers, i.e.
This proves the inequality. If equality holds for all
, this constraint forces us to have all
‘s on the
-th row. ♦
The rest of the article is dedicated to proving:
Main Theorem. For any partitions
, we have:
Written in matrix form, this gives
RSK Correspondence
The Robinson–Schensted–Knuth (RSK) correspondence works as follows; suppose we have a matrix of non-negative integers, with column sum
and row sum
We do not assume that
and
are partitions. Now take
satisfying the following:
;
- if
, then
(together with the first condition, this means the sequence of
is in lexicographical order);
is exactly the number of
for which
For example,
Now we construct a pair of SSYT as follows:
- Start with empty SSYT
.
- For each
, let
and
be the SSYT with the same shape as
but with
added to the extra box.
The above example for A gives us the following ; the coloured cells on the left refer to the bumped cells, while those on the right are the additional cells attached to maintain the same shape.
Lemma 2. The resulting
is an SSYT for each
Proof
Indeed if , then
is larger than any other number in
, so we still get an SSYT after placing it in the extra box. On the other hand if
then
so by lemma 3 here, the additional cell for
lies strictly to the right of the bumped cells of
Since these include all occurrences of
in
, it is safe to write
in the new cell for
♦
Taking the final pair , we have obtained (P, Q) of the same shape such that the type of P is
and that of Q is
Theorem. The correspondence
gives a bijection:
Proof
It remains to show how we can construct an A given (P, Q). Find the largest entry k of Q; if there are several of them, pick the rightmost one. Note that such a square must be a corner square (i.e. no square to its right or below). Now remove it from Q to obtain and perform reverse row-insertion from the corresponding square of P to obtain
This gives us
and a pair
By construction we have Now suppose
along the way. The box removed for
in Q is strictly to the right of
Hence in P, the bumped entries for
are strictly to the right of
(by lemma 3 here and the exercise after it). In particular
♦
Taking the cardinality of both sets, we obtain the desired equality:
Example
Suppose d=3. Labeling the columns and rows by partitions 3, 2+1 and 1+1+1, we get the following matrices. One easily checks that
Note
A is a permutation matrix if and only if P and Q are both standard Young tableaux.
Exercise
Find the matrix corresponding to the following tableaux:
Exercise
Let be the number of SYT of shape
Prove that we have