$n$ balls into $k$ baskets, $n \geq k$, no empty baskets

Question

I have $n$ balls and throw them into $k$ baskets.

None of $k$ baskets should be empty. Which means each basket has at least one ball.

Balls and baskets are not distinguishable.

What is the number of cases of distribution of balls? And what is the number of each case?

I would be thankful if giving some rationale rather than just a formulae.

Answer 1

We need to make sure each of the baskets contain at least one ball, so why not first place a ball in each of the baskets. Once this is done, the non-empty condition is satisfied, so we can distribute the remaining balls without restriction. How many balls are left? How many ways are there of distributing this many balls between $k$ baskets?

Added Later: Let me introduce some terminology.

A partition of a positive integer $n$ is a collection of positive integers which has sum $n$. For example, $(2, 1)$ is a partition of $3$ because $2 + 1 = 3$. Two collections of positive integers which have the same numbers just in a different order are considered to define the same partition; for example $(2, 1)$ and $(1, 2)$ are two ways of writing the same partition.

In your situation, you will need to partition the remaining balls; note, your baskets are indistinguishable, that's why $(2, 1)$ and $(1, 2)$ should be considered the same. However, you can only partition the remaining balls into at most $k$ parts. If the number of remaining balls is less than $k$ (i.e. $n \leq 2k$), all the partitions will automatically have at most $k$ parts. If $n > 2k$, the problem is a fair bit harder. I'm not sure if there is an explicit formula for the number of ways of doing such partitions in terms of $n$ and $k$.

More information about partitions can be found here.

Answer 2

As others have mentioned, this is an additive number theory problem. In general there are no nice, explicit formulas for these types of problems. Ramanujan and Hardy worked out an amazing asymptotic formulas for p(n). There are, however, a ton of recursive formulas that when applied, give you explicit formulas for fixed k.

Let $p_k(n)=$ the number of ways to partition n into k parts. Then:

$p_k(n)=p_k(n-k) + p_{k-1}(n-1)$