Stars and bars (probability)

From Wikipedia, the free encyclopedia

In the context of combinatorial mathematics, stars and bars refers to a trick used to derive certain combinatorial theorems.

Contents 1 Statements of theorems 1.1 Theorem one 1.2 Theorem two 2 Proofs 2.1 Theorem one 2.2 Theorem two 3 Example 4 References

[edit] Statements of theorems

[edit] Theorem one

For any pair of positive integers n and k, the number of distinct n-tuples of positive integers whose sum is k is given by the binomial coefficient .

[edit] Theorem two

For any pair of natural numbers n and k, the number of distinct n-tuples of non-negative integers whose sum is k is given by the binomial coefficient (for n = k = 0 this coefficient is defined to be 1). This number is also the number of multisets of cardinality k, with elements taken from a set of cardinality n.

[edit] Proofs

[edit] Theorem one

Suppose one has k objects (to be represented as stars) to be placed into n bins such that all bins contain at least one object; one distinguishes the bins (say they are numbered 1 to n) but one does not wish to distinguish the k stars (so configurations are only distinguished by the number of stars present in each bin; in fact a configuration is represented by a n-tuple of positive integers as in the statement of the theorem). Instead of starting to place stars into bins, one starts by placing the starts 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 one knows what is the first star going to the second bin, and the first start going to the third bin, and so on. One can indicate this by placing n − 1 separating bars at some places between two stars (since no bin is 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

There are k − 1 possible places for a bar (bin partition), and one has to choose n − 1 of them to actually contain a bar. Therefore (see combination), there are possible configurations.

[edit] Theorem two

If n > 0, one can apply theorem one to n + k objects, giving configurations with at least one onject in each bin, and then remove one object from each bin to obtain a distribution of k objects into n bins, in which some bins may be empty. An alternative way to arrive directly at the binomial coefficient: in a sequence of n + k − 1 symbols, one has to choose k of them to be stars and the remaining n − 1 to be bars (which can now be next to each other).

The case n = 0 (no bins at all) allows 0 configurations, unless k = 0 as well (no objects to place), in which there is one configuration (since an empty sum is defined to be 0). In fact the binomial coefficient takes these values for n = 0 (since by convention (unlike , which by convention takes value 0 when n = k = 0, which is why the other expression is used in the statement of the theorem).

[edit] Example

For example, if k = 5, n = 4, and our set of size n 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 5 stars (k) and 3 bars (n − 1).

Seven indistinguishable one dollar coins are to be distributed among Amber, Ben and Curtis so that each of them receives at least one dollar. Thus the stars and bars apply with n = 7 and k = 3; hence there are ways to distribute the coins.

[edit] References

Pitman, Jim (1993). Probability. Berlin: Springer-Verlag. ISBN 0-387-97974-3.