Q: How many ways are there to distribute 5 indistinguishable objects into 3 indistinguishable boxes?
A:
Well, first of all, each possible distribution can be represented by a set of three numbers {x,y,z} where x=objects in box 1, y=objects in box 2, z=objects in box 3 and x+y+z=5. We must also take into account that, because the boxes are indistinguishable, {2,2,1} is the same distribution as {1,2,2}. To avoid double counting, we will stipulate that x >= y >= z.
To count each possibility, we will go through and try each possible x, then y, then z.
1) Put 5 balls in x. If we do this, we have 0 remaining. {5,0,0}.
2) Put 4 balls in x. After this, we have 1 remaining, and because of our ordering principle, we must put that ball in y. {4,1,1}.
3) Put 3 balls in x. We have two remaining, and we can either split them between y and z, or put both in y. {3,1,1}, {3,2,0}.
4) Put 2 balls in x. We could put the remaining three in y, but that would violate or ordering principle. We could put 1 in y, but then z > y. So we must put 2 in y, and the last in z. {2,2,1}.
5) Put 1 ball in x. This meaning that 1 >= y and 1 >= z. Which gives a maximum of three balls. Therefore there are zero ways with x = 1.
6) Put 0 balls in x. Because of our ordering principle there are zero ways with x = 0.
Therefore, the possible distributions are:
{5,0,0} {4,1,0} {3,1,1} {3,2,0} {2,2,1}
So the answer is 5.
- --Nclaus 12:13, 5 October 2008 (UTC)
