The setting is as previous lecture. Many of the expositions are adapted from Stanley’s Volume 2 appendix by Sergey Fomin. , where and denotes the size of the inverse image by an abuse of notation. Last time we saw that
Theorem 1 (Polya) , where , and has i-cycles, and .
Note that both sides above are in . This leads to connections in character theory.
Let . Then acts on . This gives a permutation representation of with dimension . Let be a character.
where recall if is a class function on , , where the partition structure of .
Corollary 3 If , then . Since are all nonnegative, is Schur positive.
Proof: (of theorem) . If , and is a character of , then
If , then
where is the size of the centralizer of in . The proof uses . Going back to , we have the following claim
where has cycle type . Finally,
Interpretations of :
- consider . is a placement of balls into boxes. Patterns consist of configurations of unlabelled balls (Bose-Einstein statistics).
Check: set all . On the left we have the number of BE configurations of balls in boxes. On the middle and right hand side, we have
So we have
We can use this: set , for , and differentiate once at to get
Do this many times to get the joint moments of . (9) is the joint moment generating function of ‘s which are independent geometric with , , i.e., . Then the conditional distribution is Bose-Einstein! This is analogous to the picture of Poissonization of the measure on partitions induced from the uniform measure on .
If in (9), we multiply both sides by , then
On the , we have .
- Let now , then . This gives the joint moment generating function of the Poissonized multinomial distribution (whose components are iid) when multiplied by (Fisher’s Identity):
- Next try , the cyclic group acting on . Then
specializing to , we get Witts cyclotomic identity:
Back to Stanley: (1) Curtis Greene theorem on RSK rows and columns (2) Knuth equivalence. Recall RSK: , and define the shape of to be . What does mean? Or, we do and have the same shape? Let the maximum number of elements in the union of increasing subsequences of .
Theorem 4 has shape , where , and , where is the maximum number of elements in the union of decreasing subsequences.
Knuth equivalence: when do and have the same tableau?
Answer: a “Knuth move” needs three adjacent letters say , with with and adjacent, switch them: for example
More concretely, the following arrow charts are admissible Knuth move paths:
Theorem 5 and have the same tableau if and only if they are Knuth equivalent in the above sense. Furthermore they have the same tableau if and only if is Knuth equivalkent to .