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

  1. Consider 987, 45, and 123 as single tokens. Let A be the set of permutations that begins with 987, B be the set that contains 45 in the 5'th and 6'th positions, and C be the set that ends with 123. tex2html_wrap_inline252 ,   tex2html_wrap_inline254 ,   tex2html_wrap_inline256 ,   tex2html_wrap_inline258 ,   tex2html_wrap_inline260 ,   tex2html_wrap_inline262 , and   tex2html_wrap_inline264 . By the inclusion-exclusion principle, tex2html_wrap_inline266 tex2html_wrap_inline266

  2. A function F from A to B is called onto-function, if and only if for every element tex2html_wrap_inline268 there is an element tex2html_wrap_inline270 with F(a) =b. According to Page 331(Rosen's book) Theorem 1, here we have  m=7, n=5  and we find the number of onto-function from set A with seven elements to set B with five elements is:

    displaymath204

  3. This is a problem of derangements. According to page 332 Theorem 2, we have following results.
    (a).
    The number such that all  7  letters go into incorrect envelopes is :   tex2html_wrap_inline278  

    (b).
    If the machine exactly inserts one letter correctly, it has 7 letters to choose first and has   tex2html_wrap_inline280   ways to insert all of the remaining six letters incorrectly. So the answer is   tex2html_wrap_inline282  .

    (c).
    If the machine exactly inserts five letter correctly we have C(7,5) ways to choose these. There is only one derangement of the remaining two letters. Hence, the answer is C(7,5).

    (d).
    Zero ways to have exactly six letter correct and one incorrect.

    (e).
    One way.

  4. Recall that a composite integer is divisible by a prime not exceeding its square root. Thus, the composite integers between 1 and 150 must have a prime factor not exceeding 12. The only primes less than 12 are 2, 3, 5, 7, and 11, (note: 1 is usually defined not to be prime). The primes between 1 and 150 are these five primes plus the remaining integers greater than 1 that are not divisible by any of 2, 3, 5, 7, or 11.

    Let   tex2html_wrap_inline284   be the set of integers (from 2 through 150) that are divisible by i for i=2,3,5,7,11. The number of remaining prime numbers are 149 (since there are 149 integers from 2 through 150) minus the size of the union of the   tex2html_wrap_inline284 . We can calculate the size of this union using inclusion-exclusion.

    The number of integers not exceeding 150 (and greater than 1) that are divisible by all the primes in a subsets of 2, 3, 5, 7, 11 is   tex2html_wrap_inline288 ,  where  N  is the product of the primes in this subset. This follows, since any two of the these primes have no common factor. Consequently, the number of primes is

    eqnarray39

    = 5 + 149 -75-50-30-21-13 +25+15+10+6+10+7+4+4+2+1 -5-3-2-2-1-0-1-0-0-0 + 0+0+0+0+0-0 = 35 Hence, there are 35 primes between 1 and 150.

  5. Let   tex2html_wrap_inline294   be the property that 0 is in its original situation, let   tex2html_wrap_inline296   be the property that 2 is in its original situation, and similiarly use   tex2html_wrap_inline298   for 4,   tex2html_wrap_inline300   for 6,   tex2html_wrap_inline302   for 8. According to inclusion-exclusion principle,

    eqnarray70

  6. The generating function for making change for k dollars using i-dollar bills is

    displaymath205

    Hence, the required generating function for making  k  dollars is

    displaymath206

  7. Since we have

    displaymath207

    let  y=3x , we have

    displaymath208

    This is the required generating function.

  8. Since   tex2html_wrap_inline308   is the product of  n  terms, where each term is   tex2html_wrap_inline312 . In order to get the coefficient   tex2html_wrap_inline314  , we get   tex2html_wrap_inline316   from the 1st term, get   tex2html_wrap_inline318   from the 2nd term,   tex2html_wrap_inline320 ,  and get   tex2html_wrap_inline322  , from the  nth  term, where   tex2html_wrap_inline326   satisfy,

    displaymath209

    This is a typical partition problem and there are   tex2html_wrap_inline328   ways to do this partitioning.

  9. Let G(x) be the generating function for the sequence   tex2html_wrap_inline330 ,  that is,   tex2html_wrap_inline332  .

    displaymath210

    displaymath211

    displaymath212

    displaymath213

    displaymath214

    displaymath215

    displaymath216

    tex2html_wrap_inline330 is the coefficient of tex2html_wrap_inline336 .

  10. Let G(x) be the generating function for the sequence   tex2html_wrap_inline330 ,  that is,   tex2html_wrap_inline332 .

    displaymath217

    displaymath218

    displaymath219

    and since we have   tex2html_wrap_inline342 ,  hence

    displaymath220

    displaymath221

    displaymath222

    tex2html_wrap_inline330   is the coefficient of   tex2html_wrap_inline346   which is   tex2html_wrap_inline348 .

  11. Let G(x) be the generating function for the sequence   tex2html_wrap_inline330  , that is,   tex2html_wrap_inline332 .

    displaymath223

    displaymath224

    displaymath225

    displaymath226

    displaymath227

    tex2html_wrap_inline330   is the coefficient of   tex2html_wrap_inline346 . Hence,   tex2html_wrap_inline358 .