2

I have a question to an exercises which i cannot solve:

Determine all $n\geq 6$ for which the following statement is correct: There are as many permutations with $n-2$ fixed-points and one $2$-cycle as permutations with $n-6$ fixed-points and three $2$-cycles.

I'm trying to find a bijection between the two sets of those permutation but i can't find a function.

Any help is highly appreciated. Thanks!

Edit: Made a mistake in the problem of the exercise. The bold text is edited.

Michael Hardy
  • 1
Maletisiia
  • 57
  • Just count them. – Paul Jul 16 '17 at 17:12
  • @Paul How can I exactly do that? I have some trouble to count that. – Maletisiia Jul 16 '17 at 17:27
  • 1
    @Maletisiia Are you sure that the statement of your problem is correct? – Robert Z Jul 16 '17 at 17:41
  • 1
    It seems like this is false already for $n=7$. – Matt Samuel Jul 16 '17 at 17:53
  • @RobertZ You where right, i made a mistake, its edited. I`m sorry for that. Thanks for pointing it out :) – Maletisiia Jul 16 '17 at 18:05
  • Just wanted to point out, the only $n$ for which $S_n$ has an outer automorphism is $n=6$, in which case ${\rm Out}(S_6)\cong\Bbb Z_2$ and the nontrivial ones permutes conjugacy classes - in particular they swap permutations of cycle type $(xy)$ with those of cycle type $(ab)(cd)(ef)$. – anon Jul 16 '17 at 19:19

2 Answers2

3

The proposition is true only when $n=6.$ (The question has been edited so that $n=1$ or $n=0$ need no longer be mentioned.)

The number of ways to choose a $2$-cycle is $\dbinom n 2.$

The number of ways to choose three $2$-cycles is $\dbinom n 6 \cdot 15,$ since there are $15$ ways to make a set of $6$ into three $2$-cycles.

So you need $\dbinom n 6 \cdot 15 = \dbinom n 2.$

$$ \frac{n(n-1)(n-2)(n-3)(n-4)(n-5)} {6\cdot5\cdot4\cdot3\cdot2\cdot1} \cdot 15 = \frac{n(n-1)} 2. $$ $$ (n-2)(n-3)(n-4)(n-5) = 24. \tag 1 $$ If $n>6$ then the left side of $(1)$ is $>24.$ If $2\le n\le 5$ then the left side of $(1)$ is $0.$

Michael Hardy
  • 1
  • Are we getting the 15 ways to make a set of 6 into three 2-cycles with $\binom{6}{2}$ in this case? – Maletisiia Jul 16 '17 at 18:20
  • @Maletisiia : Yes. $\qquad$ – Michael Hardy Jul 16 '17 at 18:21
  • 2
    @Michael Hardy You forgot a factorial. It should be $\frac{n(n-1)(n-2)(n-3)(n-4)(n-5)}{6!}$ – Robert Z Jul 16 '17 at 18:29
  • $$ \begin{align} 1 & & ab/cd/ef \ 2 & & ab/ce/df \ 3 & & ab/cf/de \ \ 4 & & ac/bd/ef \ 5 & & ac/be/df \ 6 & & ac/bf/de \ \ 7 & & ad/bc/ef \ 8 & & ad/be/cf \ 9 & & ad/bf/ce \ \ 10 & & ae/bc/df \ 11 & & ae/bd/cf \ 12 & & ae/bf/cd \ \ 13 & & af/bc/de \ 14 & & af/bd/ce \ 15 & & af/be/cd \end{align}$$ – Michael Hardy Jul 16 '17 at 18:31
  • @RobertZ : Fixed. Thank you. $\qquad$ – Michael Hardy Jul 16 '17 at 18:33
  • 1
    @Maletisiia Another way to see why there are $15$ ways to make a set of six elements into three $2$-cycles is to list the elements in some order, match the first element in the list with one of the other five elements to form a $2$-cycle. Remove those elements, which leaves four elements. Match the first element remaining in the list with one of the other three elements to form another $2$-cycle. There is only one way to match the two remaining elements. Hence, there are $5 \cdot 3 \cdot 1 = 15$ ways to form three $2$-cycles from a set with six elements. – N. F. Taussig Jul 16 '17 at 18:38
2

The number of permutations of $\{1,\dots,n\}$ with $c_k$ cycles of size $k$ for $k=1,\dots, n$, is given by $$\frac{n!}{(1^{c_1}\cdot 2^{c_2}\cdots n^{c_n})(c_1!\cdot c_2!\cdots c_n!)}.$$ (see Number of permutations for a cycle-type). Speaking briefly, we have $n$ positions: the first $c_1$ are the $1$-cycles (fixed points), the next $2c_2$ are the $2$-cycles an so on. We arrange the $n$ elements in $n!$ ways, and for each $k$ we divide by $c_k!$ because the order of the $k$-cycles is indifferent, and we divide also by $k^{c_k}$, because a shift in a $k$-cycles is indifferent.

Now we find in your example the cardinalities of the two sets of permutations.

1) $(n-2)$-cycles and one $2$-cycle: $$\frac{n!}{(1^{n-2}\cdot 2^{1})((n-2)!\cdot 1!)}=\frac{n(n-1)}{2}$$

2) $(n-6)$-cycles and three $2$-cycle: $$\frac{n!}{(1^{n-6}\cdot 2^{3})((n-6)!\cdot 3!)}=\frac{n(n-1)(n-2)(n-3)(n-4)(n-5)}{48}$$ When are they equal?

Robert Z
  • 145,942