Chapter Review
469
for t = 1, 2,..., n - 1. Make a table of the Stirling numbers of the first kind for n =
1,2,3,4,5,6.
47. For a positive integer t, define [x]t = x(x - 1) ... (x - t + 1). We can represent xn
as a linear combination of [x1t, where n = 1, 2, 3 ... , and t = 0, 1, 2 ... , n. The
coefficients for this expansion are denoted as S(n, t) and are known as the Stirling
numbers of the second kind. Thus, for any n, we can write
n
xn
E S(n, t)[x],
t=O
The numbers S(n, t) can be defined for n = 1, 2, 3,... as S(n, 0) = 0; S(n, n) = 1;
and
S(n, t) = tS(n - 1, t) + S(n - 1, t - 1)
for 1 < t < n - 1. Make a table of the Stirling numbers of the second kind for n
1, 2, 3, 4,5, 6.
48. Still another application of the Principle of Inclusion-Exclusion: Prove that
m
Z(.-1)r C(m, r) (m - r)n
r=O
counts the number of surjections from a set of size n to a set of size m. Use this result
to determine the number of ways to discharge eight people who get on an elevator at
the ground floor of a four-story building. The elevator discharges its last passenger on
the fourth floor.
49. Still another application of the Principle of Inclusion-Exclusion: Let
X1 X2 ... Xn-- Xn
be a permutation of {1, 2, 3, .
n - 1, n} such that for 1 < i < n, there is no xi = i.
A permutation with this property is called a derangement. We denote the set of derangements on n elements as D,. Find a formula for the number of derangements on
1, 2 ..... n - 1, n for any n e N. Evaluate this formula for n = 2, 3, 4, 5, 6. Construct
all derangements for n = 2, 3. (Hint: see example 12 in Section 7.5.7.)
Chapter Review
Most counting results are based on two fundamental principles, the Multiplication Principle and the Addition Principle. Permutations (orderings of elements) and combinations
(sets of elements) provide a foundation for analyzing problems. Solution techniques for
counting problems include counting the complement, decomposing a problem into disjoint
subproblems, and using the Pigeon-Hole Principle. Counting problems are quite different
when the objects are not distinct. Results about counting permutations and combinations
involving repeated elements are presented. A more practical problem for experimentation is
to choose a random permutation of n elements from the n! possible permutations. A technique for constructing a random permutation is given. In quite a different context, it is
necessary to expand both powers of binomials and powers of multinomials. Both of these
469
for t = 1, 2,..., n - 1. Make a table of the Stirling numbers of the first kind for n =
1,2,3,4,5,6.
47. For a positive integer t, define [x]t = x(x - 1) ... (x - t + 1). We can represent xn
as a linear combination of [x1t, where n = 1, 2, 3 ... , and t = 0, 1, 2 ... , n. The
coefficients for this expansion are denoted as S(n, t) and are known as the Stirling
numbers of the second kind. Thus, for any n, we can write
n
xn
E S(n, t)[x],
t=O
The numbers S(n, t) can be defined for n = 1, 2, 3,... as S(n, 0) = 0; S(n, n) = 1;
and
S(n, t) = tS(n - 1, t) + S(n - 1, t - 1)
for 1 < t < n - 1. Make a table of the Stirling numbers of the second kind for n
1, 2, 3, 4,5, 6.
48. Still another application of the Principle of Inclusion-Exclusion: Prove that
m
Z(.-1)r C(m, r) (m - r)n
r=O
counts the number of surjections from a set of size n to a set of size m. Use this result
to determine the number of ways to discharge eight people who get on an elevator at
the ground floor of a four-story building. The elevator discharges its last passenger on
the fourth floor.
49. Still another application of the Principle of Inclusion-Exclusion: Let
X1 X2 ... Xn-- Xn
be a permutation of {1, 2, 3, .
n - 1, n} such that for 1 < i < n, there is no xi = i.
A permutation with this property is called a derangement. We denote the set of derangements on n elements as D,. Find a formula for the number of derangements on
1, 2 ..... n - 1, n for any n e N. Evaluate this formula for n = 2, 3, 4, 5, 6. Construct
all derangements for n = 2, 3. (Hint: see example 12 in Section 7.5.7.)
Chapter Review
Most counting results are based on two fundamental principles, the Multiplication Principle and the Addition Principle. Permutations (orderings of elements) and combinations
(sets of elements) provide a foundation for analyzing problems. Solution techniques for
counting problems include counting the complement, decomposing a problem into disjoint
subproblems, and using the Pigeon-Hole Principle. Counting problems are quite different
when the objects are not distinct. Results about counting permutations and combinations
involving repeated elements are presented. A more practical problem for experimentation is
to choose a random permutation of n elements from the n! possible permutations. A technique for constructing a random permutation is given. In quite a different context, it is
necessary to expand both powers of binomials and powers of multinomials. Both of these