# Reference for this combinatorial formula

This is probably standard representation theory and my phrasing is probably bad. Can someone give me a reference/standard way to state the following (proofs are also welcome):

Let $r = (a_1, \ldots, a_{1}, a_2 \ldots, a_2, \ldots, a_{d}, \ldots, a_{d})$ be a sequence of symbols of length $n$ where $a_i$ appears $t_i$ times. So $\sum_{i=1}^{d} t_i =n$.

Let $S$ denote the set of all the permutations of $r$ (ignoring repetitions of course). Then $S_n$ (and its subgroups) acts on the set $S$.

Consider the following $S_n$ representation $W := \bigoplus_{s\in S} (V_s^{\otimes n})$ where $V_s = V$ is a fixed vector space of dimension $k$

$\sigma \in S_n$ takes $(v_1 \otimes \ldots \otimes v_n) \in V_s^{\otimes n}$ to $(v_{\sigma(1)} \otimes \ldots \otimes v_{\sigma(n)}) \in V_{\sigma(s)} ^{\otimes n}$.

Then the following formula holds:

$\dim W^{S_n} = \sum_{r_1, ..., r_k ; \\ r_i \ge 0 ; \\ r_1 + \ldots + r_k = n} \text{(number of orbits of}$ $S_{r_1} \times \ldots S_{r_k}$ $\text{action on }$ $S \text{)}$.

(Well here is something that works I guess: First lets choose $x_1, \ldots, x_k$, a basis of $V$. Pick an orbit $O$ of $S_{r_1} \times \ldots S_{r_k}$ under the action of $S$. Then we create a basis element for the left hand side. Let $u = x_1 \otimes \ldots \otimes x_1 \otimes x_2 \otimes \ldots \otimes x_k \otimes \ldots \otimes x_k$ where $x_i$ appears $r_i$ times. Now consider

$$v:= \sum _{o \in O} u_o \in W$$ where $u_o$ is $u$ siting at the $o$-th place in the direct sum decomposition of $W$. The element $v$ is invariant under $S_{r_1} \times \ldots S_{r_k}$. Now $$\sum_{\overline{g} \in S_n /S_{r_1} \times \ldots S_{r_k}} \overline{g}.v$$ is $S_n$ invariant. )