CS206 -Discrete Mathematics II
Instructor: Chitoor V.Srinivasan
PROBLEM SET 3 SOLUTIONS

  1. (a). Let   tex2html_wrap_inline28   be the number of permutations of a set with n elements. Clearly,   tex2html_wrap_inline30 . The first element can be chosen in n ways, and the remaining n-1 elements can be arranged in   tex2html_wrap_inline32   ways. Thus,   tex2html_wrap_inline34 .

    (b). tex2html_wrap_inline36 .

  2. Let   tex2html_wrap_inline28   be the number of ways of getting stamps valued n cents. The initial conditions are,   tex2html_wrap_inline40 ,  and   tex2html_wrap_inline42   for all other i from 0 through 9. Stamps for n cents may be made up by adding a 10 cent stamp to some stamp(s) totalling (n-10) cents, a 6 cent stamp to some stamp(s) totalling (n-6) cents, or a 4 cent stamp to some stamp(s) totalling (n-4) cents. Thus,   tex2html_wrap_inline44 .
  3. tex2html_wrap_inline46

    (a).
    Since tex2html_wrap_inline48 ,   tex2html_wrap_inline50 ,   tex2html_wrap_inline52

    (b).
    tex2html_wrap_inline54

    (c).
    From the formula, tex2html_wrap_inline56 .

  4. There are 200 integers divisible by 5,   tex2html_wrap_inline58   divisible by 7, and   tex2html_wrap_inline60   which are divisible by both 5 and 7. The answer is 1,000 minus the number of integers which are divisible by 5 or 7, which is 1000 - (200 + 142 - 28) = 686.

  5. The answer is the number that are divisible by 3 minus the number that divisible by both 3 and 7 which is   tex2html_wrap_inline62   = 333,333 - 47,619 = 285,714

  6. The largest integer  n  such that   tex2html_wrap_inline66   is  31. The largest integer  m  such that   tex2html_wrap_inline72   is  10. The number of integers less than 1000 which are both squares and cubes is 3, since   tex2html_wrap_inline76  . Hence, the answer is  (31 + 10 - 3) = 38.

  7. Consider  fish  and  rat  as single tokens. The number of permutations containing  fish  is  (26 - 4 + 1)! = 23!, the number of permutations containing the token  rat  is similarly,  (26 - 3 + 1)! = 24!,  and the number of permumations containing both  fish  and  rat  is  (26 - 7 + 2)! = 21!. The total number of permutations not containing  fish  or  rat  is, the total number of permutations of the 26 letters minus the number of permutations containing  fish  or  rat. This is  26! - (23! + 24! - 21!).

  8. Let   tex2html_wrap_inline108   for   tex2html_wrap_inline110   be the seven sets. There will be seven singleton terms,   tex2html_wrap_inline112 ,  C(7,2) double terms   tex2html_wrap_inline114 ,  C(7,3) triples   tex2html_wrap_inline116 ,  C(7,4) quadruples and C(7,5) quintuples. For j > 5 all intersections of j sets will be empty. Hence, the answer is   tex2html_wrap_inline120 .

  9. This is   tex2html_wrap_inline122 minus the total number of bit strings that do contain four consecutive 1's. The bit strings that do contain 4 consecutive ones are

    displaymath26

    Hence, the answer is   tex2html_wrap_inline124 .

    Note that finding the number of length n bit strings not containing 4 consecutive 1s is in general hard to solve for arbitrary n tex2html_wrap_inline126 6.