2
$\begingroup$

Let's suppose I have 3 balls numbered 1 to 3 and 3 boxes numbered 1 to 3. I have here a case where I need to put 3 distinguishable balls into 3 distinguishable boxes.

I know that I can count how many ways I can place these balls into the boxes by computing $3^3 = 27$ ways.

Here are all possible combinations:

+-------+-------+-------+
| Box1  | Box2  | Box3  |
+-------+-------+-------+
| 1,2,3 |     0 |     0 |
|     0 | 1,2,3 |     0 |
|     0 |     0 | 1,2,3 |
|     1 |   1,2 |     0 |
|     1 |     0 |   1,2 |
|     2 |   1,3 |     0 |
|     2 |     0 |   1,3 |
|     3 |   1,2 |     0 |
|     3 |     0 |   1,2 |
|   2,3 |     1 |     0 |
|     0 |     1 |   2,3 |
|   1,3 |     2 |     0 |
|     0 |     2 |   1,3 |
|   1,2 |     3 |     0 |
|     0 |     3 |   1,2 |
|   2,3 |     0 |     1 |
|     0 |   2,3 |     1 |
|   1,3 |     0 |     2 |
|     0 |   1,3 |     2 |
|   1,2 |     0 |     3 |
|     0 |   1,2 |     3 |
|     1 |     2 |     3 |
|     1 |     3 |     2 |
|     2 |     1 |     3 |
|     2 |     3 |     1 |
|     3 |     1 |     2 |
|     3 |     2 |     1 |
+-------+-------+-------+

I'm trying to restrict now all cases where a given box has only one given ball. For instance: box1 (ball1), box2(ball2,ball3), box3(0) ; box1 (0), box2(ball2,ball3), box3(ball1), etc.

My try: I have ${3}\choose{1}$ ways to select the box and ${3}\choose{1}$ to select the ball. After this, I have 2 boxes and 2 balls left. The number of ways to distribute these balls into the boxes is $2^2 = 4$ ways. So:

${3}\choose{1}$ ${3}\choose{1}$ 4 = 36.

Naturally, there is a problem with my analysis, since this number should be 24. What am I doing wrong? Any help is appreciated.

$\endgroup$
2
$\begingroup$

Specifically, in your original 27 row table, your method counts the bottom 6 rows 18 times instead of 6 times, giving you a surplus of 12.

For example, on the final row, your method of $ {3\choose1} {3\choose1}2^2$ will return a set of Box1/3, Box2/2, Box3/1 a total of three times. Instead of the single time it can actually happen.

In response to your comment, there are multiple ways to create an adapted formula. One way would be "Count of times a single box has a single ball and the other two balls are in the same box PLUS the number of ways to arrange a single ball in each box". (There is no situation where only two boxes get a single ball.) So I would say $${3\choose1}{3\choose1}{2\choose1} + 3!\\18+6 $$

$\endgroup$
  • $\begingroup$ I see, how can I adapt it to not account the duplicated values? Thank you. $\endgroup$ – Rodrigo Teles May 23 at 14:16
1
$\begingroup$

You overcount.

Say you want to put ball $b_i$ into box $B_i$. Then you count this... 3 times:

$\binom{3}{1}$ ways of choosing a ball, so say we choose ball 1 and put it in box 1. Then 1 way to fill in the rest.

$\binom{3}{1}$ ways of choosing a ball, so say we choose ball 2 and put it in box 2. Then 1 way to fill in the rest.

$\binom{3}{1}$ ways of choosing a ball, so say we choose ball 3 and put it in box 3. Then 3 way to fill in the rest.

Thus you counted this combination 3 times in total, not once, and hence you overcounted.

$\endgroup$

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.