Stars and Bars

A stars and bars problem (also known as a balls and bins problem) is a combinatorial technique used to count the number of ways to form unordered selections with repetition allowed from a set.

It is equivalent to counting the number of non-negative integer solutions to
$x_{1} + x_{2} + \dots + x_{n} = k,$
$n$ is the number of distinct categories (bins), and $k$ is the number of items (stars) to be distributed among the categories. Each $x_{i}$ is simply the count of items for that category.

The number of such combinations is given by
$N = (k k + n - 1) = (n - 1 k + n - 1) .$

Intuition

Although stars and bars problems may be initially difficult to understand since you cannot derive it from any of the previous concepts, the explanation is not difficult. To begin, consider $(k n)$ , which represents the number of ways to “take out” elements from a set without replacing them, or considering order. In stars and bars we have replacement, so given a set ${1, 2, 3}$ , $(1, 1, 1, 1, 1, 1, 3)$ is a valid length-7 sequence.

Think for a second about what $k$ and $n$ alternatively represent:

We have $k$ identical elements to assign.
We need to divide them into $n$ buckets (or equivalently, $n - 1$ dividers).

For example, the length-7 sequence from the set ${1, 2, 3}$ above can equivalently be represented as $* * * * * * * ∣ ∣ * .$
Therefore, we are counting all the ways to combine the $k$ identical elements (stars) and the $n - 1$ identical dividers (bars), which together form a sequence of $k + n - 1$ symbols. Since we are selecting $k$ positions to place the elements (or equivalently, $n - 1$ positions to place the dividers), the total number of such arrangements is $(k k + n - 1) = (n - 1 k + n - 1)$

Examples

Oranges and Apples

We want to put 6 out of an infinite number of oranges and apples in 4 baskets. The order which we put the fruit in the basket does not matter. We can transform this example into a binomial string, where 1s represent separations between boxes and 0s represent the fruit. An example string is:
$011000100$
Where (from left to right) there is 1 fruit in first basket, no fruit in the 2nd basket, 3 fruits in the third basket, and 2 fruits in the fourth basket.

Knowing this, we can say that the total number of choices is equal to the number of 0s ( $k =$ fruits) plus the number of 1s ( $n =$ baskets) - 1. Then, we want to count all the possibilities of placing fruit in each basket where ordering does not matter. We use the SRC (since order doesn’t matter) to come up with:
$(k k + n - 1) = \frac{( k + n - 1 )!}{( n - 1 )! \times k !} = \frac{9 !}{8 ! \times 4 !}$

Farmer’s Market

Suppose you want $k$ items from the farmer’s market. Count how many ways you can do this, assuming:

There are pumpkins and apples at the market.

Jelly Bean Factory

A candy factory has an endless supply of red, orange and yellow jelly beans. The factory packages the jelly beans into jars of 100 jelly beans each, with each possible combination of colors in the jar being equally likely.

Find $N$ , the number of different possible color combinations of jelly beans in a single jar. We have $n = 3$ types of jelly beans: red, orange and yellow. This means that there are two bars to separate each color. Since there are $k = 100$ jelly beans in a jar, this means that $N = (3 - 1 100 + 3 - 1) = (2 102) = 5151.$

Project Alexandria

Explorer

6.2d Stars and Bars

Intuition

Examples

Graph View

Table of Contents