Stars and bars (combinatorics)

In combinatorics, stars and bars (also called "sticks and stones",[1] "balls and bars",[2] and "dots and dividers"[3]) is a graphical aid for deriving certain combinatorial theorems.

It can be used to solve a variety of counting problems, such as how many ways there are to put n indistinguishable balls into k distinguishable bins.

The table shows the six possible ways of distributing the two balls, the strings of stars and bars that represent them (with stars indicating balls and bars separating bins from one another), and the subsets that correspond to the strings.

Each subset indicates which of the four symbols in the corresponding string is a bar.

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.

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 x1 + x2 + x3 + x4 = 10 (with x1, x2, x3, x4 > 0) as the binomial coefficient where

With k fixed, the numbers for n = 0, 1, 2, 3, … are those in the (k − 1)st diagonal of Pascal's triangle.

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.

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.

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.

With n = 7 and k = 3, start by placing seven stars in a line: Now indicate the boundaries between the bins: In general two of the six possible bar positions must be chosen.

An alternative interpretation in terms of multisets is the following: 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 indicating the number of objects placed in that bin.

can also be understood as an equivalence of different counting problems: the number of k-tuples of non-negative integers whose sum is n equals the number of (n + 1)-tuples of non-negative integers whose sum is k − 1, which follows by interchanging the roles of bars and stars in the diagrams representing configurations.

When n = 7 and k = 5, the tuple (4, 0, 1, 2, 0) may be represented by the following diagram: If possible bar positions are labeled 1, 2, 3, 4, 5, 6, 7, 8 with label i ≤ 7 corresponding to a bar preceding the ith star and following any previous star and 8 to a bar following the last star, then this configuration corresponds to the (k − 1)-multiset {5,5,6,8}, as described in the proof of Theorem two.

If bins are labeled 1, 2, 3, 4, 5, then it also corresponds to the n-multiset {1,1,1,1,3,4,4}, also as described in the proof of Theorem two.

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.)

The solution of this problem should use Theorem 2 with n = 5 stars and k – 1 = 3 bars to give

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.

[5][6] By complexions (microstates) Planck meant distributions of P energy elements ε over N resonators.

In their demonstration, Ehrenfest and Kamerlingh Onnes took N = 4 and P = 7 (i.e., R = 120 combinations).

The enumerations of Theorems one and two can also be found using generating functions involving simple rational expressions.

The exponent of x indicates how many objects are placed in the bin.

; the generating function for k bins is where the multiplication is the Cauchy product of formal power series.

To find the number of configurations with n objects, we want the coefficient of

), that is, This coefficient can be found using binomial series and agrees with the result of Theorem two, namely

This Cauchy product expression is justified via stars and bars: the coefficient of

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 two bar symbols ( | | ) to occupy any two of the three gaps. Hence the problem reduces to finding the binomial coefficient 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 results the number of bins is 3. If zero is not allowed, the number of cookies should be n = 6 , as described in the previous figure. If zero is allowed, the number of cookies should only be n = 3 .