Discrete Mathematics for Computer Science

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 de-

rangements 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 Prin-
ciple 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 tech-
nique 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