
48 Combinatorics of Permutations, Second Edition
where P (n, k) is the probability that at the end of the trials there are k
empty boxes. Then it can be proved that
B
r
(n)=S(n, n − r, l)
(n − r)!
n!
l
by showing that both sides satisfy the same recurrence relations. Then,
by the formula P (k, n)=
n
r=k
(−1)
r−k
r
k
B
r
(n), our claim follows.
4. The volume of R
n,k
is equal to A(n, k)/k!. A nice combinatorial proof
was given by Richard Stanley [241]; though the result was probably
known by Laplace. The main element of Stanley’s proof is the following
measure-preserving map. It is straightforward that A(n, k)/k!isthe
volume of the set S
n,k
of all points (x
1
,x
2
,