Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Could anyone please tell me if there is a way to know the number of ways to put N indistinct objects into M indistinct boxes?

I already know how to calculate the number of ways if any or both objects and boxes are distinct.

I've been trying to solve this for a while. My first idea was to consider the number of ways to put N indistinct objects in M distinct boxes, which is ${{m+n-1}\choose{n}}$. And then divide it by the number of permutations of every possible distribution, which I thought was $n!$. But it seems not every possible distribution has exactly $n!$ permutations, so this train of thought doesn't seem to work.

Any ideas? Thanks!

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

You’re looking for $P(n,k)$, the number of partitions of $n$ into $m$ parts; there is no nice closed expression for this number. Formula $(59)$ here gives the recurrence

$$P(n,m)=P(n-1,m-1)+P(n-m,m)\;.$$

This isn’t hard to derive. If a partition of $n$ into $m$ parts has a part of size $1$, it comes from a partition of $n-1$ into $m-1$ parts by adding a part of size $1$. Otherwise, it comes from a partition of $n-m$ into $m$ parts by adding $1$ to each part. The initial conditions are $P(n,m)=0$ for $m>n$, $P(n,n)=1$, and $P(n,0)=0$ for $n>0$.

See the two links and their references for more information.

share|improve this answer
    
Thanks! This is precisely what I was looking for. I wasn't even aware of the concept of partitions. –  Seba Jan 14 '13 at 16:17
    
@Seba: You’re welcome! –  Brian M. Scott Jan 14 '13 at 16:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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