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.

Theorem 2

where recall if is a class function on , , where the partition structure of .

Corollary 3If , then . Since are all nonnegative, is Schur positive.

*Proof:* (of theorem) . If , and is a character of , then

where

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 haveSo we have

Let’s not divide, instead multiply by and sum from 0 to . Then we get

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 , thenOn 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 4has 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 5and 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 .