How many ways can you distribute 10 identical balls into two identical boxes so none are empty?

In order to continue enjoying our site, we ask that you confirm your identity as a human. Thank you very much for your cooperation.

When $n$ and $r$ become sufficiently large, the problem of finding the number of distributions of $n$ identical objects into $r$ identical bins can be daunting. Fortunately, there is a way to use recursion to break the problem down into simpler parts. The following theorem will be key in breaking down these problems.

p(n,r)=∑k=1rp(n−r,k)p(n,r)=\sum\limits_{k=1}^{r}{p(n-r,k)}p(n,r)=k=1∑r​p(n−r,k)

When parts are ordered greatest to least, each partition counted by $p(n,r)$ always starts with the integer $r$. The rest of the integers in the partition are themselves a partition of $n-r$. These partitions of $n-r$ can have a greatest integer between $1$ and $r$, inclusive. Thus, $p(n,r)$ is equal to the sum of all $p(n-r,k)$, where $k$ is an integer between $1$ and $r$, inclusive.

The strategy for solving "identical objects into identical bins" will be to use the above theorem, along with all the other theorems and base cases on this page, to arrive at a solution as efficiently as possible. It will not always be possible to arrive at a solution in a few steps, but recursion will make it possible to break a complicated problem down into simpler problems.

How many ways are there to put 12 identical cubes into 3 groups? Each group must have at least one cube, and the order of the groups does not matter.

This problem can be thought of as finding $p(12,3)$. Using the above theorem,

$p(12,3)=p(9,1)+p(9,2)+p(9,3)$

By base case 4, $p(9,1)=1$.

By base case 5, $p(9,2)=4$.

Now we can use the above theorem again to find $p(9,3)$:

$p(9,3)=p(6,1)+p(6,2)+p(6,3)$

By base case 4, $p(6,1)=1$.

By base case 5, $p(6,2)=3$.

For $p(6,3)$, $n\le 2r$. By a previous theorem, $p(6,3)=p(3)=3$.

So, $p(9,3)=1+3+3=7$

$p(12,3)=p(9,1)+p(9,2)+p(9,3)=1+4+7=12$

Therefore, there are 12\boxed{12}12​ ways to distribute 12 identical cubes into 3 groups.

For reference, the values of $p(n,r)$ for $n,r\le 7$ are listed below.

n\r123456711211311141211512211613321171343211 \begin{array} { c | c c c c c c c } _n \backslash ^r & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline 1 & 1 \\ 2 & 1 & 1 \\ 3 & 1 & 1 & 1 \\ 4 & 1 & 2 & 1 & 1 \\ 5 & 1 & 2 & 2 & 1 & 1 \\ 6 & 1 & 3 & 3 & 2 & 1 & 1 \\ 7 & 1 & 3 & 4 & 3 & 2 & 1 & 1 \\ \end{array} n​\r1234567​11111111​2112233​311234​41123​5112​611​71​​