# Kenneth Rosen-Combinatorics-Exercise for section 5.5

For this question:

There are $$5$$ balls and $$3$$ boxes. Find the number of ways to distribute the balls in the boxes for the given $$4$$ cases.

1>box and the balls are labelled:

Then we get $$3^5$$ cases

2>balls labelled but boxes are unlabelled:

$$5c5 + 5c4 + 5c3 \cdot 2 + 5c2 \cdot 3c3 + 5c2 \cdot 3c2 + 5c1 \cdot 4c3$$

$$5c5 =$$ we choose $$5$$ balls and we only consider placing it in $$1$$ of the $$3$$ envelops as all envelopes are the same.

$$5c4=$$ we choose $$4$$ balls and the one ball could be placed in any other envelope

$$5c3 \cdot 2=$$ we choose $$3$$ balls and the $$2$$ other cases correspond to placing the remaining $$2$$ balls in $$1$$ envelope or placing them in $$2$$ different envelops.

$$5c2 \cdot 3c3 + 5c2 \cdot 3c2 =$$ choosing $$2$$ balls and placing the remaining $$3$$ in the same envelope or placing the remaining $$2$$ of $$3$$ balls in one envelope and the last one in $$1$$ envelope

$$5c1 \cdot 4c3 =$$ choosing $$1$$ out of $$5$$ and placing the remaining $$4$$ balls in $$1$$ envelope.

3>balls unlabelled boxes labelled

Using counting sticks approach: $$7C2$$

4>balls unlabelled and boxes unlabelled:

$$5$$ ways (found out by writing all cases in pen and paper as there is no specific way to find it)

Your answers for the first, third, and fourth questions are correct. With regard to the fourth question, it is correct since there are five partitions of $$5$$ into at most three parts. They are \begin{align*} 5 & = 5\\ & = 4 + 1\\ & = 3 + 2\\ & = 3 + 1 + 1\\ & = 2 + 2 + 1 \end{align*}

As for placing labeled balls in unlabeled boxes, we consider the five cases that correspond to those partitions.

Five balls are placed in one box: This can be done in one way.

Four balls are placed in one box and the other ball is placed in another box: This can be done in $$\binom{5}{4}$$ ways since this distribution is completely determined by choosing which four balls are placed together.

Three balls are placed in one box and the other two balls are placed in another box: This can be done in $$\binom{5}{3}$$ ways since this distribution is completely determined by choosing which three balls are placed together.

Three balls are placed in one box with one ball each placed in each of the remaining boxes: This can also be done in $$\binom{5}{3}$$ ways since this distribution completely determined by choosing which three balls are placed together since the two boxes that each receive one ball are indistinguishable.

Two balls are placed in one box, two other balls are placed in a second box, and the remaining ball is placed in the remaining box: There are $$\binom{5}{1}$$ ways to choose which ball is placed in a box by itself. Place one of the remaining four balls in a box. There are $$\binom{3}{1}$$ ways to choose which of the remaining three balls is placed in the same box as that ball. The other two balls must be placed in the remaining box. Hence, there are $$\binom{5}{1}\binom{3}{1}$$ such distributions.

Total: There are $$\binom{5}{5} + \binom{5}{4} + \binom{5}{3} + \binom{5}{3} + \binom{5}{1}\binom{3}{1}$$ ways to distribute $$5$$ distinguishable balls into three indistinguishable boxes.

What mistakes did you make?

Notice that placing four balls in one box and one in another is the same as placing one ball in one box and four in another, so your final (incorrect) term is superfluous.

Similarly, placing three balls in one box and two in another is the same as placing two balls in one box and three in another, so you counted this case twice.

Finally, in the $$2 + 2 + 1$$ case, suppose that the balls are blue, red, green, yellow, and magenta (and that the reader can distinguish between these colors). Since the boxes are indistinguishable, the distribution

$$\{\text{blue, red}\}, \{\text{green, yellow}\}, \{\text{magenta}\}$$

is the same as the distribution

$$\{\text{green, yellow}\}, \{\text{blue, red}\}, \{\text{magenta}\}$$

so you have counted each such distribution twice.

Suppose, as in this example, that the magenta ball is in its own box. Then the other four balls can be placed in three distinguishable ways, depending on which color ball is placed in the same box as the blue ball.

$$\{\text{blue, red}\}, \{\text{green, yellow}\}, \{\text{magenta}\}$$

$$\{\text{blue, green}\}, \{\text{red, yellow}\}, \{\text{magenta}\}$$

$$\{\text{blue, yellow}\}, \{\text{green, red}\}, \{\text{magenta}\}$$

By symmetry, for each of the five ways we can choose which color ball is placed in its own box, there are three distinguishable ways to place the remaining four balls in the remaining two boxes so that there are two balls in each box. Hence, there are $$5 \cdot 3 = 15$$ such distributions.

• I have this question: that for questions asking for the number of ways to place certainitems(distinguishable./indistinguishable) in boxes(distinguishable./indistinguishable) we don't have permutations or combinations we are only required to find the ways of placing them? – Diya Jun 17 at 6:53
• We have 3 chocolates(unlabelled) and 2 envelops(labelled) the no. of ways to distribute it is 4C1 CONSIDER THE CASE:I put 3 chocolates in E1 and 2 in E2 now I can put it in many ways.. 1>put 1 chocloate in e1,then put 1 chocolate in e2,put 1 chocolate in e1,put 1 chocolate in e2,put 1 cholotae in e1 2>put 1 chocloate in e2,then put 1 chocolate in e1,put 1 chocolate in e2,put 1 chocolate in e1,put 1 cholotae in e1 3>put 1 chocloate in e2,then put 1 chocolate in e2,put 1 chocolate in e1,put 1 chocolate in e1,put 1 chocolate in e1. Aren't these cases giving us the number of permutations? – Diya Jun 17 at 7:07
• We are trying to count the distinguishable ways of placing the objects in boxes. For the case of placing $3$ indistinguishable chocolates in $2$ envelopes, what matters is how many chocolates are placed in each envelope. If the envelopes were also indistinguishable, we could partition the chocolates in two ways: $3 + 0$ and $2 + 1$. Since the envelopes are distinguishable, we have to double this count since we permute the two envelopes. That said, placing indistinguishable objects in distinguishable boxes is a combination with repetition problem. – N. F. Taussig Jun 17 at 8:47