Final Exam Review I

On this webpage I denote (n choose k) by (n | k) and (n multi-choose k) by ((n | k)). These are not standard symbols: use the vertical notation in your own writing.

• Basic Enumeration (Ch 2.1, 2.2, 2.5)
  • Basic Principles
    • Sum: split objects into disjoint cases
    • Product: analyze each object into a sequence of independent choices
    • Difference: good objects = all objects minus bad objects
    • Quotient: number of columns = number in rectangle divided by number in each row
    • Transformation: change the objects into equivalent data which are easier to count
    
    Four Basic Problems:   n!,  n^k,  (n | k) = n^k/k!,   ((n | k))
  • Multi-choose numbers:  ((n | k)) = (n+k−1 | k) = (n+k−1 | n−1) using bins-and-beans correspondence
  • Principle of Inclusion-Exclusion (PIE, negative counting):

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

    We count a set of good objects A_good, starting with a large set A of all objects and excluding sets of bad objects A₁ , ... , A_r .
  • Pascal's Triangle (n | k) = (n−1 | k) + (n−1 | k−1)
    Binomial Theorem: (a+b)ⁿ = ∑_k=0ⁿ (n | k)a^kb^n−k
  • Transformations
    • Bins-and-beans: proves ((n | k)) = (n−1 + k | k)
    • Multiplicity: writes a multi-set by counting how many of each kind
    • Position: transforms binary sequences (like coin-flips) into sets
      Proves the total number of subsets of an n-element set is 2ⁿ

• Generating functions (Ch 2.6.1−2.6.5)
  • Goal: Given a combinatorial sequence {a_k}_k≥0, find an explicit formula for a_k .
  • Step 0:  If you start with a single counting problem a, generalize it to a family of problems a_k for k = 0,1,...,n or all k ≥ 0 .
  • Step 1:  Find a simple formula for the generating function f(x) = ∑_k≥0 a_kx^k .
    • Often 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! , where f^(k)(x) means the k^th derivative.
    • Binomial Theorem (proved using Taylor's Thm)
      (1+z)ⁿ = ∑_0≤k≤n (n | k) z^k
      (1−z)⁻ⁿ = ∑_k≥0 ((n | k)) z^k (negative exponent)
    • Geometric Series
      ∑_k≥0 z^k = 1/(1−z)
      1 + z + z² + ... + zⁿ = (1−zⁿ⁺¹) / (1−z)
    • Partial fraction decomposition: (cx + d) / (px² + qx + r)  =   A/(1−ax) + B/(1−bx),
      where the two sides have the same vertical asymptotes (roots of the denominators).

• Special sequences:
  • Fibonacci 0,1,1,2,3,5,8,13,...;   F_k = F_k−1 + F_k−2 ;   F_k = ¹⁄_√5 (φⁿ − ψⁿ) for φ = ½(√5 + 1), ψ = ½(√5 − 1)
  • Catalan 1,1,2,5,14,42,...;   C_k = ∑_i=0^k−1 C_iC_k−i−1 ;   C_k = ¹⁄_(k+1) (2k | k)

See the Old Notes.

Final Review Problems I.   See also Midterm Review Problems.

1. Basic enumeration of combinations.
   Count how many ways to choose k elements of n kinds: the elements may be ordered or not, with repeats or not. The example gives the case k = 2, n = 3.
   1. Ordered list, repeats allowed: (1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2) (3,3)
   2. Ordered list, no repeats: (1,2) (1,3) (2,1) (2,3) (3,1), (3,2)
   3. Ordered list, each of the n kinds appearing at least once: no such if k < n. Hint: Use PIE with A = {lists from (a)}.
   4. Unordered set, no repeats: {1,2} {1,3} {2,3}
   5. Unordered multi-set, repeats allowed: {1,1} {1,2} {1,3} {2,2} {2,3} {3,3}
   6. Unordered multi-set, each kind appearing at least once.
      Hint: Use bins-and-beans correspondence in which you remove one element of each kind.

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. 
      Example: 6 + 0 + 4 . Hint: Put 2 bin-dividers between 10 beans.
   2. Same, but with n₁,n₂,n₃ ≥ 1. Hint: Interpret this also in terms of bins-and-beans.
   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. 
      Hint: Evaluate f(x) = ∑_k≥0 a_kx^k using the Product Principle, performing an algebraic substitution on the logical expression: (n₁ = 0 or n₁ = 1 or n₁ = 2 or ...) and (n₂ = 0 or ....) and (n₃ = 0 or ...) Compare a₁₀ with your answer above.
   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 {p_k}_k≥0 defined by the recurrence:   p_k = 3p_k−1 − 2p_k−2   for k ≥ 2, where p₀ and p₁ are arbitrary given constants.
   Hint: You can check your answer by computing p_k directly in the case p₀ = p₁ = 1 (work out some values by hand), and comparing with your general answer.

Answers

1a. Product Principle: n^k

   b. Product Principle (Basic Prob 2): n^k = n(n−1)⋅⋅⋅(n−k+1)

   c. PIE: A = {ordered list, any repeats}, A_i = {lists with element i missing} for i = 1,...,n.
       #A_good = n^k − (n | 1) (n−1)^k + (n | 2) (n−2)^k − ⋅⋅⋅ + (−1)ⁿ⁻¹ (n | n−1) 1^k .

   d. Basic Prob 3: (n | k) = n^k / k! = n! / k!(n−k)!

   e. Basic Prob 4 (bins-and-beans correspondence, Notes 9/5):

       ((n | k)) = (k+n−1 | n−1) = (k+n−1 | k)

   f. Correspondence: remove 1 element of each kind, leaving k−n elements to choose arbitrarily.
       ((n | k−n)) = (k−1 | k−n) = (k−1 | n−1)

2a. This is the Multiplicity Transform of multisets (Notes 9/5): ((3 | 10)) = (10+3-1 | 3-1) = (12 | 2) = 66.

   b. ((3 | 10−3)) = (9 | 2) = 36.

   c. Ans: 27.

3a. Problem: Let a_k be the number of solutions to n₁ + n₂ + n₃ = k with n₁, n₂, n₃ ≥ 0. Determine a_k by evaluating f(x) = ∑_k≥0 a_kx^k.
Solution: The cases counted by the coefficients a_k cannot be easily factored into a sequence of choices, but consider all choices of (n₁,n₂,n₃) without specifying the sum k:

3b. Problem: Now let b_k be the number of solutions to n₁ + n₂ + n₃ = k with n₁, n₂, n₃ ≥ 1. Determine b_k by evaluating g(x) = ∑_k≥0 b_kx^k.
Solution: By the same reasoning,

4. Turning the recurrence into an equation for f(x) = ∑_k≥0 p_kx^k, we get: