0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ what does ""conjectetive" mean? Do you mean commutative? $\endgroup$ – Anurag A Jul 12 '19 at 18:11
  • $\begingroup$ @AnuragA I meant "conjugacy", sorry $\endgroup$ – vesii Jul 12 '19 at 18:13
  • $\begingroup$ Hint: Show first that $\tau$ is conjugate to $\sigma$ if and only if the representation of $\tau$ as a product of disjoint cycles consists of one cycle of length 3 and one of length 5. $\endgroup$ – David C. Ullrich Jul 12 '19 at 18:21
  • $\begingroup$ @DavidC.Ullrich, I know how to prove it in the slow way. I'm looking for the formula though. $\endgroup$ – vesii Jul 12 '19 at 18:24
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Have you use any generic formula? $\endgroup$ – vesii Jul 12 '19 at 19:35
  • $\begingroup$ The number of $k$-cycles in $S_n$ is $\frac {{}^nP_k}k$. $\endgroup$ – Chris Custer Jul 12 '19 at 19:38
0
$\begingroup$

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)}$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I know how to do it, my question is about the formula. I'm trying to find a formula which calculates it without using the "Conjugacy Lemma". $\endgroup$ – vesii Jul 12 '19 at 18:26
  • $\begingroup$ @vesii I have added a counting technique that will work and perhaps help you to arrive at your formula as well. Unfortunately the notation in your formula is not clear to me. But the technique I have shown is easily generalizable as well. $\endgroup$ – Anurag A Jul 12 '19 at 18:42
  • 1
    $\begingroup$ @vesii I have provided the generalization as well. But I would recommend understanding the procedure of counting as opposed to memorizing strange looking formulas. $\endgroup$ – Anurag A Jul 12 '19 at 21:14
  • $\begingroup$ Perfect! Is it possible to add an example using that generic formula so I can see it in action? For example solving for $(1,7,6)(2,5,9,3,4)$ $\endgroup$ – vesii Jul 13 '19 at 10:26
  • $\begingroup$ @vesii That is already there (see the first part of my answer). $\endgroup$ – Anurag A Jul 13 '19 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.