Q: How many ways are there to distribute 5 indistinguishable objects into 3 indistinguishable boxes?
A: Suppose you have 5 identical white cue balls and 3 identical black bags. We want to find all of the possible unique combinations of the 5 white cue balls in the three black bags (keeping in mind that we can't distinguish one ball from another, nor one bag from another).
Idea: We can place different amounts of balls in a bag, and look at the possible contents of the other 2 bags.
a) 0 balls in first bag. Possibilities for the other two bags: (5,0) (4,1) (3,2) (2,3) (1,4) (0,5)
- Looking at our possibilities for our other two bags, since they are indistinguishable, the options (3,2) and (2,3) are one and the same. This also follows for (4,1) and (1,4) and also (0,5) and (5,0). These repetitions do occur in most of the other cases, but I'll leave them out as possible combinations since they are really just repeats of a previous combination.
b) 1 ball in first bag. Possibilities for the other two bags: (4,0) (3,1) (2,2)
c) 2 balls in first bag. Possibilities for the other two bags: (3,0) (2,1)
d) 3 balls in first bag. Possibilities for the other two bags: (2,0) (1,1)
e) 4 balls in first bag. Possibilities for the other two bags: (1,0)
f) 5 balls in first bag. Possibilities for the other two bags: (0,0)
Now, putting the number of balls in our first bag together with the corresponding possibilities for the other two bags, we will get all of the possible combinations.
a) (0,5,0) (0,4,1) (0,3,2)
b) (1,4,0) (1,3,1) (1,2,2)
c) (2,3,0) (2,2,1)
d) (3,2,0) (3,1,1)
e) (4,1,0)
f) (5,0,0)
Once again, we must remember that the bags are indistinguishable! This means that the possible combination (0,5,0) is the same as the combination (5,0,0). So, looking at our list, we see there are only 5 possible unique combinations after grouping like cases and counting the total number of groups.
1. (0,5,0) (5,0,0)
2. (0,4,1) (1,4,0) (4,1,0)
3. (0,3,2) (2,3,0) (3,2,0)
4. (1,3,1) (3,1,1)
5. (1,2,2) (2,2,1)
aoser@purdue.edu
--Aoser 19:30, 24 September 2008 (UTC)