Math 574
Final Exam
December 18, 1992
Show All Work


  1. Prove by induction: If n>=1, then f3n is even. Here fn is the nth Fibonacci number defined by f1 = 1, f2 = 1, and for n >= 3, fn = fn-1 + fn-2.

  2. (a). How many 4-element subsets of {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} are there? Simplify your answer to a simple integer.

    (b). How many 4-element subsets of {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} have an even sum?

    (c). How many subsets of {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} contain exactly 3 even integers (and any number of odd integers )?

  3. (a). How many divisors of n = 243557 are there (including 1 and n)?

    (b). How many sequences of length 12 whose terms are chosen from {a, b, c, d, e, f} have exactly 4 a's and 3 b's?

  4. (a). A box contains a dozen eggs. Each egg is to be colored either red, blue, yellow, or green. Also, every color must be used for at least one egg. How many different ways can this be done? (For example, one way would be to use 3 red eggs, 5 blue eggs, 2 yellow eggs, and 2 green eggs.)

    (b). How many solutions in non-negative integers are there to a + b + c + d + e = 20 with a <= 5 and b <= 8?

  5. (a). How many permutations of 1, 2, 3, 4, 5, 6, 7, 8 have 4 appearing somewhere to the         left of 5, 5 to the left of 6, and 6 to the left of 7?
    Example: 3 8 4 7 9 5 2 1 6

    (b). How many permutations of a, b, c, d ,e, f, g, h, i, j (that's ten letters.) have abc appearing together in some order and ghij appearing together in some order. (For example e b c a f d h i j g )

  6. (a). How many ways are there to place 12 or fewer identical balls into 5 distinct boxes?

    (b). How many ways are there to arrange 5's and 5 y's so that no three x's are adjacent?

  7. (a). Using characteristic equations, find a formula for the solution of
    an = 7an-1 - 10an-2, a0 = -4, a1 = 1.

  8. Using characteristic equations, find a formula for the solution of
            an = 6an-1 - 9an-2, a0 = 1 a1 = 9.
    (a). How many functions from {1, 2, 3, 4 } to {a, b, c, d, e, f } are there?

    (b). How many of these functions are 1-1?

    (c). How many of these functions are onto?

  9. Let a0 = 2, and for n >= 1 let an = 3an-1 + 5n-3. Find the generating function for an.

    (a). Let an denote the number of sequences of length n using the eight letters
    a, b, c, d, e, f, g, h that have an even total number of a's, b's and c's. Find a recurrence relation for an and appropriate initial conditions to determine all the values of an.
    (b). Let denote the number of sequences of length n using 1, 2, 3, 4, 5, 6, 7, 8, 9 that have no two odd numbers adjacent. Find a recurrence relation for an and appropriate initial conditions to determine all the values of an.

  10. How many permutations of 1, 2, 3, 4, 5, 6, 7, 8, 9 have no even number appearing in its proper position? (i.e. 2 is not in the second position, 4 is not in position 4 etc.)

  11. Suppose that 8 cards are dealt from a standard deck of 52.
    (a). What is the probability they consist of four distinct pairs?
    (Example: 2 K's, 2 J's, 2 5's, and 2 4's).

    (b). What is the probability they consist of 3 of one suit, 3 of a second suit and 2 of a
    third suit? (Maybe 3 diamonds, 3 clubs and 2 hearts.)

  12. What is the probability of getting a total of 12 in a roll of five dice?


  13. (a). What is the value of ?

    (b). What is the coefficient of x8 in the expansion of ?

  14. (a). What is the coefficient of x2y3z6 in the expansion of (x -3y +2z)11?

    (b). What is the sum of all the coefficients of the terms in this expansion?

    (c). How many distinct terms are there in this expansion?


  15. How many ways are there to place 3 X's and 9 Y's into the squares below if each square can contain any number of X's or Y's but not both an X and a Y?
                           


  16. Refer to the grid below.
                   

    (a). How many ways are there to move from the point A in the grid below to point B?

    (b). How many of these paths pass through exactly one of C or D?



Name ____________________