HOMEWORK 8, Due November 14.

Practice Problems: Rosen, Chapter 4.1: 7, 9, 17, 33 
------------------------------------------------------------


Turn in Problems:

(1)  Consider binary bit strings with 14 bits.  There are
     214 total such strings.  (only a numerical answer or
     formula is required.  You could do these mathematically, or, i
     suppose, write program to count all possible strings that fit the
     following constraints.  Full credit given for numerical answers
     or explicit formulas. 2/3's credit given for correct recursive formulas.

    (a) How many bit strings are there with alternating 0's and 1's?

    (b) How many bit strings start with 101 or end with 101?

    (c) How many bit strings are there without 2 consecutive 1's?

    (c) How many bit strings are there without 3 consecutive 1's?
 
(2) Find the number of integers between 1 and 10,000 (including 1 and 10,000),
      which are not divisible by 4,5, or 6.

(3) Write an expression for the sum of the "odd" binomial
      coefficients: that is, compute:
 
            C(n,1) + C(n,3) + C(n,5) + C(n,7) ... + C(n,n)

       You may assume that n is odd.  (Hint, try to come up with a
        combinatorial proof... think about what this expression may be
        counting, and reason (perhaps in english, but be specific) about that
        set and its size).

(4) How many different strings can be made from the letters in MISSOURI when:
 
     (a) using all the letters?

     (b) using all the letters when the "OU" must be consecutive?