How to find effective partition of $n$ into $k$?

Question

Here is a type of question that I find quite often on MO sites, that I couldn't quite solve:

How many ways can I put $n$ identical balls into $k$ identical boxes, with $n>>k$, such that each box has at least one ball?

For me, this question had $n=600$, and $k = 3$. At first, I thought this was a combinations problem, as we could have 3 balls put in each box first, and then the other $600-3=597$ balls can be placed in any boxes. The answer I first thought of was $3^{597}$. I then realised this was wrong, because I was considering each as a separate ball, in which case it wasn't.

Afterwards, I did a little research, and I thought this question might have something to do with compositions of numbers. However, the equation provided, which is $\binom{n-1}{k-1}$ was not the correct answer, when I plugged in $n$ and $k$ respectively, which got me $179101$. I realised that in my question, the $k$ boxes were not distinguishable, however in the equation, the $k$ boxes are.

I believe the way I need to solve this problem is using partitions, instead of compositions, of the numbers, but I am not yet sure. I don't know how I can solve this problem with partitions of numbers.

P.S the answer is $30,000$

Answer 1

Note that the $\binom{599}{2}$ compositions are almost exactly $6$ times the correct answer. This makes sense, because in general each partition into three parts corresponds to $3! = 6$ compositions. However, the ones with repeated parts correspond to fewer compositions, so we can't just divide by $6$.

There are three cases for a composition $\lambda_1 + \lambda_2 + \lambda_3$:

• All different (six compositions per partition)
• Two the same (three compositions per partition)
• All the same (one composition per partition)

The sum of all three cases comes to the aforementioned $\binom{599}{2}$.

The third case is a special case of the second. The total ($600$) minus the odd one out must be even, and can be any even number from $2$ to $598$, so we have $299$ partitions, of which one is the third case.

This gives a final count of $$\frac16 \left(179101 - 298 \times 3 - 1 \right) + 299 = 30000$$ as expected.

Obviously this is messier when $k > 3$.

Answer 2

You want the number of partitions of $600$ into exactly $3$ parts. See the Wikipedia article. The recursive formula given there $$p_k(n) = p_k(n − k) + p_{k−1}(n −1)\tag{1}$$ is best understood as counting the number of partitions of $n$ with largest part $k$. The first term on the right-hand side of $(1)$ counts the partitions with more than one part equal to $k$ and the second term counts the partitions with exactly one part equal to $k$. That the number of such partitions is equal to the number of partitions of $n$ with exactly $k$ parts is easily proved by transposing the Ferrers diagram, as the wiki article mentions in passing.

I checked the value with this python script:

def partitions(n,k):
    if n==k==0: return 1
    if n <=0 or k <=0: return 0
    return partitions(n-k,k)+partitions(n-1,k-1)

print(partitions(600,3))

and I did indeed get $30,000$.

This is a really inefficient way to program it, and I wouldn't use it except for a quick script that I'm going to use once and throw away.

A better way to do it, but a little harder to understand is

class Partitions(dict):
    def __init__(self):
        self[0,0] = 1
    def __missing__(self,key):
        n,k=key
        if n <= 0 or k <= 0:
            return 0
        self[n,k] = self[n-k,k] + self[n-1,k-1]
        return self[n,k]

partitions = Partitions()
print(partitions[600,3])

Answer 3

Okay, so following up from the answer:

The final answer, $179101$ is right if the question regarded each of the 3 boxes as unique. However, the question did not consider each box as unique, and each box is the same. This means that different compositions, such as $(1,3,596)$ and $(596,3,1)$ are the same sets.

For any composition, we have:

• If the combination has $3$ distinct numbers as the set, then $6$ compositions is equivalent to the corresponding partition
• If the combination has $2$ distinct numbers in the set, then there are $3$ different combinations making up the corresponding partition
• If the combination has no distinct numbers, then the amount of partitions is equal to the number of combinations for that specific number arrangement.

For the third case, we know only one is possible because if there are no distinct numbers in the combination, the value for each combination must be $600/3=200$.

For the second case, there are $299$ even numbers, excluding that of $(200,200,200)$, $298$ different cases. These numbers must be removed when we divide the sum of the combinations by 6, and they are counted 3 times.

So, what we have is: $$Original = \frac{179101-3*298-1}{6}+298+1 = 30,000$$

Just to make it slightly clearer.