Distribution Problems
The property that characterizes a distribution (occupancy) problem is that a ball (object) must go into
exactly one box (bin or cell). This amounts to a function from balls to bins.
n distinguishable boxes n indistinguishable boxes
empty box allowed no box empty empty box allowed no box empty
r disting. balls n
r
n!
_
r
n
_
n
i=1
_
r
i
_ _
r
n
_
r indisting. balls
_
r + n 1
r
_ _
r 1
n 1
_
n
i=1
r
i
r
n
We now explain the entries working from right to left.
_
r
n
_
: This is by denition. It is the same as the number of n-subsets of r balls.
n
i=1
_
r
i
_
: Use the previous and the addition principle on the cases: r balls in 1 box none empty, r balls
into 2 boxes none empty, etc.
n!
_
r
n
_
: Put the balls into indistinguishable boxes (
_
r
n
_
ways). The boxes are now distinguishable by
their contents. Then put labels on the boxes (n! ways). Later we show by inclusion-exclusion that:
n!
_
r
n
_
=
n
i=0
(1)
i
_
n
i
_
(n i)
r
which provides an alternative to the double recursion formula below for computing
_
r
n
_
.
n
r
: Just an r-sequence for each ball there are n ways to put it in a box.
r
n
: This is by denition. It is the number of partitions of r into n parts, that is, write r as a sum
of natural numbers, order unimportant. For example, for r = 4, n = 2 the partitions are: 4 = 3 + 1 and
4 = 2 + 2. Thus
4
2
= 2. The partition 3 + 1 says put 3 balls in one box and 1 in the other.
n
i=1
r
i
: Use the previous and the addition principle on the cases: r balls in 1 box none empty, r balls
into 2 boxes none empty, etc. It is the number of partitions of r into n or fewer parts. For example, 4 has
partitions 4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1.
_
r+n1
r
_
=
_
r+n1
n1
_
: This is an arrangement of r balls and n 1 dividers. Choose the positions for the
balls or the dividers, whichever you prefer.
_
r1
n1
_
: First take n balls and put one ball in each box. This leaves r n balls to distribute with no
restrictions the previous case. Thus there are
_
(rn)+n1
n1
_
ways.
Double recurrence relations
These can be used to compute the above quantities. Proofs are provided elsewhere.
Choose: C(r, n) =
_
r
n
_
has recurrence
_
r
n
_
=
_
r1
n
_
+
_
r1
n1
_
called Pascals formula.
Partition: p(r, n) =
r
n
has recurrence
r
n
rn
n
r1
n1
.
Subset: S(r, n) =
_
r
n
_
has recurrence
_
r
n
_
= n
_
r1
n
_
+
_
r1
n1
_
.
Cycle (dened below): c(r, n) = s(r, n) =
_
r
n
has recurrence
_
r
n
= (r 1)
_
r1
n
+
_
r1
n1
.
The boundary (initial) conditions are that each is 0 if either n = 0 or r = 0 but 1 if both n = 0 and
r = 0, with the exception that
_
r
0
_
= 1 regardless of r. Also
s
n
= 0 if s < 0, a required initial condition since
r n above could be negative.
_
r
n
_
is called a Stirling number of the second kind while
_
r
n
is called a Stirling number of the rst kind.
_
r
n
is the number of permutations of r objects that have n cycles. For example, permuting 1-2-3-4-5
to 2-4-5-1-3 takes the 1-st object to 4-th position, 4-th to 2-nd and 2-nd to 1-st (and so 1, 4, 2 is called a
cycle). Also it takes the 3-rd object to 5-th position and 5-th to the 3-rd (forming a second cycle 3, 5). This
permutation is said to have two cycles. 1-2-3-4-5 to 2-3-4-1-5 also has two cycles. There are actually 50
5-permutations that have 2 cycles, so
_
5
2
= 50.