# A general formula for the number of conjugacy classes of $\mathbb{S}_n \times \mathbb{S}_n$ acted on by $\mathbb{S}_n$

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

-
You say you can compute this for fixed $n$. Have you tried computing the first few terms and looking in the Encyclopedia of Integer Sequences? –  Michael Lugo Oct 6 '10 at 21:55
research.att.com/~njas/sequences/A110143 no formula is given. –  Steve D Oct 7 '10 at 1:57
What's wrong with the generating function given there? –  Martin Rubey Oct 7 '10 at 18:31

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.

-
Try oeis([sum([la.centralizer_size() for la in Partitions(n)]) for n in range(1, 23)]) in sage; matches all 22 entries for A110143 in OEIS. –  Amritanshu Prasad Apr 3 '14 at 4:42

The question is equivalent to asking for the number of homomorphisms of the free group on 2 generators to $\mathbb S_n$, up to conjugacy.

For large n, the majority of homomorphisms are epimorphisms, that is, most pairs of elements generate the full symmetric group: if they do not generate, they both lie in a proper subgroup, the biggest of which has index $n$ so has frequency $1/n^2$ ... and other terms trail off. The orbit of a pair of generators under the conjugacy action is free, so there are somewhat less than $n!*n!/n! = n!$ pairs of generators, up to conjugacy. In addition, there are pairs that do not generate, which have smaller orbits, but still, $n!$ is a good enough number for many purposes. You couldn't compute many of these by hand without further insight because of the combinatorial explosion.

Both GAP and Magma can compute this kind of thing for small n, and in particular they have highly-tuned functions to compute the related enumeration of epimorphisms from a finitely presented group to a finite group, up to automorphism of the target. Applying this to the free gropu, the first few numbers are (from GAP):

f = FreeGroup(2);;
epis := List( [2..6], i -> GQuotients(f, SymmetricGroup(i)) );;
List(epis, Length);
[ 3, 3, 9, 57, 159 ]


Neither this sequence nor $1,3,3,9,57,159$ (where the case for $\mathbb S_1$ is prepended) registers a hit in the OEIS. I have no expertise in combinatorics, but it seems to me probably difficult to get a good general exact formula for the number of homomorphisms, although it shouldn't be hard to get reasonable estimates.

-
In what way is the answer related to the question? –  Guntram Oct 7 '10 at 9:50
The first paragraph directly addresses the question by giving a rough estimate of the number of equivalence classes. The GAP computation is of a commonly-studied set of numbers for a variation of the question, where it was easy to get the first few numbers. The lack of hits in the OEIS suggests it's not likely there's a known good pattern or formula. With more work one could compute similar numbers for the original question, but I answered what I had time for. –  Bill Thurston Oct 7 '10 at 11:43
@Guntram: Rereading my answer, I saw that I made abrupt leaps, so I added some connective sentences to clarify the connection of what I was doing to the wording of the question. Someone with better fluency than me in GAP or Magma, or who is good at hand calculation, should calculate the first few terms of the sequence as requested, and more terms of the sequence I gave (I stopped where I did because it required changing memory parameters to go further, and I didn't want to mess with it). –  Bill Thurston Oct 7 '10 at 11:52
I am confused. How could this be the right answer? For S_2 acting on S_2 x S_2, there should be 4 orbits, not 3. –  Steve D Oct 7 '10 at 11:59
@Steve D: The numbers above are not for the original question (homomorphisms up to conjugacy), but for the related question of epimorphisms up to automorphism, just because the latter question has a built-in GAP function, GQuotients. Efficiency is a critical issue in computations like this because of the combinatorial explosion, so I didn't want to casually code the original question from scratch. –  Bill Thurston Oct 7 '10 at 12:10

I don't know that it is of the type you wish, but there is a formula of sorts.

Consider the more general case of a finite group $G$ acting diagonally by conjugation on the set of $k$-tuples of elements of $G$. For a fixed $g$ in $G$, the number of fixed points of $g$ is $|C_G(g)|^k$. Let $g_1,\dots,g_c$ be a set of representatives for the conjugacy classes of $G$. Applying Burnside's Lemma and grouping together elements in the same conjugacy class, we see that the number of orbits of $G$ in the given action is the sum over all $g_i$ of $|C_G(g_i)|^{k-1}$.

So, in your case, we have the sum of $|C_G(g_i)|$ over a set of representatives for the conjugacy classes of $S_n$. As you noted, these classes are parameterized by partitions of n, and if such a partition $p$ has $a_j$ parts of size $j$ for each $j$ in $[n]$, the order of the corresponding centralizer is the product over all such $j$ of $(a_j)!j^{a_j}$. Thus we get the sum over all partitions of n of such products.

Maybe it is worth remarking that, for any $G$, when $k=2$ the number in question is the sum of the square norms of the entries of the character table of $G$.

-

The answer by Marty Isaacs is, of course, correct. For a general group $G,$ the number of orbits of $G$ acting by conjugation on $G \times G$ by conjugation (when diagonally embedded) is equivalently expressible as $\sum_{x}|C_{G}(x)|,$ where $x$ runs over a full set of representatives for the conjugacy classes of $G.$

For the symmetric group $S_{n}$ , the conjugacy classes are labelled by the partitions of $n.$ The centralizer of an element with cycle structure labelled by $\lambda = 1^{m_{1}}2^{m_{2}} \ldots r^{m_{r}}$ is $\prod_{i} C_{i} \wr S_{m_{i}}$ (direct), where $C_{i}$ denotes the cyclic group of order $i.$ The order of the centralizer of such an element is therefore $\prod_{i=1}^{r} i^{m_{i}} m_{i}!,$ which we denote by $w(\lambda).$

Hence the required number of orbits is $\sum_{\lambda} w(\lambda),$ where $\lambda$ runs over the partitions of $n.$

-

I discovered this old question in connection with someone else's similar (and current) question: The Simultaneous Conjugacy Problem in the symmetric group $S_N$

If anyone still cares, here is a slightly different answer for your question using the character table instead of centralizer sizes. The characters might be more accessible in certain cases (and of interest in their own right). $$N=\frac{1}{n!} \sum_{\alpha \in G} \left( \sum_{\text{irreps}\ \chi} \chi(\alpha)^2 \right)^2$$ The inner sum is just the centralizer term in Marty Isaacs answer, but expressed in a different way. It might be of some use in this form. For example, if you want to enrich the group action to allow coordinate swap or inversion, similar class functions can be used.

The OP and others may be interested in the above linked question, which discusses the related decision problem and the generalization to more coordinates.

-