0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ That depends greatly on what sort of objects you are wanting to count. The answer depends heavily on interpretation of the problem and the way it is written currently it sounds ambiguous to me. Notice, $\binom{2n}{n}n!n! = (2n)!$. Your count includes things like $(12,34)$ and $(34,12)$ and treats these as separate outcomes. The TA was interpreting the problem as counting things like $\{12,34\}$ which would have been treated as the same result as $\{34,12\}$ while your interpretation treats these as different. $\endgroup$ – JMoravitz Dec 10 '19 at 20:51
  • $\begingroup$ Thank you!!! It's been bothering me for a long time. I should've asked it here earlier. $\endgroup$ – user665125 Dec 10 '19 at 20:54
  • $\begingroup$ As to which interpretation is more correct... I would have used the same interpretation as you. That we pick $n$ of the elements, permute them, then permute the remaining $n$ elements, and concatenate the two together. In doing so, we in fact generate all possible $(2n)!$ permutations of the $2n$ numbers had we done so directly rather than indirectly. Using your TA's interpretation, it is unclear which permutation we should get, $1234$ or $3412$ given the $\{12,34\}$ object that he counted earlier. You could come up with an arbitrary rule, such as whichever has earlier start goes first... $\endgroup$ – JMoravitz Dec 10 '19 at 20:57
  • $\begingroup$ ...in which case we missed half of the permutations of $2n$, namely all of those permutations where the first position is larger than the $n+1$'st position. $\endgroup$ – JMoravitz Dec 10 '19 at 20:58
  • $\begingroup$ Something is fishy here. If we define a permutation as simply a sequence containing all the numbers, as JMoravitz has done above, then as he mentions you'd need to have a rule to recombine them. For any given rule, your answer would be the correct one. If instead we define a permutation as a bijective function from the set to itself, then you are more than just double-counting. For instance you count the identity permutation $\binom{2n}{n}$ times. Either way, I don't see your TA's solution as being right. $\endgroup$ – Brian Moehring Dec 10 '19 at 21:18
0
$\begingroup$

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.

$\endgroup$

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.