Stars and bars (combinatorics)

In the context of combinatorial mathematics, stars and bars 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.[1]

Statements of theorems

The stars and bars method is often introduced specifically to prove the following two theorems of elementary combinatorics.

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.

Both of these numbers are given by the binomial coefficient ${\displaystyle \textstyle {{n-1} \choose {k-1}}}$. For example, when n = 3 and k = 2, the tuples counted by the theorem are (2, 1) and (1, 2), and there are ${\displaystyle {\tbinom {3-1}{2-1}}=2}$ of them.

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.

Both numbers are given by the multiset number ${\displaystyle \left(\!{\tbinom {n+1}{k-1}}\!\right)}$, or equivalently by the binomial coefficient ${\displaystyle {\tbinom {n+k-1}{k-1}}={\tbinom {n+k-1}{n}}}$ or multiset number ${\displaystyle {\big (}\!{\tbinom {k}{n}}\!{\big )}}$. For example, when n = 3 and k = 2, the tuples counted by the theorem are (3, 0), (2, 1), (1, 2), and (0, 3), and there are ${\displaystyle \left(\!{\tbinom {3+1}{2-1}}\!\right)=4}$ of them.

Proofs via the method of stars and bars

Theorem one

Suppose there are n objects (represented by stars; in the example below n = 7) to be placed into k bins (in the example k = 3), 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. Instead of starting by placing stars into bins, start by placing the stars on a line:

★ ★ ★ ★ ★ ★ ★

Fig. 1: seven objects represented by stars

where the stars for the first bin will be taken from the left, followed by the stars for the second bin, and so forth. Thus, 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, and so on. This can be indicated by placing k − 1 separating bars at places between two stars. Since no bin is allowed to be empty, there can be at most one bar between a given pair of stars:

★ ★ ★ ★

|

★

|

★ ★

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

View the n stars as fixed objects defining n − 1 gaps between stars, in each of which there may or may not be one bar (a bin partition). A configuration is obtained by choosing k − 1 of these gaps to actually contain a bar; therefore, there are ${\displaystyle {\tbinom {n-1}{k-1}}}$ possible configurations (see combination).

Theorem two

In this case, the representation of a tuple as a sequence of stars and bars, with the bars dividing the stars into bins, is unchanged. The weakened restriction of nonnegativity (instead of positivity) means that one may place multiple bars between two stars, as well as placing bars before the first star or after the last star. Thus, for example, when n = 7 and k = 5, the tuple (4, 0, 1, 2, 0) may be represented by the following diagram.

★ ★ ★ ★

|

|

★

|

★ ★

|

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

This establishes a one-to-one correspondence between tuples of the desired form and selections with replacement of k − 1 gaps from the n + 1 available gaps, or equivalently (k − 1)-element multisets drawn from a set of size n + 1. By definition, such objects are counted by the multichoose number ${\displaystyle \left(\!{\tbinom {n+1}{k-1}}\!\right)}$.

To see that these objects are also counted by the binomial coefficient ${\displaystyle {\tbinom {n+k-1}{n}}}$, observe that the desired arrangements consist of n + k − 1 objects (n stars and k − 1 bars). Choosing the positions for the stars leaves exactly k − 1 spots left for the k − 1 bars. That is, choosing the positions for the stars determines the entire arrangement, so the arrangement is determined with ${\displaystyle {\tbinom {n+k-1}{n}}}$ selections. Note that ${\displaystyle {\tbinom {n+k-1}{n}}={\tbinom {n+k-1}{k-1}}}$, reflecting the fact that one could also have determined the arrangement by choosing the positions for the k − 1 bars.

Examples

Example 1

If n = 5, k = 4, and a set of size k is {a, b, c, d}, then ★|★★★||★ would represent the multiset {a, b, b, b, d} or the 4-tuple (1, 3, 0, 1). The representation of any multiset for this example would use n = 5 stars and k − 1 = 3 bars.

Many elementary word problems in combinatorics are resolved by the theorems above. For example, 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 the stars and bars apply with n = 7 and k = 3, and there are ${\displaystyle {7-1 \choose 3-1}=15}$ ways to distribute the coins.

Example 2

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”.[2]

Planck called “complexions” the number R of possible distributions of P energy elements ε over N resonators:[3] ${\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

1. Feller, William (1950). An Introduction to Probability Theory and Its Applications. 1 (2nd ed.). Wiley.
2. Ehrenfest, Paul; Kamerlingh Onnes, Heike (1915). "Simplified deduction of the formula from the theory of combinations which Planck uses as the basis of his radiation theory". The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science: Series 6. 29 (170): 297–301. doi:10.1080/14786440208635308. Retrieved 5 December 2020.
3. Planck, Max (1901). "Ueber das Gesetz der Energieverteilung im Normalspectrum". Annalen der Physik. 309 (3): 553–563. doi:10.1002/andp.19013090310. Retrieved 5 December 2020.

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.