$\def\S{\mathbb{S}}$ Dear all,
So I have $\S_n$ acting on $\S_n \times \S_n$ via conjugacy. That is:
for $g \in \S_n, (x,y) \in \S_n \times \S_n$: $g(x,y) = (gxg^{-1},gyg^{-1}).$
Is there a general formula (or a nice combinatorial description) for the number of conjugacy classes produced in this case?
Some thoughts on the problem: for a fixed $n$ one can compute this by hand as follows:
Note that if we consider the action of $\S_n \times \S_n$ on $\S_n \times \S_n$ by conjugation, then we have classes of types $(\lambda, \mu)$ for each configuration $\lambda$ and $\mu$ of the Young diagram. Here we restrict ourselves to the diagonal action, so this would split the $(\lambda,\mu)$ pair further. To compute this splitting for a fixed pair $(x,y)$ where $x$ is of type $\lambda$, y is of type $\mu$, let $C(x)$ denotes the centralizer of $x$. For any $g \in \S_n$, write $g = g_1g_x$ for some $g_x \in C(x)$. Then
$(x,y) \sim (g_1xg_1^{-1}, g_1(g_xyg_x^{-1})g_1^{-1})$
Then the number of equivalence classes we have for this pair is the number of orbits of the class $\mu$ acted upon by $C(x)$ via conjugation.
But is there a general formula?
Thanks,
Ngoc
Best Answer
Let me follow up on, and try to clarify some of what has been said. Given a group $G$, we want to count the number of $G$-orbits on $G \times G$, where the action is conjugation in each coordinate. The number of fixed points of $x \in G$ is thus $|C_G(x)|^2$, so by the "Burnside" lemma (due to Cauchy and Frobenius) the number $N$ of orbits is given by $$ N = \frac{1}{|G|}\sum_{x \in G} |C_G(x)|^2 . $$ Grouping together the elements of each class, summing over classes $K$ and using the fact that $|G| = |C_G(x)|K|$, where $K$ is the class of $x$, we get
$$ N = \frac1{|G|}\sum_K |K|\big(\frac{|G|}{|K|}\big)^2 = |G| \sum_K \frac{1}{|K|}. $$
We can easily compute this in Magma for $G = S_n$ for small $n$, and we get: $1,4,11,43,161,901,5579,43206,\ldots$. This appears to match sequence A110143 in the OEIS.