Stars and bars (combinatorics)

In combinatorics, stars and bars (also called "sticks and stones", "balls and bars", and "dots and dividers") is a graphical aid for deriving certain combinatorial theorems. It can be used to solve many simple counting problems, such as how many ways there are to put n indistinguishable balls into k distinguishable bins.

Theorems one and two are the coefficients used for 2 different support ranges in the negative binomial probability distribution.

Statements of theorems

The stars and bars method is often introduced specifically to prove the following two theorems of elementary combinatorics concerning the number of solutions to an equation.

Theorem one

For any pair of positive integers n and k, the number of k-tuples of positive integers whose sum is n is equal to the number of (k − 1)-element subsets of a set with n − 1 elements.

For example, if n = 10 and k = 4, the theorem gives the number of solutions to x₁ + x₂ + x₃ + x₄ = 10 (with x₁, x₂, x₃, x₄ > 0) as the binomial coefficient

${\binom {n-1}{k-1}}={\binom {10-1}{4-1}}={\binom {9}{3}}=84,$

where ${\binom {n-1}{k-1}}$ is the number of combinations of n − 1 elements taken k − 1 at a time.

This corresponds to compositions of an integer.

Theorem two

For any pair of positive integers n and k, the number of k-tuples of non-negative integers whose sum is n is equal to the number of multisets of cardinality n taken from a set of size k, or equivalently, the number of multisets of cardinality k − 1 taken from a set of size n + 1.

For example, if n = 10 and k = 4, the theorem gives the number of solutions to x₁ + x₂ + x₃ + x₄ = 10 (with x₁, x₂, x₃, x₄ $\geq 0$ ) as:

$\left(\!\!{k \choose n}\!\!\right)={k+n-1 \choose n}={\binom {13}{10}}=286$

$\left(\!\!{n+1 \choose k-1}\!\!\right)={n+1+k-1-1 \choose k-1}={\binom {13}{3}}=286$

${\binom {n+k-1}{k-1}}={\binom {10+4-1}{4-1}}={\binom {13}{3}}=286$

This corresponds to weak compositions of an integer.

Proofs via the method of stars and bars

Theorem one proof

The problem of enumerating k-tuples whose sum is n is equivalent to the problem of counting configurations of the following kind: let there be n objects to be placed into k bins, so that all bins contain at least one object. The bins are distinguished (say they are numbered 1 to k) but the n objects are not (so configurations are only distinguished by the number of objects present in each bin). A configuration is thus represented by a k-tuple of positive integers.

The n objects are now represented as a row of n stars; adjacent bins are separated by bars. The configuration will be specified by indicating the boundary between the first and second bin, the boundary between the second and third bin, and so on. Hence k − 1 bars need to be placed between stars. Because no bin is allowed to be empty, there is at most one bar between any pair of stars. There are n − 1 gaps between stars and hence n − 1 positions in which a bar may be placed. A configuration is obtained by choosing k − 1 of these gaps to contain a bar; therefore there are ${\tbinom {n-1}{k-1}}$ configurations.

Example

With n = 7 and k = 3, start by placing seven stars in a line:

★ ★ ★ ★ ★ ★ ★

Fig. 1: Seven objects, represented by stars

Now indicate the boundaries between the bins:

★ ★ ★ ★ | ★ | ★ ★

Fig. 2: These two bars give rise to three bins containing 4, 1, and 2 objects

In general two of the six possible bar positions must be chosen. Therefore there are ${\binom {6}{2}}=15$ such configurations.

Theorem two proof

In this case, the weakened restriction of non-negativity instead of positivity means that we can place multiple bars between stars and that one or more bars also be placed before the first star and after the last star. In terms of configurations involving objects and bins, bins are now allowed to be empty.

To see that there are ${\tbinom {n+k-1}{k-1}}$ possible arrangements, observe that any arrangement of stars and bars consists of a total of n + k − 1 symbols, n of which are stars and k − 1 of which are bars. Thus, we only need to choose k − 1 of the n + k − 1 positions to be bars (or, equivalently, choose n of the positions to be stars).

Rather than a (k − 1)-set of bar positions taken from a set of size as (n − 1) as in the proof of Theorem one, we now have a (k − 1)-multiset of bar positions taken from a set of size as (n + 1) (since bar positions may repeat and since the ends are now allowed bar positions). There is an alternative interpretation in terms of multisets: there is a set of k bin labels from which a multiset of size n is to be chosen. (The multiplicity of a bin label in this multiset indicates the number of objects placed in that bin.)

Example

When n = 7 and k = 5, the tuple (4, 0, 1, 2, 0) may be represented by the following diagram:

★ ★ ★ ★ | | ★ | ★ ★ |

Fig. 3: These four bars give rise to five bins containing 4, 0, 1, 2, and 0 objects

Relation between Theorems one and two

Theorem one can be restated in terms of Theorem two, because the requirement that each variable be positive can be imposed by shifting each variable by −1, and then requiring only that each variable be non-negative.

For example:

$x_{1}+x_{2}+x_{3}+x_{4}=10$

with $x_{1},x_{2},x_{3},x_{4}>0$

is equivalent to:

$x'_{1}+x'_{2}+x'_{3}+x'_{4}=6$

with $x'_{1},x'_{2},x'_{3},x'_{4}\geq 0,$

where $x'_{i}=x_{i}-1$ for each $i\in \{1,2,3,4\}$.

Proofs by generating functions

Both cases are very similar, we will look at the case when $x_{i}\geq 0$ first. The 'bucket' becomes

${\frac {1}{1-x}}$

This can also be written as

$1+x+x^{2}+\dots$

and the exponent of x tells us how many balls are placed in the bucket.

Each additional bucket is represented by another ${\frac {1}{1-x}}$, and so the final generating function is

${\frac {1}{1-x}}{\frac {1}{1-x}}\dots {\frac {1}{1-x}}={\frac {1}{(1-x)^{k}}}$

As we only have n balls, we want the coefficient of $x^{n}$ (written $[x^{n}]:$) from this

$[x^{n}]:{\frac {1}{(1-x)^{k}}}$

This is a well-known generating function - it generates the diagonals in Pascal's Triangle, and the coefficient of $x^{n}$ is

${\binom {n+k-1}{k-1}}$

For the case when $x_{i}>0$, we need to add x into the numerator to indicate that at least one ball is in the bucket.

${\frac {x}{1-x}}{\frac {x}{1-x}}\dots {\frac {x}{1-x}}={\frac {x^{k}}{(1-x)^{k}}}$

and the coefficient of $x^{n}$ is

${\binom {n-1}{k-1}}$

Examples

Many elementary word problems in combinatorics are resolved by the theorems above.

Four cookies are distributed between Tom, Dick, and Harry (TDH) in such a way that each gets at least one cookie. The 4 cookies are traditionally represented as stars (****). But here, they are shown as cookie-colored circles (●●●●). The 3 gaps between the cookies are indicated by red carets (^ ^ ^). With three people, we need 2 bar symbols (| |) to occupy any two of the three gaps. Hence the problem reduces to finding the binomial coefficient ${\tbinom {3}{2}}.$ Also shown are the three corresponding 3-compositions of 4.

The three-choose-two combination yields two results, depending on whether a bin is allowed to have zero items. In both cases the number of bins is 3. If zero is not allowed, the number of cookies is n = 6, as described in the previous figure. If zero is allowed, the number of cookies is only n = 3.

Example 1

If one wishes to count the number of ways to distribute seven indistinguishable one dollar coins among Amber, Ben, and Curtis so that each of them receives at least one dollar, one may observe that distributions are essentially equivalent to tuples of three positive integers whose sum is 7. (Here the first entry in the tuple is the number of coins given to Amber, and so on.) Thus stars and bars theorem 1 applies, with n = 7 and k = 3, and there are ${\tbinom {7-1}{3-1}}=15$ ways to distribute the coins.

Example 2

If n = 5, k = 4, and a set of size k is {a, b, c, d}, then ★|★★★||★ could represent either the multiset {a, b, b, b, d} or the 4-tuple (1, 3, 0, 1). The representation of any multiset for this example should use SAB2 with n = 5, k – 1 = 3 bars to give ${\tbinom {5+4-1}{4-1}}={\tbinom {8}{3}}=56$.

Example 3

SAB2 allows for more bars than stars, which isn't permitted in SAB1.

So, for example, 10 balls into 7 bins is ${\tbinom {16}{6}}$, while 7 balls into 10 bins is ${\tbinom {16}{9}}$, with 6 balls into 11 bins as ${\tbinom {16}{10}}={\tbinom {16}{6}}.$

Example 4

If we have the infinite power series

$\left[\sum _{k=1}^{\infty }x^{k}\right],$

we can use this method to compute the Cauchy product of m copies of the series. For the nth term of the expansion, we are picking n powers of x from m separate locations. Hence there are ${\tbinom {n-1}{m-1}}$ ways to form our nth power:

$\left[\sum _{k=1}^{\infty }x^{k}\right]^{m}=\sum _{n=m}^{\infty }{{n-1} \choose {m-1}}x^{n}$

Example 5

The graphical method was used by Paul Ehrenfest and Heike Kamerlingh Onnes—with symbol ε (quantum energy element) in place of a star and the symbol 0 in place of a bar—as a simple derivation of Max Planck's expression for the number of "complexions" for a system of "resonators" of a single frequency.

By complexions (microstates) Planck meant distributions of P energy elements ε over N resonators. The number R of complexions is

$R={\frac {(N+P-1)!}{P!(N-1)!}}.\$

The graphical representation of each possible distribution would contain P copies of the symbol ε and N – 1 copies of the symbol 0. In their demonstration, Ehrenfest and Kamerlingh Onnes took N = 4 and P = 7 (i.e., R = 120 combinations). They chose the 4-tuple (4, 2, 0, 1) as the illustrative example for this symbolic representation: εεεε0εε00ε.

See also

• Gaussian binomial coefficient
• Partition (number theory)
• Twelvefold way
• Dirichlet-multinomial distribution

Further reading

• Pitman, Jim (1993). Probability. Berlin: Springer-Verlag. ISBN 0-387-97974-3.
• Weisstein, Eric W. "Multichoose". Mathworld -- A Wolfram Web Resource. Retrieved 18 November 2012.