Difference between revisions of "Brian Thomas: 5.5 no 54 MA375Fall2008walther" - Rhea

Revision as of 07:31, 30 September 2008

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 03:34, 25 September 2008 (UTC)