Simple (not for me) combinatorics question

There are four balls of different colors, and four boxes of colors, same as those of the balls.What are the number of ways, in which, the balls, one each in a box, could be placed, such that a ball does not go to a box of its own color.

I name the balls A,B,C,D. Correspondingly, I name the boxes A,B,C,D.

(i) Now starting with ball A, I could select one of the boxes B,C,D in 3 different ways. (ii) Let, I put ball A in box B. (iii) Moving onto ball B, I could select one of A,C,D in 3 different ways. (iv) Let, I put ball B in box C. (v) As, no ball goes into corresponding box, ball C must be put in box D, ball D must be put in box A. Number of ways to do this is 1

So, total no. of ways=3 x 3 x 1 = 9

9 is the answer given in my book (not the process, this is an exercise problem, even no hints given).

But now, consider the following case (i) Starting with ball A, I could select one of the boxes B,C,D in 3 different ways. (ii) Let, I put ball A in box B. (iii) Moving onto ball C, I could select one of A,D in 2 different ways (as ball C cannot go to box C). (iv) Let, I put ball C in box D. (v) Then I select ball B; it could be put in either of the boxes A,C in 2 different ways. Let it be C. (vi) Lastly, ball D could be put in box A, in only 1 way.

So, total no. of ways=3 x 2 x 2 x 1 = 12

Two different answers---something (I don't know what) should be wrong in the second solution.

What you're looking for is called a derangement. There exists a general formula for derangement of $n$ objects. Here's how you get it:

First determine all the possibilities. In this case, $$T=n!$$ Now determine how many choices have atleast $1$ object going into its designated spot. It's $${n \choose 1}(n-1)!$$ Now subtract this number from $T$. But you have taken away some cases twice, the cases in which atleast $2$ objects get their spot. So you have to add that number to compensate. You have to add $${n \choose 2}(n-2)!$$ But again, you have overadded the cases in which $3$ objects get their spots. So you again subtract $${n \choose 3}(n-3)!$$ and go on and on. What you eventually end up with is $$P=T-\left({n \choose1}(n-1)! - {n \choose 2}(n-2)! \cdots (-1)^{n+1} {n \choose n}0! \right)$$ If you have trouble imagining the overcompensation like I did, try drawing a venn diagram. Evaluating the expression for $n=4$, you do get the $9$.

Both methods are wrong. You should simply list out all the solutions (there are so few!) and see which of your steps break down or cannot be justified. The correct solution that generalizes to many boxes and many balls will require the inclusion-exclusion principle, but I think that is really beyond you now.

• not really beyond----I had figured out the solution, but as I pondered more over the problem---a sort of confusion disturbed my thinking---and that is why I have posted this question. Jun 1 '14 at 14:36
• @abstract: Oh okay sure. Just remember that whenever you count "number of ways", make sure there really is a bijection between the original set (of solutions) and the new set (of choices), then such mistakes will not be made. Jun 1 '14 at 14:39
• it is then 4!-1-(4C1 X 2)-(4C2 X 1)-(4C3 X 0) =9 Jun 1 '14 at 14:57
• @abstract: I don't see where you got your answer from. What do you get for $5$ boxes and $5$ balls? Jun 1 '14 at 15:10
• 5!-1-(5C1*9)-(5C2*2)-(5C3*1)-(5C4*0)=120-1-45-20-10-0=44 Jun 1 '14 at 16:32

Your first method is not too far off, but it's not right at the moment.

There are three boxes we could put A in, and they're all equivalent. Let's say we choose B.

Now there are three boxes we can put B in, but they're not all equivalent. We can either put it in box A, or one of the others (say C). If we put B in A, there is only one possibility for the rest (C must go in D and vice versa). If we put B in C, there is again only one possibility for the rest (D must go in A, and so C must go in D).

This gives the answer as $3\times(1\times 1+2\times 1)=9$. However, the fact that we get the same number of possibilities no matter where we put B is just a fluke, and doesn't happen for larger numbers of objects.

Generalising this approach can give you the recurrence relation $D_n=(n-1)(D_{n-2}+D_{n-1})$.