[Math] Counting Problem: How many ways are there to distribute 8 objects into 9 boxes if the objects and the boxes are indistinguishable

combinatorics

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.

Best Answer

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.