# The number of permutations of a given cycle type that fix a string with a given histogram

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?

Example

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?

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