0
$\begingroup$

How many permutations of [9] are there in which exactly 5 numbers are in their original position?

My professor does not mean equivalence class, she means the set of positive integers less than or equal to 9: so {${1,2,3,4,5,6,7,8,9}$}.

This looks like a derangement problem. So my first intuition is to count the number of possible permutations of all 9 numbers, which is simply $9!$, then subtract the number of derangements which would be $D_5$. So my answer would be $9!-D_5$.

Am I thinking of this the correct way? What's a better way of going about solving problems like this Any tips?

$\endgroup$
  • $\begingroup$ $D_5$ is rather small, so you are claiming that almost every permutation qualifies. That is clearly not the case. $\endgroup$ – Ross Millikan Jul 16 '17 at 17:12
3
$\begingroup$

Hint: First choose the five numbers which will be in their original positions. How many ways to do that? Then you need a derangement of the remaining four. How many of those are there?

$\endgroup$
  • $\begingroup$ So, let's suppose all the odd numbers stay in their original position. There's only one way to do that. That means, we need to derange the remaining 4. So there are 9 derangements total for those 4 numbers ($D_4$)? $\endgroup$ – John Locke Jul 16 '17 at 17:14
  • $\begingroup$ Yes, that is right. $\endgroup$ – Ross Millikan Jul 16 '17 at 17:16
  • $\begingroup$ Cool that makes sense. When do we use complementary counting, to subtract $D_4$ from $9!$? Because the answer to this problem is just $D_4$? $\endgroup$ – John Locke Jul 16 '17 at 17:29
  • $\begingroup$ No, you need to multiply by the number of ways to choose the fixed ones. You use complementary counting when it is the easiest way to the answer $\endgroup$ – Ross Millikan Jul 16 '17 at 17:32
  • $\begingroup$ the answer was actually 9 choose 5 * 9 $\endgroup$ – John Locke Jul 18 '17 at 22:32

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.