3
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ 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$. $\endgroup$ Commented Apr 13, 2021 at 16:57
  • 1
    $\begingroup$ @MarkWildon Hence the keyword is the Young permutation module! Thank you very much for your answer! $\endgroup$
    – gualterio
    Commented Apr 13, 2021 at 16:59
  • 1
    $\begingroup$ @MarkWildon: wouldn't what you described be the action of $S_n$ on $k$-tuples of distinct elements of $[n]$? $\endgroup$ Commented Apr 13, 2021 at 17:01
  • $\begingroup$ 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. $\endgroup$ Commented Apr 13, 2021 at 17:16
  • 2
    $\begingroup$ 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)$. $\endgroup$ Commented Apr 13, 2021 at 17:20

2 Answers 2

7
$\begingroup$

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)$.

$\endgroup$
3
  • $\begingroup$ Nice summary!.. $\endgroup$ Commented Apr 13, 2021 at 18:57
  • $\begingroup$ I think your answer will be helpful for my further study in this area. Thank you for the references! $\endgroup$
    – gualterio
    Commented Apr 14, 2021 at 7:58
  • $\begingroup$ Numbering changed to Thm 5.6 in v2. $\endgroup$ Commented Nov 7, 2022 at 22:23
2
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Apr 13, 2021 at 18:12
  • $\begingroup$ @PhilTosteson Yeah, I realized I had some mistakes in my code. It now agrees with the answer above. $\endgroup$ Commented Apr 13, 2021 at 19:07
  • 1
    $\begingroup$ 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). $\endgroup$ Commented Apr 13, 2021 at 19:08
  • $\begingroup$ @SamHopkins Ah, right! I was too hasty. $\endgroup$ Commented Apr 14, 2021 at 6:41
  • 1
    $\begingroup$ Thank you for your answer! I will study your answer. $\endgroup$
    – gualterio
    Commented Apr 14, 2021 at 8:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .