# Permutation character of the symmetric group on subsets of certain size

The symmetric group $S_n$ acts on $[n]:=\{1,\ldots,n\}$, thereby inducing an action on the set $$\wp_k(n)=\{\: A\subseteq[n] \::\: \#A=k \:\}$$ of subsets of cardinality $k$, simply by $$(g,A)\mapsto g(A)=\{\: g(a) \::\: a\in A \:\}.$$ This finally yields an action on $V_k:=\mathbb C[\wp_k(n)]$. By Lemma 4 in this paper (arXiv:0903.2864), the character of $V_k$ is given as $$\tag1 \sum_{r=0}^k \chi_{(n-r,r)}$$ where $\chi_\lambda$ is the irreducible character of $S_n$ corresponding to the partition $\lambda\vdash n$. There is no proof of Lemma 4 in the above reference, but the author says that the result is due to Frobenius. I would like to have a reference of $(1)$ - it doesn't have to be the original paper of Frobenius, in fact I would prefer a more recent work which also has a proof.

• See also exercise 8 here: dpmms.cam.ac.uk/study/II/RepresentationTheory/2010-2011/…. To compute the inner product, as in the exercise, observe that under the permutation action of $S_n$ on $X_k\times X_l$, the pairs $(A,B), (C,D)\in X_k\times X_l$ lie in the same $S_n$-orbit if and only if $\#(A\cap B) = \#(C\cap D)$. – Alex B. Mar 6 '13 at 9:49
• I think it makes sense to do this with combinatorial species: the cycle index series (aka Frobenius character) of the species of sets of cardinality $k$ is $h_k$, so the species of subsets of cardinality $k$ of an $n$-element set has cycle index series $h_{n-k}\cdot h_k=h_{n-k,k}$ which equals the sum in display. – Martin Rubey Mar 6 '13 at 19:55

A classical construction of the Specht modules of $S_n$ says that $\chi_{(n-k,k)}$ is present in the character $\pi_k$ of the action $S_n$ on $V_k$, with multiplicity 1. Indeed $M^\lambda:=V_k$ is the permutation module arising along the way of constructing the Specht module $S^\lambda$ for the partition $\lambda=(n-k,k)$.

Moreover, it is easy to see that the centralizer of the action of $S_n$ on $V_k$ in the full matrix algebra of $\binom{n}{k}\times\binom{n}{k}$ is commutative, and has dimension $k+1$ (The centralizer is spanned as an algebra by the 0-1 matrices corresponding to the orbits of $S_n$ on the ordered pairs of $k$-subsets - this is a general fact about permutation representations of finite groups; here these matrices are symmetric, and thus it's a commutative algebra). Thus $\pi_k$ is a sum of $k+1$ irreducible characters, each of them with multiplicity 1. At this moment we know two of them, namely $\chi_{(n-k,k)}$ and $\chi_{(n)}$ (the latter is there, as it's the trivial character, present in every permutation character).

There is a description (see e.g. Volume 2 of the Richard Stanley's book) of irreducible characters arising in $M^\lambda$, for any $\lambda$. Namely, $$M^\lambda=S^\lambda\oplus \oplus_{\mu\triangleright\lambda} K_{\lambda\mu} S^\mu,$$ where $\triangleright$ stands for the dominance partial ordering on the partitions of $n$, and the $K_{\lambda\mu}$'s are famous Kostka numbers (in our case they are all 0 or 1). Using this, one can easily complete the proof of (1).

PS. In Stanley's book, this question is Example 7.18.8 on p.355, Volume 2.

• Where exactly in the book can I find that classical construction of $M^\lambda$? – Karl Mar 6 '13 at 14:11
• No, not in Stanley's book. Any book on the representation theory of $S_n$ will have it, or you can look in these notes, Sect 4.12: ocw.mit.edu/courses/mathematics/… Or Sect.1 of my old lecture notes: www1.spms.ntu.edu.sg/~dima/mas722/2011/notes/snreprs.pdf – Dima Pasechnik Mar 6 '13 at 15:11
• Stanley mostly does the corresponding character theory, in terms of symmetric functions. – Dima Pasechnik Mar 6 '13 at 15:16
• Hm. I don't really see how this all proves the statement, and I still hope that there is a less obscure reference for the statement. I'm sorry, I am quite new to this. – Karl Mar 6 '13 at 15:21
• As you read arXiv:0903.2864, I expected that you know some representation theory of $S_n$. It is not something one can explain in one mathoverflow answer, IMHO. – Dima Pasechnik Mar 6 '13 at 15:30