Final Exam Review I -- Solutions

1a. Product Principle: kⁿ
  b. Product Principle: kⁿ = k(k−1)⋅⋅⋅(k−n+1)
  c. PIE: A = {ordered list, any repeats}, A_i = {no element i} for i = 1,...,n.
       kⁿ − (n | 1) (k−1)ⁿ + (n | 2) (k−2)ⁿ − ⋅⋅⋅ + (−1)ⁿ⁻¹ (n | n−1) 1ⁿ .
  d. Product Principle in reverse: (n | k) = n^k / k! = n! / k!(n−k)!
  e. Bins-and-beans correspondence (Notes 1/11):
       ((n | k)) = (k+n−1 | n−1) = (k+n−1 | k)
  f. Correspondence: remove 1 element of each kind.
       ((n | k−n)) = (k−1 | k−n) = (k−1 | n−1)

2a. ((3 | 10)) = (10+3-1 | 3-1) = (12 | 2) = 66.
b. ((3 | 10-3)) = (9 | 2) = 36.
c. Ans: 19.

3a. Problem: Let a_k be the number of triples of whole numbers n₁, n₂, n₃ ≥ 0 satisfying the equation n₁ + n₂ + n₃ = k. Evaluate the generating function f(x) = ∑_k≥0 a_kx^k using the Product Principle, and use this to get an expression for a_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:

choose (n₁,n₂,n₃) ⇔ (n₁ = 0 or n₁ = 1 or n₁ = 2 or ...) and (n₂ = 0 or ....) and (n₃ = 0 or ...)

To turn this into a generating function, replace the left side by f(x); "or" by plus; "and" by times; "n_i = m" by x^m (since this choice contributes m to the sum n₁+n₂+n₃):

f(x) = ∑_k≥0 a_kx^k = (x⁰ + x¹ + x² + ...) (x⁰ + ...)(x⁰ + ...)
= (1 + x¹ + x² + ...)³ = ( 1/(1-x) )³ = ∑_k≥0 ((3 | k)) x^k .

Hence a_k = ((3 | k)) = (k+3-1 | 3-1) = (k+2)(k+1)/2 , and in particular a₁₀ = 66. Here (n | k) means (n choose k) and ((n | k)) means ((n multi-choose 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,

g(x) = ∑_k≥0 b_kx^k = (x¹ + x² + ...) (x¹ + ...)(x¹ + ...)
= ( x (1 + x¹ + x² + ...) )³ = x³( 1/(1-x) )³
= ∑_k≥0 ((3 | k)) x^k+3 = ((3 | 0)) x³ + ((3 | 1)) x⁴ + ((3 | 2)) x⁵ + ...
= ∑_k≥3 ((3 | k-3)) x^k Hence b_k = ((3 | k-3)) = (k-3+3-1 | 3-1) = (k-1)(k-2)/2.

4. Problem: Solve the recurrence a_k = 3a_k−1 − 2a_k−2 for k ≥ 2, with a₀ , a₁ arbitrary constants.
Solution: The generating function is:

f(x)

(a₁-3a₀)x + a₀

1 − 3x + 2x²

Since the denominator factors as: 1 − 3x + 2x² = (1 − x)(1 − 2x) , we may write:

f(x) = A/(1−x) + B/(1−2x) = ∑_k≥0 A x^k + ∑_k≥0 2B x^k ,

where: A = 2a₀ − a₁ , B = a₁ − a₀ .Collecting x^k terms, we find:

a_k = 2a₀ − a₁ + 2^k (a₁ − a₀) .

For the special case a₀ = a₁ = 1, the recurrence clearly works out as a_k = 1, which agrees with our general formula.