3
$\begingroup$

Here is the question:

How many ways are there to distribute 8 objects into 9 boxes (each box can contain more than one object) if both the objects and the boxes are indistinguishable?

I've looked at using partitions, but I don't really understand it, or if it can be applied to a situation where there are less objects than boxes. I would greatly appreciate any help.

Thanks.

$\endgroup$
4
$\begingroup$

OK, so I found a useful resource that helped me understand (I think) how to apply the idea of partitioning to this problem.

Before starting, I should say that we will assume each box can contain all 8 objects, no objects, or any integer in between. Other answers may use other assumptions.

Basically:

Definition: P(k, i) is the number of partitions of k into i parts.

In this case P(8,i), where i $\leq 8$.

P(k) is the number of partitions of k into any number of parts.

In this case we want P(8).

So we need to enumerate all the possible combinations:

P(8,1) = 1 (i.e. 8 objects in one box, all others empty.)
P(8,2) = 4 [(6,2), (7,1), (5,3), (4,4)]
P(8,3) = 5 [(5,2,1), (3,3,2), (4,2,2), (4,3,1), (6,1,1)]
P(8,4) = 5 [(2,2,2,2), (4,2,1,1), (3,2,2,1), (5,1,1,1), (3,3,1,1)]
P(8,5) = 3 [(4,1,1,1,1), (3,2,1,1,1), (2,2,2,1,1)]
P(8,6) = 2 [(3,1,1,1,1,1), (2,2,1,1,1,1)]
P(8,7) = 1 [(2,1,1,1,1,1,1)]
P(8,8) = 1 [(1,1,1,1,1,1,1,1)]

P(8) = $\sum{P(8,i)}$ = 22

Therefore the answer is 22.

EDIT: "A recurrence relation is part(n,k) = part(n-1,k-1) + part(n-k,k)" This is from: http://2000clicks.com/mathhelp/CountingObjectsInBoxes.aspx
The site contains a link to the proof.

$\endgroup$
  • $\begingroup$ Right. With balls and boxes indistinguishable, the $9$th box is irrelevant; it's just another empty box. You didn't say *what* useful resource you found. The partition numbers are sequence [A000041](oeis.org/A000041) in the OEIS; there are Wikipedia articles on [partitions of numbers](en.wikipedia.org/wiki/Partition_(number_theory)) and [Euler's pentagonal numbers theorem](en.wikipedia.org/wiki/Pentagonal_number_theorem). You can compute numbers like $p(8)=22$ using Euler's recurrence (continued in next comment) $\endgroup$ – bof Dec 7 '14 at 20:33
  • $\begingroup$ $p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n-12)+p(n-15)-p(n-22)-\cdots=p(n-1)+p(n-2)-p(n-2-3)-p(n-3-4)+p(n-3-4-5)+p(n-4-5-6)-p(n-4-5-6-7)-p(n-5-6-7-8)+\cdots$ $\endgroup$ – bof Dec 7 '14 at 20:37
  • $\begingroup$ Thanks, the resource is mentioned in a comment of the question. Here's the link:people.qc.cuny.edu/faculty/christopher.hanusa/courses/636fa12/… $\endgroup$ – JC2188 Dec 7 '14 at 21:01
3
$\begingroup$

If the boxes are indistinguishable and can be rearranged as well at will, then it becomes the same question as "How many monotonic decreasing sequences of natural numbers exist where the sum is equal to 8?"

By brute force, here are the possible sequences.

(8,0,...),(7,1,0,...),(6,2,0,...),(6,1,1,0,...),(5,3,0,...),(5,2,1,0,...)(5,1,1,1,0,...),(4,4,0,...),(4,3,1,0...),(4,2,2,0,...),(4,2,1,1,0,...),(4,1,1,1,1,0,...),(3,3,2,0,...),(3,3,1,1,0,...),(3,2,2,1,0,...),(3,2,1,1,1,0,...),(3,1,1,1,1,1,0,...),(2,2,2,2,0,...),(2,2,2,1,1,0,...),(2,2,1,1,1,1,0,...),(2,1,1,1,1,1,1,0,...),(1,1,1,1,1,1,1,1,0,...)

As you can see, there are 22 of them. I'm not sure how to generalize this result at the moment, perhaps someone who is more familiar with the problem will come around with a counting method. Perhaps a recurrence relation.

Looking for a pattern at the sequence of numbers for this problem with 1,2,3,... number of objects: I get the amounts: 1,2,3,5,7,11,15,22.

By google searching I find http://mathworld.wolfram.com/PartitionFunctionP.html which has a great deal of history about the problem and methods of calculating the sequence.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.