2
$\begingroup$

In how many ways can we distribute 5 different balls into 4 different boxes, given that order does not matter inside the boxes and empty boxes are not allowed?

My attempt

First I chose $4$ balls out of $5$ and arranged them for the $4$ boxes: $\binom 54 \times 4!.$

Then for the remaining ball I can choose any of the $4$ boxes. Multiplying them, we get $480$, which is double the answer given as correct answer. Why I am wrong? And how can I solve the problem if the order matters inside the boxes?

$\endgroup$
1
  • 1
    $\begingroup$ Cases will repeat in your way.. Use inclusion-exclusion principle $\endgroup$
    – Zenix
    Mar 15, 2020 at 17:33

4 Answers 4

5
$\begingroup$

For any allowed distribution we have just one box with $2$ balls and the others with $1$ ball each. We choose such box in $4$ ways. Now multiply such number by the number of permutations of the $5$ balls, i.e. $5!$ and finally divide the result by $2$ because in the box with two balls order does not matter. Hence the result is $$\frac{4\cdot 5!}{2}=240.$$

$\endgroup$
3
$\begingroup$

With your attempt you count a disposition more than once.

Named $A,B,C,D$ the boxes and $a,b,c,d,e$ the balls you count (for example) two times the combination: $a,e\in A$, $b\in B$, $c\in C$, $d\in D$.

The first time you choose the set $\{a,b,c,d\}$, put $a\in A, b\in B, c\in C, d\in D$, then you put $e\in A$;

The second time you chose the set $\{e,b,c,d\}$, put $e\in A, b\in B, c\in C, d\in D$, then you put $a\in A$.

Since I do not see how to fix this count, I suggest another approach:

First, choose the box which will contain $2$ balls in $\binom{4}{1}$, second choose the two balls you will put in the box chosen in $\binom{5}{2}$, then choose how to put the last three balls in last three boxes in $3!$.

So the answer should be: $$\binom{4}{1} \cdot \binom{5}{2} \cdot 3! = 240$$

$\endgroup$
1
$\begingroup$

Using inclusion-exclusion principle,

$4^5 - ^4C_1 3^5 + ^4C_2 2^5 - ^4C_3 1^5$

Subtract cases when all 5 objects go in 3 boxes (exclusion) then include when objects go in 2 boxes, because they are subtracted more than the number of times such case comes. Then again exclude when all objects go in one box.

$\endgroup$
1
$\begingroup$

Two methods:

Method 1: There is only one case possible 2,1,1,1

So, first we will go with unnamed distribution of 5 distinct things and then we will arrange them in 4 places.

$$\frac{5!}{(2!)(1!)^3(3!)}4!= 240$$

Method 2:

Distribution of identical objects then arranging them. Solve x+y=5 and arrange the balls in the boxes

$$=C(_{3-1}^{5-1})\frac{5!}{2!}=240$$

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