Stars and bars (combinatorics)

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

Theorem one

There are ${{n-1} \choose {k-1}}$ distinct positive integer-valued vectors of length $k$ whose components sum to $n$.

Theorem two

There are ${{n+k-1} \choose {k-1}}$ distinct nonnegative integer-valued vectors of length $k$ whose components sum to $n$.

Derivation of theorem one

Imagine we have $n$ indistinguishable objects to be placed into $k$ bins such that all bins contain at least one object. We may represent the objects with side-by-side stars,

★★★★★★

(seven objects)

and we may represent the $k-1$ partitions between the $k$ bins with bars:

★★★★	|	★	|	★★
(an allocation into three bins containing 4, 1, and 2 objects)

In fact for $n$ stars (objects), there are $n-1$ possible places a bar (bin partition) could be placed such that all bins contain at least one object. Therefore (see combination), there are

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

ways to allocate $n$ objects to $k$ bins such that each bin contains at least one object. The theorem follows from the fact that we may represent the number of objects in the bins by a vector of $k$ positive integers.

Derivation of the theorem two

This follows from applying theorem one to $n+k$ objects, and ensuring that exactly one of each of the $k$ additional objects ends up in its own bin.

Example

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

${{7-1} \choose {3-1}}=15$

ways to distribute the coins.

References

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