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.
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:
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
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
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
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:
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:
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
A is a permutation matrix if and only if P and Q are both standard Young tableaux.
Find the matrix corresponding to the following tableaux:
Let be the number of SYT of shape Prove that we have