Stanley's Positivity Problems in Algebraic Combinatorics — Problem 12: Combinatorial interpretation of the row sums of the character table of S_n

Definitions and mathematical statement

Let $n\geq 1$ be an integer, and let $S_n$ be the symmetric group on $\{1,\ldots,n\}$. A partition $\lambda\vdash n$ is a weakly decreasing finite sequence of positive integers summing to $n$. Write $\chi^\lambda$ for the irreducible complex character of $S_n$ indexed by $\lambda$, and let $\mathcal K_n$ be the set of conjugacy classes of $S_n$. For $K\in\mathcal K_n$, write $\chi^\lambda(K)$ for the common value of this character on $K$. Define the unweighted row sum \[ r_\lambda=\sum_{K\in\mathcal K_n}\chi^\lambda(K). \] Thus each conjugacy class contributes once, without a factor equal to its size.

Let $S_n$ act on the complex vector space with basis $\{e_h:h\in S_n\}$ by $g\cdot e_h=e_{ghg^{-1}}$, and denote the character of this permutation representation by $\psi_{S_n}$. The source supplies the identity \[ r_\lambda=\langle\psi_{S_n},\chi^\lambda\rangle_{S_n}\in\mathbb Z_{\geq0}, \qquad \langle\alpha,\beta\rangle_{S_n} =\frac{1}{n!}\sum_{g\in S_n}\alpha(g)\overline{\beta(g)}. \]

Problem (Stanley, 1999, Problem 12). For every $n\geq1$ and every $\lambda\vdash n$, give a combinatorial interpretation of $r_\lambda$: describe a finite family of combinatorial objects, defined explicitly from $\lambda$, whose cardinality is $r_\lambda$, thereby giving a combinatorial proof that these row sums are nonnegative. The source does not prescribe the type of combinatorial objects or a particular construction. Its supplied status label is open; that label is not an independently verified assessment.

Short English statement

For each irreducible character of $S_n$, add its values over all conjugacy classes, counting each class once. Find combinatorial objects counted by this sum, so that its nonnegativity follows from counting. The source already identifies the sum as a representation multiplicity; the requested interpretation should provide the combinatorial explanation.

Sources

• Local UnsolvedMath registry, supplied complete source record: permanent ID $801185$, source problem code catalogue entry, AMR Open Problem Lists. The record attributes the problem to Stanley (1999) and labels it open. Its supplied upstream revision is d371ee917ac9647fbb06cd6fc529deec6f3dda82.
• Stanley, Positivity Problems and Conjectures in Algebraic Combinatorics (1999), Problem 12. Supplied source URL: https://math.mit.edu/~rstan/papers/problems.pdf. The record reports access on 2026-10-16 and extraction by pdf+html_verified; these are supplied provenance claims, not independent verification performed for this draft.
• The supplied background also refers to Stanley, Enumerative Combinatorics, Vol. 2, Exercise 7.71. No edition or URL for this reference is supplied.