# Is there any simple formula for the character of $S_{n}$ represented by the set of $k$-tuples of $\{1,2,...,n\}$?

I'm interested in the representation theory of symmetric groups.

I'm now trying to search for the formula for the characters of $$\Omega^{k}$$, the set of $$k$$-tuple of elements of $$\Omega$$ a set of $$n$$ elements where $$S_{n}$$ acts in the standard way.

More precisely, I want to know the formula for the expansion of the characters of $$\Omega^{k}$$ into the linear combination of irreducible characters $$\chi^{\lambda}$$ labeled by the partitions $$\lambda$$.

It seems that such a formula was used in the old papers (for example papers of Frobenius) to compute the character tables.

So I hope there is some simple well-known formula.

Is there any? Or can we just use the Littlewood Richardson Rule on the power of $$1 + \chi^{(n-1,1)}$$ manually?

Any references are welcome.

• This is the character of the Young permutation module $M^{(n-k,1^k)}$, or the character usually denoted $\pi^{(n-k,1^k)}$ and the decomposition is given by Young's rule. You can also use the more general Littlewood–Richardson Rule if you like. Anyway, the multiplicity of $\chi^\lambda$ is the number of semistandard $\lambda$-tableaux with content $(n-k,1^k)$, i.e. the number of standard $\lambda$-tableaux with $n-k$ $1$s, and one each of $2$, $\ldots$, $k+1$. Apr 13 at 16:57
• @MarkWildon Hence the keyword is the Young permutation module! Thank you very much for your answer! Apr 13 at 16:59
• @MarkWildon: wouldn't what you described be the action of $S_n$ on $k$-tuples of distinct elements of $[n]$? Apr 13 at 17:01
• Since the action (for $k>1$) is not transitive, it cannot be the same as the action on a Young subgroup. But probably you can express it as a sum of these. Apr 13 at 17:16
• Yes, I assumed, partly from the reference to Frobenius, that a transitive action was intended. But as you say, if the content is arbitrary one just gets a sum of the $\pi^{(n-j,1^j)}$: the multiplicity of $\pi^{(n-j,1^j)}$ is the number of partitions of $k$ into exactly $j$ parts. For instance if $k=4$ then we have $2\pi^{(n-2,1,1)}$, corresponding to the two orbits containing $(1,1,2,2)$ and $(1,1,1,2)$. Apr 13 at 17:20

There are several possible interpretations of $$\Omega^k$$ (admittedly some don't quite align with what you ask): ordered/unordered subsets of $$k$$ distinct/not necessarily distinct elements of $$[n]$$. There are two questions about them, "what is the character?" and "what are the multiplicities of irreducibles?".

Case 1: ordered, not necessarily distinct

In this case we can recognise the permutation representation as just the $$k$$-th tensor power of $$\mathbb{C}^n$$ (with the usual action). Since the character of $$\mathbb{C}^n$$ on an element of cycle type $$\mu$$ is just $$m_1(\mu)$$ (the number of parts of size $$1$$ in $$\mu$$), the character of $$\Omega^k$$ is $$m_1(\mu)^k$$. The multiplicity rules can be easily deduced from the rule for taking the tensor product with $$\mathbb{C}^n$$. Details can be found in RSK Insertion for Set Partitions and Diagram Algebras and the answer is "vacillating tableaux of shape $$\lambda$$ and size $$k$$". (Caveat: you need to be a little more careful if $$n$$ is smaller than $$2k$$, for example if $$n=1$$, then any tensor power of $$\mathbb{C}^n$$ is still just $$\mathbb{C}^n$$, which is definitely not true if $$n > 1$$. Feel free to ask for more detail if Secion 2 of the paper doesn't address your concerns.)

Case 2: unordered, not necessarily distinct

In this case, we can recognise $$\Omega^k$$ as the $$k$$-th symmetric power of $$\mathbb{C}^n$$. One way to view this is as the restriction of $$\mathrm{Sym}^k(\mathbb{C}^n)$$ from $$GL_n(\mathbb{C})$$ to $$S_n$$ (viewed as the subgroup of permutation matrices). Hence the character is obtained by evaluating the Schur polynomial $$s_k(x_1, x_2, \ldots, x_n)$$ at the eigenvalues of a permutation matrix (each $$r$$-cycle contributes the set of all $$r$$-th roots of unity). You can read more about this approach in Symmetric group characters as symmetric functions. As for the multiplicities, there is a (well-known?) formula which can be found in Exercise 7.74 of Enumerative Combinatorics Vol. 2 which states that the multiplicity of the irreducible $$S^\mu$$ in the $$GL_n(\mathbb{C})$$ irreducible indexed by $$\lambda$$ is

$$\langle s_\lambda, s_\mu[1 + h_1 + h_2 + \cdots ] \rangle$$

where $$s_\lambda, s_\mu$$ are Schur functions, square brackets denote plethysm, and $$h_i$$ are complete symmetric functions. In our case, $$\lambda = (k)$$ and we can use some tricks (which I can elaborate on, if requested) to deduce that the multiplicity is the number of semi-standard Young tableau of shape $$\mu$$ and weight $$\nu$$, such that $$0 \nu_1 + 1 \nu_2 + 2 \nu_3 + \cdots = k$$.

Case 3: ordered, distinct

Note first of all that if we require distinctness, $$k \leq n$$. As Mark Wildon pointed out in the comments, we may recognise $$\Omega^k$$ as the permutation module $$M^{(n-k, 1^k)}$$ (i.e. indexed by the partition that has $$k$$ parts of size 1, and one part of size $$n-k$$). The number of fixed points of an elements of cycle type $$\mu$$ is $${m_1(\mu) \choose k}$$ (so this is the character). The multiplicity of $$S^\lambda$$ is given by the number of semi-standard Young tableaux of shape $$\lambda$$ and weight $$(n-k, 1^k)$$.

Case 4: unordered, distinct

We can identify $$\Omega^k$$ as the permutation module $$M^{(n-k,k)}$$. Although this has a basis that can be identified with the $$k$$-th exterior power of $$\mathbb{C}^n$$, that is not the correct representation because swapping two adjacent elements of a wedge monomial incurs a sign, while swapping to elements of an unordered set does not. This was investigated by Stier, Wellman, and Xu in Dihedral Sieving on Cluster Complexes; see Theorem 6.4. Similarly to Case 2, This gives a polynomial, which when evaluated at eigenvalues of a permutation matrix, gives the character. As for the multiplicities, they are given by the number of semi-standard Young tableaux of shape $$\lambda$$ and weight $$(n-k,k)$$.

• Nice summary!.. Apr 13 at 18:57
• I think your answer will be helpful for my further study in this area. Thank you for the references! Apr 14 at 7:58

EDIT: I realized my previous answer used buggy code. The stuff below should be more correct.

The Frobenius characteristics for different values of $$n$$, $$1\leq k\leq n$$ are $$\begin{array}{lllll} s_1 & \text{} & \text{} & \text{} & \text{} \\ s_2+s_{11} & s_2 & \text{} & \text{} & \text{} \\ s_3+s_{21} & s_3+s_{21} & s_3 & \text{} & \text{} \\ s_4+s_{31} & s_4+s_{22}+s_{31} & s_4+s_{31} & s_4 & \text{} \\ s_5+s_{41} & s_5+s_{32}+s_{41} & s_5+s_{32}+s_{41} & s_5+s_{41} & s_5 \\ \end{array}$$

In general, the Frobenius characteristic is just $$h_{n-k}h_k$$ where $$h$$ is a complete homogeneous symmetric function. Expanding these in the Schur basis can be done with the Pieri rule, and here we see that the multiplicities are Kostka coefficients (i.e., a number of SSYT).

I just follow these steps to compute the Frobenous characteristic explicitly. We let $$M$$ be the $$S_n$$-module with basis $$\{x_{T}\}$$ with $$T\subset \binom{[n]}{k}$$. This is clearly $$\binom{n}{k}$$-dimensional. Also, $$S_n$$ act on $$M$$ by acting on the variable indices.

We want to see how $$\sigma \in S_n$$ act on a basis vector. Here, $$\sigma (x_S) = 0 x_{T_1} + 0 x_{T_2}+ \dotsb + 1 x_{\sigma(S)}+ \dotsb + 0 x_{T_\ell},$$ for general $$\sigma \in S_n$$. We express this as a square matrix, with $$\binom{n}{k}$$ rows/columns. The trace of this matrix is the character value of $$\sigma$$. We sum $$p_{\lambda(\sigma)}$$ over all $$\sigma$$, and divide the total with $$n!$$. This gives the following table.

$$\begin{array}{lllll} p_1 & \text{} & \text{} & \text{} & \text{} \\ p_{11} & \frac{1}{2} \left(p_2+p_{11}\right) & \text{} & \text{} & \text{} \\ \frac{1}{6} \left(3 p_{21}+3 p_{111}\right) & \frac{1}{6} \left(3 p_{21}+3 p_{111}\right) & \frac{1}{6} \left(2 p_3+3 p_{21}+p_{111}\right) & \text{} & \text{} \\ \frac{1}{24} \left(8 p_{31}+12 p_{211}+4 p_{1111}\right) & \frac{1}{24} \left(6 p_{22}+12 p_{211}+6 p_{1111}\right) & \frac{1}{24} \left(8 p_{31}+12 p_{211}+4 p_{1111}\right) & \frac{1}{24} \left(6 p_4+3 p_{22}+8 p_{31}+6 p_{211}+p_{1111}\right) & \text{} \\ \frac{1}{120} \left(30 p_{41}+15 p_{221}+40 p_{311}+30 p_{2111}+5 p_{11111}\right) & \frac{1}{120} \left(20 p_{32}+30 p_{221}+20 p_{311}+40 p_{2111}+10 p_{11111}\right) & \frac{1}{120} \left(20 p_{32}+30 p_{221}+20 p_{311}+40 p_{2111}+10 p_{11111}\right) & \frac{1}{120} \left(30 p_{41}+15 p_{221}+40 p_{311}+30 p_{2111}+5 p_{11111}\right) & \frac{1}{120} \left(24 p_5+20 p_{32}+30 p_{41}+15 p_{221}+20 p_{311}+10 p_{2111}+p_{11111}\right) \\ \end{array}$$

Converting to the Schur basis gives the decomposition into irreducibles.

• I'm confused by this answer: first the OP seemed to want the product not the set of size $k$ subsets, and second you seem to be claiming that Sn acts trivially on size k subsets, which is false. Apr 13 at 18:12
• @PhilTosteson Yeah, I realized I had some mistakes in my code. It now agrees with the answer above. Apr 13 at 19:07
• You're still answering the question for subsets and not tuples. The subsets question is well-known and explained for instance in Stanley's EC 2, Example 7.18.8(a) (as I had mentioned in a previous comment which I deleted after realizing the OP was interested in tuples). Apr 13 at 19:08
• @SamHopkins Ah, right! I was too hasty. Apr 14 at 6:41