1
$\begingroup$

Suppose you have n bins numbered from 1 to n, and suppose $n\ge4$.

bin 1, bin 2, bin 3, bin 4, bin 5, ... , bin n

Then you place the numbers 1 through n into the bins, using each number exactly once.

If the number 3 goes into bin 3, then we say "3 is in its own bin."

1) How many ways are there to put at least 1 integer not in its own bin?

2) How many ways are there to put at least 2 integers not in their own bins?

There's no way to put exactly 1 integer not in its own bin, because you have to displace at least two integers at a time. So, the answer for 1) and 2) is the same. There are $n!$ arrangements of integers into bins, and only 1 way that has every integer in its own bin.

Therefore, the answer is $n!-1$.

But then...

3) At least 3 integers not in their own bins?

4) At least 4 integers not in their own bins?

How can I approach these two parts? I was thinking about using a sum: find the number of ways to choose k integers, then multiply that by the number of ways to completely rearrange k elements (such that none go back into their original places). Then do a sum for all values of k from 3 to n, and from 4 to n. But "completely rearranging" k elements is not an easy problem, I found out this is called "derangements" and the formula is very weird, and there's probably a simpler way.

Any help is appreciated. Thanks!

$\endgroup$
  • $\begingroup$ When we ask how many permutations have exactly (say) $k$ fixed points, the counts are called rencontres numbers. $\endgroup$ – hardmath Jan 11 '16 at 0:48
0
$\begingroup$

I don't think that there is a simple method in general, but I can come up with some answers for $3$ and $4$. The statement "at least 3 not in their own bins" is the opposite of "exactly 0, 1, or 2 not in their own bins," so we just need to count these. As you already noted, there is exactly one permutation with exactly $0$ not in its own bins, and there are no permutations with exactly $1$ not in its own bin. Considering $2$ not in their own bins, we select two bins to swap with each other, so there are $\binom{n}{2}$ ways to do this. Thus for $3$ the answer is $n!-1-\binom{n}{2}$.

For $4$, we must now count the number of ways to put $3$ not in their own bins. To do this, we must select $3$ bins to swap (circularly) with each other. There are two ways to swap and $\binom{n}{3}$ ways to select these bins, so the answer is now $n!-1-\binom{n}{2}-2\binom{n}{3}$.

The two came from the number of derrangments, so without using that formula, it would be difficult to create a general formula.

$\endgroup$
  • $\begingroup$ Thanks, that's very clear :) $\endgroup$ – user19650 Jan 11 '16 at 0:35

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.