Formula to find the number of conjugacy elements with a permutation

Question

While trying to solve exercises about permutation, I came across with the following question:

Find the number of permutations in $S_9$ that conjugacy with $\sigma = (1,7,6)(2,5.9,3,4)$.

In the solution they just said to use the following formula:

$$\prod_{k=1}^t (size\_of\_k) \cdot \prod_{k=1}^{m} (q_k !) \cdot (n-appear)!$$

I'm not familiar with this formula and I don't understand how to use it. The formula is written without any additional context. Tried to search web through similar formula but without any success. Is it possible to explain how to use this formula in order to find the number of conjugacy elements?

EDIT: Maybe they meant:

$$\prod_{k=1}^t (size\_of\_tuple) \prod_{k=1}^m q_k! \cdot (number\_of\_elements\_that\_does\_not\_appear)$$

where $q_k$ is the number of tuples of order $k$, $m$ the size of the max tuple and $t$ is the number of disjoint tuples?

Answer 1

Two permutations $\alpha$ and $\beta$ are conjugate if there exists a permutation $\tau$ such that $\beta=\tau \alpha\tau^{-1}$. Moreover conjugate of a cycle $(a_1 \, a_2 \ldots a_k)$ is given by $$\tau (a_1 \, a_2 \ldots a_k) \tau^{-1}=(\tau(a_1) \, \tau(a_2) \ldots \tau(a_k)).$$ With this and using the fact that disjoint cycles commute, we get: $$\tau (1 \,7 \, 6)(2 \, 5 \, 9 \, 3 \, 4 )\tau^{-1}=(\tau(1) \,\tau(7) \, \tau(6)) \,\, (\tau(2) \, \tau(5) \, \tau(9) \, \tau(3) \, \tau(4) ).$$ Thus a $(5,3,1)$ cycle type gets mapped to a $(5,3,1)$ cycle type under conjugation.

So you have to now count how many permutations with cycle type $(5,3,1)$ are there. Can you proceed from here?

---

A counting technique:

Suppose we have $[9]=\{1,2,3,4,5,6,7,8,9\}$. Consider a permutation written as follows (note: I have put separators to indicate a 3-cycle, a 5-cycle and a 1-cycle): $$a_1 \, a_2 \, a_3 || a_4 \, a_5 \, a_6 \, a_7 \, a_8 || a_9.$$ Each permutation of $[9]$ can be written as above. then the number of permutations of these without any restrictions would be $9!$. But because of the cycles representing the same permutation when objects within are shifted cyclically. We have to compensate for the overcounting. Since $(a_1 \, a_2 \, a_3)=(a_2 \, a_3 \, a_1)=(a_3 \, a_1 \, a_2)$ so will divide by $3$ to compensate for the overcounting. Same with a $5-$cycle. Thus the number of permutations in $S_9$ with $(5,3,1)$ cycle type are: $$\frac{9!}{3 \cdot 5}.$$

---

Generalization

Suppose you want to find how many permutations in $S_n$ are of cycle type $(k_1^{r_1}, k_2^{r_2}, \ldots ,k_t^{r_t})$, where $k_i$ represents the length of the $i-$th cycle, $k_1>k_2>k_3 \dotsb > k_t$, $r_i$ represents the number of cycles of length $k_i$ and $\sum_{s=1}^{t}r_sk_s=n$.

For example, in $S_{12}$ a permutation $\alpha$ is of cycle type $(3^2,2^2,1^2)$ if it's disjoint cycle representation is $\alpha=(abc)(def)(gh)(ij)(k)(l)$.

Using the technique I showed above we can find the number of permutations in $S_n$ are of cycle type $(k_1^{r_1}, k_2^{r_2}, \ldots ,k_t^{r_t})$ as

$$\frac{n!}{\left(\prod_{s=1}^{t}r_s!\right) \,\, \left(\prod_{s=1}^{t}(k_s)^{r_s}\right)}$$

Answer 2

Should be $\frac{{}^9P_3}3\frac{{}^6P_5}5=3\cdot8\cdot 7\cdot6\cdot4\cdot 3\cdot2=24192$.