We went over distinguishable combinatorics already. Now, let’s work through some harder, indistinguishable combinatorics problems.

• I have 4 identical balls and 4 distinguishable bins. How many ways can I put the balls in the bins so that every ball is inside a bin?

Since the balls are identical, this problem is more complicated. If all of the balls were distinguishable, we could have chosen one of the 4 bins for each ball, and the answer would have been 4 x 4 x 4 x 4.

However, the balls are identical, which makes this problem more complicated. When the bins are distinguishable and the balls are identical, we can use the stars and bars method.

For this method, we can draw 4 circles (representing the balls) and 3 vertical lines. All of the balls in front of the first vertical line represent the first bin, the balls between the first and second lines represent the second bin, etc.

Now, we need to see how many ways we can arrange the balls and bins. In total, there are seven objects. We can leave the balls and choose the positions of the three vertical lines. Thus, this becomes 7 C 3, which equals 35. This is our final answer.

Note that there are multiple arrangements of the same pattern. For example, in the 4, 0, 0, 0 pattern, the 4 balls can be in any of the 4 gaps (bins).

• I have 4 identical balls and 4 identical bins. How many ways can I put the balls in the bins so that every ball is inside a bin?

This problem is a little different. Notice that both the balls and the bins are identical. Now, we need to use casework to solve this problem. When both the balls and the bins are identical, the only things that distinguish orderings are the sizes of the groups of balls.

Case 1: 4 balls in one bin.

Case 2: 3 balls in one bin and 1 ball in another.

Case 3: 2 balls in one bin and 1 ball in each of 2 bins.

Case 4: 2 balls in one bin and 2 balls in another.

Case 5: 1 ball in each bin.

Notice that there is only one way to place the balls for each case since everything is identical. So, the answer is 5.

• I have 4 distinguishable balls and 4 identical bins. How many ways can I put the balls in the bins so that every ball is inside a bin?

For this problem, we can use the 5 cases from the previous problem. In the first case, the four balls can go into any of the four bins. However, since all of the bins are identical, this does not matter. Thus, there is 1 possibility for this case.

For the next case, there are 4 ways to choose the 1 ball that does not go with the rest. The rest of the balls will go together. So, there are 4 possibilities for this case.

For case 3, there are 4 C 2 ways to choose the 2 balls that go together. The other two balls must be in separate bins. So, there are 6 possibilities for this case.

For case 4, there are again 4 C 2 ways to choose the 2 balls that go together. However, the other group of 2 balls also goes together. So, we are actually double-counting the number of possibilities for this case. For example, if we chose balls 1 and 2 to go in a group, this would be the same as choosing balls 3 and 4 to go in a group since balls 1 and 2 would still be together. Thus, we have 6 / 2 possibilities for this case, which is 3.

For the final case, each of the balls must be independent. There is only 1 way to do this. So, our final answer is 1 + 4 + 6 + 3 + 1, which equals 15.