Problem: How many ways are there to distribute five indistinguishable objects into three indistinguishable boxes? (Discrete Mathematics and Its Applications, Sixth Edition by Kenneth H. Rosen - Section 5.5, Problem #54)
Solution: There is likely a fancy formula for doing this, and the formula likely can be extended to count the number of arrangements in n indistinguishable objects into m boxes. Being lazy and not wanting to count the ways to do this, I looked for such a formula. However, finding this solution proved to be difficult. So, instead, I came up with the next best thing: an algorithm to count them, so that the computer (and not me) can do all the work, while I still enjoy the credit for doing the problem.
Let's work in general with n indistinguishable objects in m boxes first. Start by assuming that the m boxes are distinct. We can create an m-tuple that would represent the boxes:
$ [n_1, n_2, ..., n_m] $, where $ n_1 $ is the number of objects in box 1, $ n_2 $ is the number of objects in box 2, etc. In addition, we require that $ n_1 + n_2 + ... + n_m = n $.
However, as we know, the boxes are indistinguishable. For instance, $ [n_1, n_2, n_3, n_4, ..., n_m] = [n_2, n_1, n_3, n_4, ..., n_m] $. (For the purpose of this exercise, we will call these two m-tuples equivalent.) So, we need to find a way to express each possible m-tuple and its equivalents exactly once.
One solution is to require that $ n_1 \leq n_2 \leq ... \leq n_m $. The reasoning behind this is that each possible m-tuple has some number of inversions, but all m-tuples can be rearranged to have no inversions. Additionally, there is only one distinguishable way to write a 0-inversion m-tuple with given elements. Thus, all equivalent m-tuples can be rearranged and will be grouped under the one, 0-inversion equivalent of them. Counting these 0-inversion m-tuples up will then give us the answer we are looking for.
So, we need an algorithm to write all possible non-invertible m-tuples. The following is one solution:
- 1. Start by assigning $ n_m = n $, and all other values as 0. This will produce one m-tuple.
- 2. Form a new m-tuple from the previous one by decreasing $ n_m $ by 1 and increasing $ n_{m-1} $ by 1. Repeat this step as long as $ n_{m-1} \leq n_m $. (So that the m-tuple remains non-inverted)
- 3. Now, form a new m-tuple by setting $ n_{m-2} = 1, n_{m-1} = 1, n_m = n-2 $. Repeat step 2. Then, increase $ n_{m-2} $ and $ n_{m-1} $ by 1. Set $ n_m = n - n_{m-1} - n_{m-2} $ and repeat step 2. Continue with this pattern, and repeat so long as $ n_{m-2} \leq n_{m-1} \leq n_m $.
- 4. Continue with the pattern established, extending non-zero values to $ n_{m-3}, n_{m-4}, ..., n_2, n_1 $.
Doing this for 5 indistinguishable objects in 3 indistinguishable boxes would generate the 3-tuples in this order, which turned out quite simple to do by hand:
[0,0,5]
[0,1,4]
[0,2,3]
[1,1,3]
[1,2,2]
Counting the 3-tuples up, we discover that there are 5. That is, there are 5 different ways of arranging 5 indistinguishable objects into 3 indistinguishable boxes.
Thomas34 21:10, 23 September 2008 (UTC)
Week 6 - comments
Thumbs up! The most comprehensive solution to this problem in Rhea so far!
--Asuleime 12:40, 30 September 2008 (UTC)
