Identical Objects into Distinct Bins

Identical objects into distinct bins is a problem in combinatorics in which the goal is to find the number of distributions of a number of identical objects into a number of distinct bins. This problem has a similar wording to problems such as distinct objects into distinct bins and distinct objects into identical bins, but the approach for these type of problems is quite different.

Suppose there are 4 identical balls to be distributed among 3 children. How many ways can the balls be distributed?

---

In this problem, the balls are modeled as identical objects, and the children are modeled as distinct bins. The distributions can be listed exhaustively, as below:

In all, there are \(\boxed{15}\) distributions.

In the kinds of problems outlined on this page, every object distributed is the same, but it matters how many of each object is given to each person or place. A relevant example would be a research director counting how many ways there are to distribute funding allotments to research groups, assuming all funding allotments are the same. Research groups who receive fewer allotments would certainly take notice, but the research director must also consider the goals of her organization in determining allotments. An accounting of all the possible distributions of allotments would give the research director a picture of how she could allocate the money.

In the example in the introduction, the distributions were exhaustively mapped out and listed as a set. Unfortunately, this is not a very efficient way of counting the distributions. Coming up with an efficient way to count the distributions requires some creative thinking. This approach, called stars and bars, is also used in other areas of combinatorics.

Imagine the 4 objects in a line, shown here as stars:

\[\large\star\star\star\star\]

The objects can be divided into bins by placing a bar either between the stars or at the ends:

\[\large\star\star\star|\star\]

\[\large|\star\star\star\star\]

Placing 1 bar creates 2 distinct groups. Placing the bar at one of the ends will create a group with 0 stars.

Placing 2 bars will create 3 distinct groups:

\[\large\star|\star\star|\star\]

\[\large\star||\star\star\star\]

Placing bars next to each other creates a group with 0 stars.

As a general rule, if we would like to divide the stars into \(r\) distinct groups, this will require \(r-1\) bars.

Back to the problem of distributing 4 identical objects among 3 distinct groups. Modeled as stars and bars, there will be 4 stars and 2 bars. There are \(4+2=6\) things that need to be placed, and 2 of those placements are chosen for the bars. Thus, there are \(\binom{6}{2}=15\) possible distributions of 4 identical objects among 3 distinct groups. This is consistent with the answer from before.

Suppose there are \(n\) identical objects to be distributed among \(r\) distinct bins. This can be done in precisely \(\binom{n+r-1}{r-1}\) ways.

Modeled as stars and bars, there are \(n\) stars in a line and \(r-1\) bars that divide them into \(r\) distinct groups. There are a total of \(n+r-1\) things that will be placed, and \(r-1\) of those placements are chosen for the bars. The stars will be put in the remaining placements. Thus, there are \(\binom{n+r-1}{r-1}\) possible placements of the bars. Equivalently, there are \(\binom{n+r-1}{r-1}\) possible distributions of \(n\) identical objects among \(r\) distinct bins.

There are 10 identical bananas that are to be distributed among 5 distinct monkeys. How many ways are there to distribute the bananas?

---

In this example, there are \(n=10\) identical objects and \(r=5\) distinct bins. Using the formula above, there are \(\binom{14}{4}=\boxed{1001}\) ways to distribute the bananas.

The previous problems and examples covered situations in which bins could be left empty. Now consider how the problem changes when bins are required to be non-empty. Fortunately, a similar approach can be used.

Consider a problem in which we are attempting to find the number of distributions of 8 identical objects among 5 distinct bins, and bins cannot be left empty. Modeling the problem as stars and bars, it would start off by looking like this:

\[\large\star\star\star\star\star\star\star\star\]

Just as with previous examples, the number of bars will be \(1\) less than the number of bins. So we have \(4\) bars to place. Where can they be placed? If you recall from the previous example, if bars were put at the ends or next to other bars, it created empty groups. So in order for there to be no empty groups, bars can only be placed between the stars, and only one bar can be placed between a pair of stars.

\[\large\star|\star|\star\star|\star\star|\star\star\]

There are exactly \(7\) potential locations that meet these criteria. In other words, \(1\) less than the number of objects. Out of these \(7\) potential locations, \(4\) bars are placed. Thus, there are \(\binom{7}{4}=35\) possible distributions of 8 identical objects into 5 distinct non-empty bins.

Suppose there are \(n\) identical objects to be distributed among \(r\) distinct non-empty bins, with \(n\ge r\). This can be done in precisely \(\binom{n-1}{r-1}\) ways.

For this type of problem, \(n\ge r\) must be true. If \(n<r\), then there are not enough objects to fill each of the bins with at least one object.

Modeled as stars and bars, there are \(n\) stars and \(r-1\) bars to place. In order for the groups to be non-empty, the bars can only be placed between the stars, and only one bar can be placed between a pair of stars. Thus, there are \(n-1\) possible placements for the bars. Out of those \(n-1\) possible placements, \(r-1\) are chosen for the bars. Hence, the number of possible arrangements of stars and bars is \(\binom{n-1}{r-1}\). Equivalently, there are \(\binom{n-1}{r-1}\) distributions of \(n\) identical objects into \(r\) distinct non-empty bins.

A teacher has 12 identical pencils to distribute among a classroom of 9 distinct students. How many ways are there to distribute the 12 pencils such that each student gets at least one pencil?

---

In this example, there are \(n=12\) identical objects to be distributed among \(r=9\) distinct bins. Using the above formula, the number of possible distributions is \(\binom{11}{8}=\boxed{165}\).