189 views

How many ways are there to distribute five balls into three boxes if each box must have at least one ball in it if

1. both the balls and boxes are labeled?
2. the balls are labeled, but the boxes are unlabeled?
3. the balls are unlabeled, but the boxes are labeled?
4. both the balls and boxes are unlabeled?

Here, it is said that there is at least one ball in each box, thus, there can be only two combinations possible –  (3.1.1) or (1,2,2).

1. for the first combination (3.1.1), there are $\binom{5}{3}$ ways to chose 3 balls, then 3 ways to put these 3 balls into one box. for the remaining balls, there are 2 ways for the 4th ball and 1 way for the last ball. Applying product rule, we get $\binom{5}{3}$ *3 *2 = 60 ways

for the second combination (1,2,2), there are 3 ways to choose the box containing the lonely ball and 5 ways to choose which ball will be the unlucky one.  For the remaining balls, there are $\binom{4}{2}$* $\binom{2}{2}$ ways. Applying product rule we get 3*5*$\binom{4}{2}$ * $\binom{2}{2}$ = 90 ways.

Applying sum rule(because there are two alternatives), we get 60+90 = 150 ways.

2. This is similar to the Integer composition problem. We need to find the number of compositions of 8 into 3 parts.

The first is (1.1.3) which can be done in $\binom{5}{3}$ = 10 ways.

for the second composition, that is (1,2,2), we csn do it in ($\binom{5}{2}$ * $\binom{4}{2}$) / 2 = 15 ways.

Applying Sum rule, we get, 10+15 = 25 ways.
1. This is a Stars and Bars Probelm, a very common and very important IODB template. There are 3-1=2 bars and 2 stars. (there is one ball each in the boxes already, thus 5-3 = 2). To put the 2 balls, there are 4C2 or 6 ways.
1. This is the Integer Partition Problem. We need to find the number of partions of 5 into 3 parts. And as we have already seen, there 2 partitions. 1+1+3 and 1+2+2. Thus, there are only 2 ways.

1
157 views