Ball-and-urn

Revision as of 20:31, 27 February 2016 by VivekA (talk | contribs)

The ball-and-urn technique, also known as stars-and-bars, is a commonly used technique in combinatorics.

It is used to solve problems of the form: how many ways can one distribute $k$ indistinguishable objects into $n$ bins? We can imagine this as finding the number of ways to drop $k$ balls into $n$ urns, or equivalently to drop $k$ balls amongst $n-1$ dividers. The number of ways to do such is ${n+k-1 \choose k}$, given there can be $0$ balls in an urn. However, if there can only be a positive amount of balls in an urn, then the number of ways to do such is ${n-1 \choose k-1}$