How many permutations of 2n numbers can you generate in the following way; Choose n numbers and permute them and the permute the other n. Characterize the permutations which can not be generated this way.
This is what I get ${2n \choose n}n!n!$, but the solution says it still needs to be divided by half. The TA said it is because if we swap the ordering of choosing the first n number and the rest n numbers, we get the same permutation. I still don't get it.
If we have this set {1, 2, 3, 4}, what permutations could we get?
Thanks
Start by splitting the set $\{ 1,2 \cdots 2n \}$ into $2$ sets of size $n$, say $\{a_1, \cdots , a_n \}$ and $\{b_1, \cdots , b_n \}$. Note that we could swap all the $a'$s with all the $b'$s and get exactly the same split, this is where the factor of $2$ comes from.