Let $\lambda$ and $\mu$ be partitions of some integer $n \geq 1$. Let $d$ be the number of parts in $\mu$ and let $\bar{\mu} \in \{1,\dotsc,d\}^n$ denote the string $1^{\mu_1} 2^{\mu_2} \dotsb d^{\mu_d}$ (i.e., $\mu_1$ ones, $\mu_2$ twos, etc.). Let $N_{\lambda\mu}$ denote the number of permutations of cycle type $\lambda$ that leave the string $\bar{\mu}$ invariant.

Does this quantity have a name or is it perhaps related to some other known combinatorial quantity? Is there any simple formula or algorithm for computing it?


One can check that $N_{(2,1,1,1),(3,2)} = 4$ because in the string 11122 there are three ways of swapping ones and one way of swapping twos.

Computing $N_{\lambda\mu}$

More generally one can go about computing $N_{\lambda\mu}$ by packing the cycles $\lambda$ into the histogram $\mu$. We call $\{S_1, \dotsc, S_d\}$ a packing of $\lambda$ into $\mu$ if $S_i$ are disjoint sets such that their union is $\{1, \dotsc, k\}$, where $k$ is the number of parts in $\lambda$, and $\mu_i = \sum_{j \in S_i} \lambda_j$ for all $i \in \{1, \dotsc, d\}$. Then it seems that $$ \begin{align} N_{\lambda\mu} &= \sum_{\{S_1,\dots,S_d\}} \prod_{i=1}^d \binom{\mu_i}{\lambda_{S_i}} \prod_{j \in S_i} (\lambda_j-1)! \\ &= \sum_{\{S_1,\dots,S_d\}} \prod_{i=1}^d \frac{\mu_i!}{\prod_{j \in S_i} \lambda_j} \end{align} $$ where the sum is over all packings of $\lambda$ into $\mu$ and $\binom{\mu_i}{\lambda_{S_i}}$ denotes the multinomial coefficient with the parts of $\lambda$ indexed by $S_i$ at the bottom. Is there any simpler way of doing this?


1 Answer 1


Corrected version. Let $R_{\lambda\mu}$ be the number of words of length $n$ with $\mu_i$ $i$'s that are fixed by a permutation $w$ of cycle type $\lambda$. Using standard symmetric function notation, we have $$ h_\mu = \sum_{\lambda\vdash n}z_\lambda^{-1}R_{\lambda\mu}p_\lambda. $$ By considering the total number of pairs $(w,\alpha)$ such that $w$ has cycle type $\lambda$, $\alpha$ has $\mu_i$ $i$'s for all $i$, and $w\cdot \alpha = \alpha$, we get $$ R_{\lambda\mu}=\frac{z_\lambda}{n!} \binom{n}{\mu_1,\mu_2,\dots}N_{\lambda\mu}. $$ (I am using $N_{\lambda\mu}$ as defined in the question, though it has a different meaning in the standard theory of symmetric functions.) There is further information on this expansion of $h_\lambda$ in the books by Mendes-Remmel and Macdonald, and in Chapter 7 of my book Enumerative Combinatorics, vol. 2.

Note also by the orthogonality of the power sums or by a direct combinatorial argument, we have $$ p_\lambda = \sum_{\mu\vdash n}R_{\lambda\mu}m_\mu. $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.