Wreath product $S_k\wr S_n$ inside $S_{kn}$

Question

I want to understand wreath products a little better.

Currently, my intuition about them is as follows. Take $nk$ disks, pile them in order forming $n$ piles of $k$ disks (one pile contains disks {1,...,k}, another pile disks {k+1,...,2k}, so on). The wreath product $H_{k,n}=S_k \wr S_n$ preserves this strucutre, i.e. it only permutes disks within piles or permutes whole piles.

In other words, if $P=S_k\times S_k\times \cdots\times S_k$ is the direct product of groups permuting disks within piles, then $H_{k,n}$ is its normalizer inside $S_{kn}$.

I believe all the above is correct. What I need help with is how $H_{k,n}$ sits inside $S_{kn}$. For example, what is the cardinality of the double coset $H_{k,n}/S_{kn}\backslash H_{k,n}$?

For $k=2$ I known that this cardinality equals $p(n)$, the number of partitions of $n$. (My intuition is that it would always be $p(n)$ for any $k$, but I am not confident about it.)

Suggestions of accessible sources would be welcome (I am a physicist).

Answer 1

The numbers arise in two contexts of physics:

The first is counting symmetric tensor invariants without color. See Counting Tensor Model Observables and Branched Covers of the 2-Sphere, chapter 6.

The second is in the counting of vacuum Feynman graphs. The paper features the enumeration of row/column permutation equivalence classes of RC-magic squares, which are $n\times n$ integral matrices with nonnegative entries whose rows and columns sums to $k$. See A combinatorial matrix approach for the generation of vacuum Feynman graphs multiplicities in φ$^4$ theory.

The equivalence classes of RC-magic squares are in 1-1 correspondence with the double cosets.

To see this, let $g$ be an element of $S_{kn}$, acting on $n$ piles of $k$ disks.

We construct an RC-magic square $M(g)$ in the following way: $M(g)_{ij}$ is the number of elements in the $j$-th pile which were originally in the $i$-th pile.

In order to prove 1-1 correspondence, we need to prove

1)Two elements in the same double coset necessarily corresponds to the same equivalence class

2)Two elements in the same equivalent class necessarily lies in the same coset.

Let $P$ denote the group permuting disks within piles, and $T$ the group permuting piles. Let $H$ be the wreath product group.

To prove 1), let $g'=h_1gh_2$, where $h_1,h_2\in H$. Then there exists $p_1,p_2\in P$, $t_1,t_2\in T$ such that $g'=t_1p_1gp_2t_2$. $p_1$ and $p_2$ induce no action on $M(g)$, $t_1$ permute the rows, and $t_2$ permute the columns. So $g$ and $g'$ belongs to the same equivalent class.

To prove 2), let $M(g)$ and $M(g')$ lie in the same class. Then $M(g)=t_1M(g')t_2$ for some $t_1,t_2\in T$. ($t_1$ and $t_2$ induce actions on $M(g')$). So $g$ and $t_1g't_2$ moves the same number of balls from pile $i$ to pile $j$ for each $i,j$, which means they differ by elements in $P$: $p_1g=t_1g't_2p_2$ for some $p_1,p_2\in P$. (It is possible to make the point more rigorous, by assigning an order on the elements, and let $p_1$ and $p_2$ sort the elements in each pile). It follows that $g$ and $g'$ are in the same coset.

For $k=3$, one can find the exact numbers in Ronald C. Read's PhD Thesis, Some enumeration problems in graph theory, page 156. The asymptotics are given as

$$ \frac{(3n)!}{(n!)^26^{2n}}\exp\Bigl(2 - \frac{2}{9n} + O(n^{-2})\Bigr),$$

which can be found in Brendan Mckay's MathOverflow answer.