Ball-and-urn
The ball-and-urn technique, also known as stars-and-bars, sticks-and-stones, or dots-and-dividers, is a commonly used technique in combinatorics.
It is used to solve problems of the form: how many ways can one distribute indistinguishable objects into
distinguishable bins? We can imagine this as finding the number of ways to drop
balls into
urns, or equivalently to arrange
balls and
dividers. For example,
represent the ways to put
objects in
bins. The number of ways to do such is
.
More generally, the number of ways to put objects into
bins is
.
The number of ways to put objects into
bins, where each bin must have at least 1 object in it, is
.
Restrictions
Let's say that we want to put objects in
bins, but there must be at least
objects in each bin. Without the restriction, we can set the following equation up:
. We know that each
(the bins) must have at least
objects in them, so we can subtract
from
, since that's how many objects are left. This means that there are
ways to distribute the objects.
Well what if we can have at most objects in each bin? We can use the following formula to find this:
This can be derived using the Principle of Inclusion-Exclusion.
Reasoning 1
Arranging *'s and
|'s is the same as saying there are
positions:
and you want to fill
of them with *'s and the rest of them with |'s. Thus you are choosing
positions out of
total positions, resulting in a total of
ways.
Reasoning 2
If you could only put one ball in each urn, then there would be possibilities; the problem is that you can repeat urns, so this does not work. You can, however, reframe the problem as so: imagine that you have the
urns (numbered 1 through
) and then you also have
urns labeled "repeat 1st", "repeat 2nd", ..., and "repeat
-th". After the balls are in urns you can imagine that any balls in the "repeat" urns are moved on top of the correct balls in the first
urns, moving from left to right. There is a one-to-one correspondence between the non-repeating arrangements in these new urns and the repeats-allowed arrangements in the original urns.
For a simple example, consider balls and
urns. The one to one correspondence between several of the possibilities and the "repeated urns" version is shown. Since there are 4 balls, these examples will have three possible "repeat" urns. For simplicity, I am listing the numbers of the urns with balls in them, so "1,1,2,4" means
balls in urn
in urn
and
in urn
The same is true for the "repeat" urns options but I use the notation
etc.
(no repeats).
.
,
.
,
.
Since the re-framed version of the problem has urns, and
balls that can each only go in one urn, the number of possible scenarios is simply
Note: Due to the principle that
, we can say that
.