Identical Objects into Identical Bins

Identical objects into identical bins is a type of problem in combinatorics in which the goal is to count the number of ways a number of identical objects can be placed into identical bins.

Although similar problems distinct objects into distinct bins and identical objects into distinct bins have closed-form solutions, the "identical objects into identical bins" problem presents some particular challenges with finding solutions efficiently.

In this type of problem, the objects are identical. This means that it does not matter which objects are grouped together; it only matters how many objects go into each bin. In addition to this, the bins are identical. This means that the ordering of the bins does not matter, and bins must be non-empty.

There are 5 identical balls. How many ways can these balls be put into groups? There can be any number of groups, and groups can be of any size except 0.

---

This problem is asking us to find the number of distributions of 5 identical objects into any number of identical bins. These distributions are shown below:

In total, there are \(\boxed{7}\) ways to group the balls.

The "identical objects into identical bins" problem is closely related to the problem of partitioning an integer. Many of the same problem-solving strategies will be used. Problems of the type "identical objects into any number of identical bins" are equivalent to the partition of an integer problem.

If you have visited the partition of an integer wiki page, then the previous problem will seem familiar. In fact, there is a bijection between the distributions of the 5 objects and the partitions of the integer 5. This holds true for the distribution of \(n\) identical objects into any number of identical bins.

The number of distributions of \(n\) identical objects into any number of identical bins is \(p(n)\), where \(p(n)\) is the partition function.

For reference, the values of the partition function for \(n\le 7\) are listed below. Note that the function is defined to have a value of \(1\) at \(n=0\):

\[\begin{array}{c|c} n & p(n) \\ \hline 0 & 1 \\ 1 & 1 \\ 2 & 2 \\ 3 & 3 \\ 4 & 5 \\ 5 & 7 \\ 6 & 11 \\ 7 & 15 \\ \end{array}\]

The problems discussed on this page so far have been of the type, "identical objects into any number of identical bins." These can be solved simply by finding \(p(n)\), where \(n\) is the number of objects.

Problems of the type "identical objects into identical bins" are somewhat different because they require a specific number of non-empty bins. Fortunately, many of the same problem-solving strategies used for partitions of an integer can be used. This problem can be thought of as finding the number of partitions of a number into a specific number of parts.

How many ways can 6 identical balls be put into 3 groups?

---

This problem can be modeled as finding the partitions of \(6\) into exactly \(3\) parts. These partitions are listed below:

\[4+1+1\] \[3+2+1\] \[2+2+2\]

In total, there are \(\boxed{3}\) ways to put the \(6\) balls into \(3\) groups.

If \(n\) and \(r\) are relatively small, then it is simple to list out all of the distributions, as above. For larger \(n\) and \(r\), a different approach will be needed involving recursion. The following theorem will be needed:

The number of partitions of an integer \(n\) into \(r\) parts is the same as the number of partitions of \(n\) for which the largest part is \(r\).

The partition function for which the largest part is \(r\) is denoted as \(p(n,r)\).

The proof of this theorem is on the integer partitions page. The benefit of this theorem is that it allows for finding partitions in a much more predictable manner.

What is \(p(6,3)\)?

---

The answer to this problem should be the same as the previous example due to the theorem above. The partitions of \(6\) for which \(3\) is the largest part are listed below:

\[3+3\] \[3+2+1\] \[3+1+1+1\]

As before, there are \(\boxed{3}\) partitions of \(6\) for which \(3\) is the largest part. However, one could argue that this version of the problem is slightly easier to solve. With \(3\) as the largest part, there is \(3\) left to partition. Thus, the answer is the same as \(p(3)\).

If \(n\le 2r\), then \(p(n,r)=p(n-r)\)

\(p(n,r)\) leads to partitions in which the first part is always \(r\), and the rest of the parts are partitions of the integer \(n-r\).
When \(n\le 2r\), \(n-r\le r\). Therefore, the partitions of \(n-r\) in \(p(n,r)\) will be all of the partitions of \(n-r\).
Thus, \(p(n,r)=p(n-r)\) when \(n\le 2r\).

The preceding theorem applies to partitions of \(n\) for which \(r\) is the largest part. This is equivalent to partitions of \(n\) into exactly \(r\) parts, so the preceding theorem can also be applied to problems of that type.

How many ways are there to partition \(1729\) into exactly \(1726\) positive integers?

---

The answer to this problem is equal to \(p(1729,1726)\), the number of partitions of \(1729\) for which \(1726\) is the largest part.

\(1729\le 2\times1726\), so \(p(1729,1726)=p(1729-1726)=p(3)\)

\(p(3)=3\), so there are exactly \(\boxed{3}\) ways to partition \(1729\) into \(1726\) positive integers.

Let \(n\) be the number of identical objects to be distributed among \(r\) identicals bins. There are a couple of relatively simple cases for the number of distributions. These will be useful in the future, because recursion will be used to find the solutions to more complicated problems.

Case 1: \(n<r\)

There are not enough objects to go into each bin. Therefore, the number of distribution is \(0\).

Case 2: \(n=r\)

There is exactly \(1\) object for each bin. Therefore, there is only \(1\) distribution.

Case 3: \(n=r+1\)

There is exactly \(1\) object for each bin, and \(1\) more object left to be placed. It does not matter which bin it is placed into, so there is exactly \(1\) distribution.

Case 4: \(r=1\)

There is only one bin the objects can go into, so there is only \(1\) distribution.

Case 5: \(r=2\)

If \(n\) is odd, then the number of distributions is \(\dfrac{n-1}{2}\). If \(n\) is even, then the number of distributions is \(\dfrac{n}{2}\).

You have $987 that you are thinking about putting into 2 identical savings accounts. How many ways are there to distribute the money into 2 groups?

---

Assume that money is distributed into whole dollar amounts. This can be modeled as \(n=987\) identical objects distributed into \(r=2\) identical bins.

The base case for \(r=2\) can be used. \(987\) is odd, so the number of distributions is \(\dfrac{n-1}{2}=\dfrac{986}{2}=493\).

Thus, there are \(\boxed{493}\) ways to distribute the money into 2 groups.

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)=\sum\limits_{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 \(\boxed{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.

\[ \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} \]