Final Exam Review I

Final Exam:  Fri May 2, 2008, 10:00--12:00, in our usual room Wells C-305.

• Basic Enumeration (Ch 2.1−2.3)
  • Product Principle. Typical Problems:  n^k,  k!,  n^k,  (n | k), 
  • Multi-choose numbers:  ((n | k)) = (n+k−1 | k) = (n+k−1 | n−1), bins-and-beans correspondence
  • Principle of Inclusion-Exclusion (PIE):

    |Agood|	=	| A − (A1∪...∪Ar) |
    	=	|A|  −  ∑i |Ai|  +  ∑ i < j |Ai∩Aj|  − ... +  (−1)k|A1∩...∩Ar|

    Here A is a large set of objects, A₁,...,A_r are subsets of bad objects, and our goal is to count the good objects.We use this method when the good objects are difficult to count directly, but the bad objects are easy to count.

• Generating functions (Ch 2.4.1−2.4.5)
  • Goal: Given a combinatorial sequence {a_k}_k≥0, find an explicit formula for a_k .
  • Step 1:  Find a simple formula for the generating functionf(x) = ∑_k≥0 a_kx^k .
    • Often with a_k counts the objects of size k in some (usually infinite) set A. The Product Principle for objects in A gives a product expression for f(x), often involving Geometric Series (1+x+x²+...) = 1/(1−x) .
    • Recurrence for a_k implies an equation involving f(x). Solve this equation for f(x).
  • Step 2:  Given a formula for f(x), find a formula for its coefficients a_k
    • Taylor's Theorem: a_k = f^(k)(0)/k!
    • Binomial Theorem (proved using Taylor's Thm)
      (1+z)ⁿ = ∑_0≤k≤n (n | k) z^k
      (1−z)⁻ⁿ = ∑_k≥0 ((n | k)) z^k  
    • Partial fraction decomposition: 1/(1−ax)(1−bx) = A/(1−ax) + B/(1−bx)

Final Review Problems I.  

1. Basic enumeration of combinations. Count the possiblities for each type of objects.
   In each case, we have k elements of n kinds, with various conditions on ordering and repeats.
   1. Ordered list, repeats allowed.
   2. Ordered list, no repeats.
   3. Ordered list, each kind appearing at least once.
   4. Unordered set, no repeats.
   5. Unordered multi-set, repeats allowed.
   6. Unordered multi-set, each kind appearing at least once.

2. Counting solutions of n₁ + n₂ + n₃ = 10.
   1. Count the triples of whole numbers n₁,n₂,n₃ ≥ 0  satisfying the equation n₁ + n₂ + n₃ = 10.  Hint: Put 2 bars between 10 stars.
   2. Same, but with n₁,n₂,n₃ ≥ 1. Hint: Interpret this also in terms of stars-and-bars.
   3. Extra Credit: Same, but suppose the numbers are rolls of the dice, so that each 1 ≤ n_i ≤ 6. Hint: PIE, combined with the previous solution.

3. Re-do the above problem using generating functions.
   1. Let a_k be the number of triples of whole numbers n₁,n₂,n₃ ≥ 0  satisfying the equation n₁ + n₂ + n₃ = k.  Evaluate f(x) = ∑_k≥0 a_kx^k using the Product Principle, and use this to get an expression for a_k . Compare a₁₀ with your answer above.Hint: Perform an algebraic substitution on the logical expression:(n₁ = 0 or n₁ = 1 or n₁ = 2 or ...)and (n₂ = 0 or ....) and (n₃ = 0 or ...)
   2. Same, but with n₁,n₂,n₃ ≥ 1.
   3. Extra Credit: Same, but with 1 ≤ n_i ≤ 6. Hint: Expand the top, and take each term over the denominator.

4. Give a formula for the sequence {a_k}_k≥0 defined by the recurrence   a_k = 3a_k−1 − 2a_k−2   for k ≥ 2, and a₀ and a₁ are arbitrary constants.
   Hint: You can check your answer by computing a_k directly in the case a₀ = a₁ = 1 , and comparing with your general answer.