# Ways to put at least 1, 2, 3, or 4 numbers into the wrong-numbered bins

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!

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

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}$.