Page 586 - Discrete Mathematics and Its Applications

Key Terms and Results 565

11. In how many ways can seven different jobs be assigned for n ≥ 2. [Hint: Note that there are n − 1 choices for the
to four different employees so that each employee is as- first element k of a derangement. Consider separately the
signed at least one job and the most difficult job is as- derangements that start with k that do and do not have 1
signed to the best employee? in the kth position.]
12. List all the derangements of {1, 2, 3, 4}. ∗ 19. Use Exercise 18 to show that
13. How many derangements are there of a set with seven D n = nD n−1 + (−1) n
elements?
for n ≥ 1.
14. What is the probability that none of 10 people receives
the correct hat if a hatcheck person hands their hats back 20. Use Exercise 19 to find an explicit formula for D n .
randomly? 21. For which positive integers n is D n , the number of de-
rangements of n objects, even?
15. A machine that inserts letters into envelopes goes haywire
and inserts letters randomly into envelopes. What is the 22. Suppose that p and q are distinct primes. Use the prin-
probability that in a group of 100 letters ciple of inclusion–exclusion to find φ(pq), the number
of positive integers not exceeding pq that are relatively
a) no letter is put into the correct envelope?
prime to pq.
b) exactly one letter is put into the correct envelope?
∗ 23. Use the principle of inclusion–exclusion to derive a for-
c) exactly 98 letters are put into the correct envelopes?
mula for φ(n) when the prime factorization of n is
d) exactly 99 letters are put into the correct envelopes?
a 2
a 1
a m
e) all letters are put into the correct envelopes? n = p p ··· p m .
1
2
16. A group of n students is assigned seats for each of two ∗ 24. Show that if n is a positive integer, then
classes in the same classroom. How many ways can these
seats be assigned if no student is assigned the same seat n!= C(n, 0)D n + C(n, 1)D n−1
for both classes? + ··· + C(n, n − 1)D 1 + C(n, n)D 0 ,
∗ 17. How many ways can the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 be
where D k is the number of derangements of k objects.
arranged so that no even digit is in its original position?
25. How many derangements of {1, 2, 3, 4, 5, 6} begin with
∗ 18. Use a combinatorial argument to show that the sequence the integers 1, 2, and 3, in some order?
{D n }, where D n denotes the number of derangements
26. How many derangements of {1, 2, 3, 4, 5, 6} end with the
of n objects, satisfies the recurrence relation
integers 1, 2, and 3, in some order?
D n = (n − 1)(D n−1 + D n−2 ) 27. Prove Theorem 1.
Key Terms and Results

TERMS linear nonhomogeneous recurrence relation with constant
coefficients: a recurrence relation that expresses the terms
recurrence relation: a formula expressing terms of a se-
quence, except for some initial terms, as a function of one of a sequence, except for initial terms, as a linear combina-
or more previous terms of the sequence tion of previous terms plus a function that is not identically
zero that depends only on the index
initial conditions for a recurrence relation: the values of the divide-and-conquer algorithm: an algorithm that solves a
terms of a sequence satisfying the recurrence relation before problem recursively by splitting it into a fixed number of
this relation takes effect
smaller non-overlapping subproblems of the same type
dynamic programming: an algorithmic paradigm that finds generating function of a sequence: the formal series that has
the solution to an optimization problem by recursively the nth term of the sequence as the coefficient of x n
breaking down the problem into overlapping subproblems sieve of Eratosthenes: a procedure for finding the primes less
and combining their solutions with the help of a recurrence than a specified positive integer
relation derangement: a permutation of objects such that no object is
linear homogeneous recurrence relation with constant co- in its original place
efficients: a recurrence relation that expresses the terms of
a sequence, except initial terms, as a linear combination of
RESULTS
previous terms
characteristic roots of a linear homogeneous recurrence the formula for the number of elements in the union of two
relation with constant coefficients: the roots of the poly- finite sets:
nomial associated with a linear homogeneous recurrence
relation with constant coefficients |A ∪ B|=|A|+|B|−|A ∩ B|