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$
1
  • $\begingroup$ $D_5$ is rather small, so you are claiming that almost every permutation qualifies. That is clearly not the case. $\endgroup$ Jul 16, 2017 at 17:12

1 Answer 1

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$
6
  • $\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$ Jul 16, 2017 at 17:14
  • $\begingroup$ Yes, that is right. $\endgroup$ Jul 16, 2017 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$ Jul 16, 2017 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$ Jul 16, 2017 at 17:32
  • $\begingroup$ the answer was actually 9 choose 5 * 9 $\endgroup$ Jul 18, 2017 at 22:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .