$S_n$ is a set of all possible permutations of length $n$ here. I think solving it with decrement is too hard and inversions should be used instead. So, it's obvious that $Id$ has zero inversions and 1->n, 2->n-2,...,n->1 has $ \binom{n}{2}$ inversions and it's max possible. Then I tried to find permutation with $\binom{n}{2}-1$, $ \binom{n}{2}-2$ number of inversions so that i could compute desirable product but kinda failed.
Asked
Active
Viewed 50 times
0
-
What is the question? Do you want to compute the product? If yes then note that the number of permutations in $S_n$ is $n!$, and exactly half of them have negative sign. So the product is $(-1)^{\frac{n!}{2}}$, which will be equal to $1$ when $n\geq 4$. – Mark Aug 26 '19 at 19:38
-
@Mark , why exactly half of them will have negative sign? – Назар Петровский Aug 26 '19 at 19:43
-
Have you heard of the alternating group? – Angina Seng Aug 26 '19 at 19:45
-
If $n\geq 2$ then exactly half of them have negative sign, yes. You can easily prove this if you know group theory, as the sign of a permutation is a homomorphism of groups. – Mark Aug 26 '19 at 19:46
-
@Mark Thanks a lot, but unfortunately I am not familiar with group theory. Can it be shown without it? – Назар Петровский Aug 26 '19 at 19:48
-
@LordSharktheUnknown, not yet. – Назар Петровский Aug 26 '19 at 19:49
-
Not sure. Maybe it can be, but I have never seen a different proof. – Mark Aug 26 '19 at 19:51
-
@Mark, thanks, I was thinking maybe if there is a some kind of rule to match every even permutation with uneven then it would be half and half – Назар Петровский Aug 26 '19 at 19:53
1 Answers
2
Assume $n\geq2$, and fix an arbitrary transposition $s$ (transpositions swap two elements, they are odd permutations). There is a bijection between the even permutations of length $n$ and the odd permutations of length $n$ given by taking any permutation $t$, and returning the permutation given by first applying $s$, then applying $t$. In other words, $t\mapsto ts$. We see it is bijective because it is its own inverse. This proves that there are equally many odd and even permutations.
Since there are equally many even and odd permutations, there are $\frac{n!}2$ odd permutations, meaning the given product is equal to $1$ for $n\geq4$, and $-1$ for $n=2,3$.
Arthur
- 199,419
-
Thanks, I'll try to check it. But to clarify is bijection between $t$ and $ts$ or $t$ and $tst$? (not really good with english). edit: I get it, it's $t$ <-->$ts$ bijections – Назар Петровский Aug 26 '19 at 20:08
-
@НазарПетровский Yes, $t\leftrightarrow ts$ is the bijection I had in mind. – Arthur Aug 26 '19 at 20:24
