Stars and bars (combinatorics)

In the context of combinatorial mathematics, 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 was popularized by William Feller in his classic book on probability. 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.^[4]

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 ${\displaystyle n=10}$ and ${\displaystyle k=4}$, the theorem gives the number of solutions to:

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

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

The answer is given by the binomial coefficient ${\displaystyle {n-1} \choose {k-1}}$. For the above example, there are ${\displaystyle {\binom {10-1}{4-1}}={\binom {9}{3}}=84}$ of them.

These consist of the permutations of the tuples ${\displaystyle (1,1,1,7),(1,1,2,6),(1,1,3,5),(1,1,4,4),(1,2,2,5),(1,2,3,4),(1,3,3,3),(2,2,2,4),(2,2,3,3)}$.

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 k − 1 taken from a set of size n + 1.

For example, if ${\displaystyle n=10}$ and ${\displaystyle k=4}$, the theorem gives the number of solutions to:

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

with ${\displaystyle x_{1},x_{2},x_{3},x_{4}\geq 0}$

The answer is given by the binomial coefficient ${\displaystyle {\binom {n+k-1}{k-1}}}$. For the above example, there are ${\displaystyle {\binom {10+4-1}{4-1}}={\binom {13}{3}}=286}$ of them.

Proofs via the method of stars and bars[]

Theorem one proof[]

Suppose there are n objects (represented here by stars) to be placed into k bins, such that all bins contain at least one object. The bins are distinguishable (say they are numbered 1 to k) but the n stars are not (so configurations are only distinguished by the number of stars present in each bin). A configuration is thus represented by a k-tuple of positive integers, as in the statement of the theorem.

For example, with n = 7 and k = 3, start by placing the stars in a line:

The configuration will be determined once it is known which is the first star going to the second bin, and the first star going to the third bin, etc.. This is indicated by placing k − 1 bars between the stars. Because no bin is allowed to be empty (all the variables are positive), there is at most one bar between any pair of stars.

For example:

There are n − 1 gaps between stars. A configuration is obtained by choosing k − 1 of these gaps to contain a bar; therefore there are ${\displaystyle {\tbinom {n-1}{k-1}}}$ possible combinations.

Theorem two proof[]

In this case, the weakened restriction of non-negativity instead of positivity means that we can place multiple bars between stars, before the first star and after the last star.

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

To see that there are ${\displaystyle {\tbinom {n+k-1}{k-1}}}$ possible arrangements, observe that any arrangement of stars and bars consists of a total of n + k − 1 objects, 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).

Theorem 1 can now be restated in terms of Theorem 2, because the requirement that all the variables are positive is equivalent to pre-assigning each variable a 1, and asking for the number of solutions when each variable is non-negative.

For example:

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

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

is equivalent to:

${\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=6}$

with ${\displaystyle x_{1},x_{2},x_{3},x_{4}\geq 0}$

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 ${\displaystyle {\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 ${\displaystyle n=6}$, as described in the previous figure. If zero is allowed, the number of cookies is only ${\displaystyle 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 ${\displaystyle {7-1 \choose 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 stars and k − 1 = 3 bars to give ${\displaystyle {5+4-1 \choose 4-1}={8 \choose 3}=56}$.

Example 3[]

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

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

Example 4[]

If we have the infinite Taylor series ${\displaystyle \left[\sum _{k=1}^{\infty }x^{k}\right]^{m}}$, then we can use this method to expand the sum. For the nth term of the expansion, we are picking n powers of x from m separate locations. Hence there are ${\displaystyle {{n-1} \choose {m-1}}}$ ways to form our nth power:

${\displaystyle \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 – as a simple derivation of Max Planck's expression of "complexions".^[5]

Planck called "complexions" the number R of possible distributions of P energy elements ε over N resonators:^[6] ${\displaystyle R={\frac {(N+P-1)!}{P!(N-1)!}}\ }$

The graphical representation would contain P times the symbol ε and (N - 1) times the sign | for each possible distribution. 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: εεεε|εε||ε

See also[]

• Twelvefold way
• Partition (number theory)

References[]

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.