Discrete Mathematics for Computer Science

472 CHAPTER 7 Counting and Combinatorics

4. How many r - digit sequences composed of O's, l's, 2's, and 3's are there in which

each of 1, 2, and 3 appears at least once?

5. How many solutions are there for x1 + X2 + x 3 + X4 = 30 with -10 < xi < 20 for
   1 <i <4.


6. Find the number of solutions for x, + x 2 + X3 + X4 = 18 with xi < 7 for 1 < i < 4.


7. How many solutions in integers are there for

X1 + X2 + X3 =^14

if -2 < x 1 < 4; x 2 < 5; and2<x 3 <6?

(Hint: Let U be the set of solutions satisfying the conditions xi > -2; x2 > 0; X3 >_ 2.

Treat the -2 as if you could put -2 elements in box 1, and then solve the equation

for 16. The upper bounds are handled by the Principle of Inclusion-Exclusion us-

ing the sets A 1 , {(X, x2, x3) e U : Xl > 5}, A 2 = {(Xl, X2, x3) E U : X2 > 6}, and

A 3 = {(X, x 2 , x3) E U : x3 > 71.

8. Give a combinatorial proof of P(n, r) = rP(n - 1, r - 1) + P(n - 1, r).

9. Prove that Y=0 C(m, k) • C(n, r - k) = C(m + n, r). This is called Van Der-

monde's Identity.

10. Prove that C(n, m) • C(m, k) = C(n, k) • C(n - k, m - k). This is called Newton's
    Identity. Prove that C(n, k) • C(n - k, m) = C(n, m) • C(n - m, k).


11. Count the number of ways to choose 10 elements from among three pears, four apples,
    and five bananas. (Hint: Ai = the set of 10-combinations with more than three pears.
    A 2 = the set of 10-combinations with more than four apples. A 3 = the set of 10-
    combinations with more than five apples.)


12. How many ways can the 26 letters of the alphabet be permuted so that none of the
    patterns car, dog, pun, or byte occurs?


13. Prove that () (n) .-(nf+'r) both algebraically and combinatorially.


14. How many derangements are there of the set {1, 2, 3, 4}? List all these permutations.


15. A "word" is a string of one or more lowercase letters. How many words can be formed
    from the letters of the word ... In how many words will p and i occur together? In how
    many will h and y not occur together? How many words can be formed from the letters
    in the word zigzag where no two consecutive letters are the same?

7.12.4 Using Discrete Mathematics in Computer Science

1. In Section 7.3.3, we counted the number of UNIX passwords of length six, except that
   we left a factor of 60 underived.
   (a) Derive the factor of 60.
   (b) Count how many UNIX passwords there are of length six, seven, or eight.
   (c) At a speed of 200,000 words a second, how long would it take to try all the pass-
   words you counted in part (b)?


2. Assume that a computer stores each file at consecutive locations on a hard disk, with
   files written on both sides of the disk. When a large file is erased and a smaller file is
   written in its place, only some of the space is used. If the original disk had files written
   on both sides, a small block of space is left unused. After many changes to the disk-
   that is, after a sequence of additions and deletions mixed together-there may be many