Stars and Bars
is a mnemonic I learned in high school math team
for a common combinatorial
How many ways can k indistinguishable balls be placed in n distinguishable boxes?
To answer this, you take a 'star' for each of the k balls, and n - 1 'bars' denoting the separators between the n boxes. Then each arrangement of the balls corresponds to a permutation of these k + n - 1 objects. For instance, when k = 6, n = 4, one of the arrangements might be written (3, 0, 2, 1); that is, 3 balls in the first box, etc. This arrangement corresponds to the string
* * * | | * * | *
of 6 stars and 3 bars. But now that we have only two kinds of objects, it is easy to count the number of arrangements: there is one arrangement for every choice of which k out of the k + n - 1 slots receive a star. Thus the answer is the binomial coefficient C(k + n - 1, k) = C(k + n - 1, n - 1).
Among other things, this number counts the multi-indices of dimension n and weight k, which is the dimension of the space Symk(Rn) of symmetric tensors of type (k, 0) or (0, k) on Rn. This space comes up when you formulate multivariable calculus in a general context, as the kth derivative of a function Rn → R is a symmetric (k, 0) tensor.
A good place to learn more about this kind of problem is Concrete mathematics by Ronald Graham, Donald Knuth and Oren Patashnik. Richard Stanley's two-volume masterwork Enumerative combinatorics is a more advanced reference; the stars-and-bars problem is one component of what he calls the Twelvefold Way of basic counting.