# What will be the possible permutations of set S={1,2,3,4}. And how many are of those odd and even?

I have solved it as per my knowledge and understanding. Since there are 4 elements so no. of permutations will be $$4! = 24$$ $$(1,2,3,4), (1,2,4,3), (1,3,2,4), (1,3,4,2), (1,4,2,3), (1,4,3,2), (2,1,3,4), (2,1,4,3), (2,3,1,4), (2,3,4,1), (2,4,1,3), (2,4,3,1), (3,2,1,4), (3,2,4,1), (3,1,2,4), (3,1,4,2), (3,4,2,1), (3,4,1,2), (4,2,3,1), (4,2,1,3), (4,3,2,1), (4,3,1,2), (4,1,2,3), (4,1,3,2)$$

Is it correct?

• And for even and odd-

Even: product of even no of transpositions. e.g., $(1,2,3) = (1,2)(1,3)$ is even Odd: product of odd no of transpositions. e.g., $(1,2,3,4) = (1,2)(1,3)(1,4)$ is odd.

• But if I apply this theory in this question then all permutations will be odd. I am confused here, is my solution incorrect? May be there will be more permutations with less elements like $(1,2,3) , (1,2,4)$?

• Also there is a swapping logic! If the numbers are swapped odd times then it is odd and even otherwise

So in this case $(1,2,3,4)$ is even (no swaps) $(3,2,1,4)$ = Swap 1<->3 is odd Also $(4,2,1,3)$ = Swap 3<->4 then swap 1<->4 = even permutation

What will be the answer to my question?

• Be careful on which notation you use for your permutations, as this is what has lead to your confusion. On $n$ points there are $n!$ permutations, half of which are odd, and the other half of which are even. I would suggest reading up on the Symmetric Group $S_n$. – Bill Wallis May 5 '18 at 16:36
• Oh! I'm sorry! I feel disappointed and demotivated now. I don't think i will be able to understand this. :( btw Thank you so much for your valuable replies. – Ankit Kumar May 5 '18 at 16:46
• @RoryDaulton Here math.stackexchange.com/questions/361822/odd-even-permutations in the last answer he has written "For example (132) is an even permutation as (132)=(13)(12) can be written as a product of 2 transpositions." Is that wrong too? – Ankit Kumar May 5 '18 at 16:56
• @RoryDaulton There is nothing wrong with $(1,2,3)=(1,2)(1,3)$. The way you multiply depends on whether your permutations are acting on the left or on the right. I presume you would have them act on the left, in which case $(1,2,3)=(1,3)(1,2)$, but if they act on the right then $(1,2,3)=(1,2)(1,3)$. – Robert Chamberlain May 5 '18 at 17:03

There are twenty four elements in $\mathcal{S}_4$, namely $$\{\operatorname{id}, (1\ 2), (1\ 3), (1\ 4), (2\ 3),\ (2\ 4), (3\ 4), (1\ 2\ 3),\ (1\ 2\ 4), (1\ 3\ 4), (2\ 3\ 4),\ (1\ 3\ 2),\ (1\ 4\ 2),\ (1\ 4\ 3), (2\ 4\ 3),\ (1\ 2\ 3\ 4), (1\ 3\ 4\ 2), (1\ 4\ 2\ 3), (4\ 3\ 2\ 1), (2\ 4\ 3\ 1), (3\ 2\ 4\ 1), (1\ 2)(3\ 4), (1\ 3)(2 \ 4),\ (1\ 4)(2\ 3)\}.$$ In general; there are $n!$ elements in $\mathcal{S}_n.$

Now, list the cycle types of $\mathcal{S}_4$ $$\{(1, 1, 1, 1), (2,1,1),(2,2),(3,1),(4)\}.$$ List how many cycles each cycle type takes, let's call this quantity $\gamma(a)$ where $a$ corresponds to each cycle type. Then $$\gamma(1,1,1,1)=4,\quad\gamma(2,1,1)=3,\quad\gamma(2,2)=2,\quad\gamma(3,1)=2,\quad\gamma(4)=1.$$ Then, a permutation is even if $n-\gamma(a)$ is even. So, the even permutations are the ones of cycle type $(1,1,1,1)$, $(2,2)$, $(3,1)$. This gives us a total of twelve even permutations, namely $$\{\operatorname{id}, (1\ 2)(3\ 4), (1\ 3)(2 \ 4),\ (1\ 4)(2\ 3),(1\ 2\ 3),\ (1\ 2\ 4), (1\ 3\ 4), (2\ 3\ 4),\ (1\ 3\ 2),\ (1\ 4\ 2),\ (1\ 4\ 3), (2\ 4\ 3)\},$$ with the other twelve permutations being odd.

In general, there are $n!/2$ even and odd permutations in $\mathcal{S}_n$.

• I don't think anymore answers are required now. That was a great and complete answer and cleared all of my remaining doubts thank you so much – Ankit Kumar May 6 '18 at 5:27
• Isnt Id permutation and $(1,2,3,4)$ same? – Ankit Kumar May 6 '18 at 7:58
• The identity permutation is $(1)(2)(3)(4)$, so a bit of a difference to $(1\ 2\ 3\ 4)$. The three permutations you mention are equivalent to the ones you propose that they should be. – thesmallprint May 6 '18 at 8:37
• Think about what $(2\ 4\ 3\ 1)$ does. It sends $2$ to $4$, $4$ to $3$, $3$ to $1$ and then $1$ to $2$. Now consider $(1\ 2\ 4\ 3)$. If you write out a similar path to the one I did for the previous one, you'll find it follows the same one just in a different order. So these two permutations are the same. – thesmallprint May 6 '18 at 8:50
• Yes, brilliant. No problem. Now, do you fancy trying the same thing for $\{1,2,3,4,5\}$? Instead of writing out all $120$ elements; instead feel free to tell me the cycle types that will result in even permutations if you wish. – thesmallprint May 6 '18 at 9:00

Don't be put off! You have made a very simple mistake which might be easily rectified.

I haven't checked your list for completeness, but I suspect it does include all the permutations, you've just mixed up two different notations.

I assume for example that in the list $(4,2,3,1)$ is the permutation mapping $1\mapsto 4$, $2\mapsto 2$, $3\mapsto 3$, $4\mapsto 1$? The usual (or cycle) notation for this would be $(1,4)$, an odd permutation.

As you have written $(2,3,1,4)$, would usually be written $(1,2,3)=(1,2)(1,3)$ (or $(1,3)(1,2)$ depending on the convention you use), an even permutation.

See this wiki page for a brief description of the cycle notation.

As for how many are even and how many are odd, you must have proven that a cycle is either even or odd, not both. So if $x$ is an odd permutation, then it is the product of an odd number of transpositions, so $(1,2)x$ is a product of an even number of transpositions so is even. This map $x\mapsto (1,2)x$ is a bijection between the set of odd and the set of even permutations. What does this tell you about how much there must be of each?

• That was really helpul. Thank you so much for clearing my doubt. As you have written "(2,3,1,4) is usually written as (1,2,3)" tha means it is not necessary to write the no. of which is mapped to itself ? Like (2,1,3,4) can be written as just (1,2) and (3,2,1,4) as (1,3) ? Did i get this write? – Ankit Kumar May 6 '18 at 5:12
• It's more that what you wrote is different notation, but yes the two you wrote in the comment are correct. Normally people leave out numbers mapped to themselves, of you want to include them you do things like $(1,2)=(1,2)(3)(4)$. In cycle notation $(2,3,1,4)$ would mean $4$ maps to $2$. I just guessed from your list you meant something different – Robert Chamberlain May 6 '18 at 5:54