MTH 481
Discrete Math I

Corrections and recent revisions are in red.

• Old Homework

• 2/8: HHM 2.6.4 Fibonacci Numbers pp. 177-179.
  HW:
  1. The Golden Ratio ψ is a special number which supposedly gives the most beautiful proportions for a rectangle. It is defined by the following property: if we divide a rod of length 1 into parts ψ and 1−ψ, then the ratio of ψ to the whole length 1 is equal to the ratio of the other part 1−ψ to ψ. That is:     ψ/1 = (1−ψ)/ψ .
     1. Solve this equation for ψ. Also compute φ = 1/ψ, and rationalize the denominator. Either ψ or φ can be called the Golden Ratio.
     2. In class we stated Binet's formula for Fibonacci numbers: F_k = (φ^k − (−ψ)^k ) / √5 . Check this amazing formula for F_k by hand for k = 0, 1, 2, 3. In particular, note how the irrational square roots all cancel out, leaving only a whole number.
     3. Since |ψ| < 1, its powers become very small, so that the second term in the above formula is only a small correction. In fact: F_k = round(φ^k / √5), where round( ) means round to the nearest integer.
        Problem: On your calculator, compute φ^k / √5 for k = 1,2,...,12. How close are they to the Fibonacci numbers? Do you have to round up or down? Explain the direction of the rounding by looking at the original formula.
     4. Use the rounding formula and your calculator to compute F₄₀ exactly. Compute the largest F_k that will fit on your calculator or computer.
  2. Partial fraction decomposition is a technique to find the series of a rational function. A typical example is below.
     1. Let f(x) = 1 / (1−3x+2x²). Find the vertical asymptotes, which are the roots of the denominator.
     2. Find the two simple functions of the form 1/(1−γx) which have the same vertical asymptotes as f(x).
        Hint: For a given γ, find the asymptote of 1/(1−γx). Now, for our given a vertical asymptotes x = 1, x = ½, what are the values of γ that produce these asymptotes?
     3. We want to find constants A,B such that f(x) = 1 / (1−3x+2x²) = A/(1−x) + B/(1−2x). To do this, we combine terms on the right hand side: (A(1−2x) + B(1−x)) / (1−x)(1−2x) = (A(1−2x) + B(1−x)) / (1−3x+2x²) ; then multiply out: 1 = A(1−2x) + B(1−x)   for all x. Now substitute any values of x, for example: x = 1 and x = ½, and solve the resultiing equations for A, B.
     4. For the A,B you found in part (c), combine terms in A/(1−x) + B/(1−2x) and verify that it is indeed f(x).
     5. Write out the geometric series for A/(1−x) and B/(1−2x), and find the explicit Taylor series of f(x).
     6. Now consider a different function from class: f(x) = x / (1−x−x²). Show that the asymptotes of f(x) are x = −φ and x = ψ, and repeat the above analysis, eventually getting f(x) = A/(1−φx) + B/(1−ψx) for A = 1/√5 and B = −1/√5. Find the explicit Taylor series of f(x) and derive Binet's formula.
        Hint: In your calculations, use that φ = 1/ψ , φ+ψ = √5 , and φ−ψ = 1.
  3. Extra Credit: Other formulas for Fibonacci numbers
     1. Fibonacci numbers and binomial coefficients. If we use different algebraic tricks on the generating function of the Fibonacci numbers, we get another formula for F_k.
        Factoring out an x from the generating function, we get: f(x)/x = ∑_k≥0 F_k+1 x^k  =  1 / (1 − (x+x²)) . Expand this in two stages. First use the geometric series formula 1/(1−z) = ∑_j≥0 z^j with z = x+x² . Then expand (x+x²)^j by the Binomial Theorem. You should get a double sum of the form: f(x)/x = ∑ _j≥0 ∑^j_i=0 .... You may prefer to write this out in a table of terms with rows corresponding to j = 0, 1, 2,... and columns corresponding to i = 0, 1,..., j.
        Now collect terms with like powers of x : that is, add up the coefficients with no x, with x¹, x², x³, until you see the pattern. Or use summation notation, and collect the terms corresponding to all values of j and i which produce a total exponent equal to k. Obtain a formula for F_k as a sum of certain choose numbers (j | i). Write your formula explicitly for k = 1,...,6 .
     2. Hopscotch problem. A hopscotch board is a sequence of columns of 1 or 2 squares (see picture HHM p.181 #10). Let h_k be the number of boards with a total of k squares. Equivalently, h_k is the number of ways of splitting k into a sum of 1's and 2's, where order matters. For example, h₅ = 8 counts the 8 sums: 5 = 2+1+1+1 = 1+2+1+1 = 1+1+2+1 = 1+1+1+2
        = 2+2+1 = 2+1+2 = 1+2+2 = 1+1+1+1+1 . Also let h₀ = 1.
        Find the generating function of h_k using the Sum and Product Principles. Choosing any sum of 1's and 2's is equivalent to the following: first decide how many 1-or-2 numbers you will add (say, j numbers), then choose 1 or 2 for each of the j numbers. This choice will contribute to h_k where k is the sum of the 1-or-2 numbers chosen. Sum over all j ≥ 0 to get the generating function of h_k's . You should get a kind of geometric series 1 + z + z² + ... , which you can sum using the usual formula. Now use the result to compare h_k to the Fibonacci numbers.
  Solutions: 1a. The equation reduces to ψ² = 1−ψ, or ψ²+ψ−1 = 0, which has roots (−1±√5)/2. The positive root is ψ = (√5−1)/2 .
  Also φ = 1/ψ = 2/(√5−1) = 2(√5+1) / (√5−1)(√5+1) = 2(√5+1) / (5−1) = (√5+1) / 2. The approximate values are ψ ≅ 0.6 , φ ≅ 1.6 .
  2a. Roots of the denominator (and hence the vertical asymptotes) are x = 1 and x = ½.
  2b. 1/(1−γx) has vertical asymptote x = 1/γ. Thus we want 1/γ = 1, giving γ = 1 and the function 1/(1−x). Also 1/γ = ½, giving γ = 2 and the function 1/(1−2x).
  2c. Substituting x = 1, we get 1 = A(1−2) + B(1−1) = −A, so A = −1. Substituting x = ½, we get 1 = A(1−2(½)) + B(1−½) = ½B, so B = 2.
  2d. −1/(1−x) + 2/(1−2x)  =  (−(1−2x) + 2(1−x)) / (1−x)(1−2x)  =  1/(1−3x+2x²)
  2e. f(x) = −1/(1−x) + 2/(1−2x)  =  (−1 − x − x² − x³ −...) + (2 + 2(2x) + 2(2x)² + 2(2x)³ + ...)
  = (−1+2) + (−1+2²)x + (−1+2³)x² + (−1+2⁴)x³ + ...
  2f. The simple functions with the asymptotes x = ψ and x = −φ are 1/(1 − x/ψ) = 1/(1−φx) and 1/(1 + x/φ) = 1/(1+ψx). In fact 1−x−x² = (1−φx)(1+ψx).
  Multiplying out x / (1−x−x²) = A/(1−φx) + B/(1+ψx), we get x = A(1+ψx) + B(1−φx) for all x.
  Substituting x = ψ gives ψ = A(1+ψ²) + B(1−φψ) = A(1+ψ²) so A = ψ/(1+ψ²) = ... = 1/√5. Similarly B = −1/√5.
  It is much easier to rewrite the original equation as: x = (A+B) + (Aψ−Bφ)x, and equate the constant terms and the coefficients of x on the two sides: 0 = A+B, so that B = −A; and 1 = Aψ−Bφ = Aψ+Aφ, so that A = 1/(ψ+φ) = 1/√5 and B = −1/√5.

• 2/10: HHM 2.6.5 Recurrence Relations pp. 181-183. Video on partial fraction decomposition.
  HW:
  1. Use generating functions to solve the recurrence a₀ = 1, a_k = 2a_k−1 + 1 for k≥1.
     Step 1: Use the recurrence for a_k to write an equation involving f(x) = ∑_k≥0 a_kx^k, then solve the equation to get a simple formula for f(x). Be careful with the first term a₀, where the recurrence does not hold.
     Step 2: Use partial fractions to explicitly find the Taylor series of f(x), and therefore get a formula for a_k. Hint: Use HW 9/30 #2c for the decompositon.
  2. General recurrence relations: Use generating functions to give formulas for the sequences a_k defined by the following recurrence relations:
     (a)   a_k = a_k−1 + c              (b)   a_k = b a_k−1 + c r^k              (c)   a_k = b a_k−1 + c k
     Here b,c,r are some given constants. Also a₀ is given, and the recurrences are valid for k ≥ 1.
     Test that your general formula agrees with #1 above, which is an example of (b) with constants b = 2, c = r = 1. Test some more examples by taking specific b,c,r,a₀, computing a few terms of the series by hand, and seeing that they agree with the general formulas.
     Hints: In (a), the value of a_k is trivial, but I want you to see what it means in terms of generating functions. In (c), you will need the know the formula for ∑_k≥0 k x^k, which you can get from differentiating both sides of the geometric series formula.
  Solutions: 1. See class notes, where I solved a similar recurrence.
  Step 1: f(x)  =  a₀ + ∑_k≥1 a_kx^k  = 1 + ∑_k≥1 (2a_k−1+1)x^k
   =  1 + 2x∑_k≥1a_k−1x^k−1 + ∑_k≥1x^k  =  1 + 2xf(x) + 1/(1−x) − 1.
  That is, f(x) = 2xf(x) + 1/(1−x). We can solve for f(x) = 1/(1−x)(1−2x).
  Step 2: By partial fraction decomposition, f(x) = −1/(1−x) + 2/(1−2x) = ∑_k≥0 (−x^k) + ∑_k≥0 2(2^k)x^k. (See the previous HW 2/8 #2 for how to find the numerators.) Collecting x^k terms, we find the coefficient is: a_k = −1 + 2^k+1. This agrees with the first few values of a_k.
  2a. Recurrence: a_k = a_k−1 + c. Here the solution is obvious, but let's do it by generating functions just for practice.   f(x)   =    a₀ + ∑_k≥1 (a_k−1 + c) x^k   =    a₀ + ∑_k≥1 a_k x^k
    =    a₀ + x ∑_k≥1 a_k−1x^k−1 + cx ∑_k≥1 x^k−1   =    a₀ + x f(x) + cx/(1−x)
  Thus: f(x) = a₀/(1−x) + cx/(1−x)²   =    a₀ + ∑_k≥1 a₀ x^k + ∑_k≥0 c ((2 | k)) x^k+1
  = a₀ + a₀x + c((2|0))x + a₀x² + c((2|1))x² + ... Final answer: a_k = a₀ + c ((2 | k−1)) = a₀ + c (k | k−1) = a₀ + ck = a₀ + ck , which is indeed the obvious result.
  2b. Recurrence: a_k = b a_k−1+ c r^k. Here the answer is not at all obvious. Step 1 gives:
  f(x) = a₀ + bx f(x) + crx/(1−rx)   so   f(x) = a₀/(1−bx) + crx/(1−rx)(1−bx)
  Partial fractions: crx/(1−rx)(1−bx) = A/(1−rx) + B/(1−bx) .
  Clear denominators, substitute x = 1/b, 1/r , get A = cr/(r−b), B = −cr/(r−b).
  Final answer:   a_k = a₀b^k + A r^k + B b^k   =   a₀b^k + cr(r^k − b^k)/(r−b).
  Check: For the case in Prob #1, we have b = 2, c = r = 1, a₀ = 1, so a_k = 1(2^k) + 1(1^k−2^k)/(1−2) = 2^k − (1−2k) = −1 + 2^k+1 as we got in #1.
  2c. Recurrence: a_k = b a_k−1 + ck . This one is harder than I would give on a test.
  First, differentiating (1−x)⁻¹ = ∑_k≥0 x^k gives: (1−x)⁻² = ∑_k≥0 kx^k−1, so x/(1−x)² = ∑_k≥0 kx^k.
  Equation: f(x) = a₀ + bx f(x) + cx/(1−x)²   so   f(x) = a₀/(1−bx) + cx/(1−bx)(1−x)²
  Partial fractions: cx/(1−bx)(1−x)² = A/(1−bx) + B/(1−x)² + C/(1−x) .
  Clear denominators and substitute x = 1/b, x = 1 to get A = cb/(b−1)² ,   B = −c/(b−1) .
  Then we have:   C/(1−x) = cx/(1−bx)(1−x)² − A/(1−bx) − B/(1−x)² = −c/(b−1)²(1−x) .
  Final answer:   a_k = (a₀ + cb/(b−1)²) b^k − ck/(b−1) − cb/(b−1)² .
  Check: Compare with obvious formulas in the case b = 0 and in the case c = 0 .

• 2/13: HHM 2.6.6 Catalan Numbers pp. 185-189. Try the Wikipedia article.
  HW:
  1. Use the recurrence: C_k = C_k−1C₀ + C_k−2C₁ + C_k−3C₂ + ... + C₀C_k−1 for k ≥ 1 and C₀ = 1 to compute C₁,... C₈. Can you find any patterns, or guess any formula?
  2. Grouping products: one of the many, many problems that give rise to Catalan numbers.
     The associative law says that a product does not depend on the grouping of factors: for example (2×3)×4 = 6×4 = 24 and 2×(3×4) = 2×12 = 24. Abstractly: (x₀x₁)x₂ = x₀(x₁x₂). Of course it works with more factors, and there are more ways to multiply: ((x₀x₁)x₂)x₃ = (x₀(x₁x₂))x₃ = (x₀x₁)(x₂x₃) = x₀((x₁x₂)x₃) = x₀(x₁(x₂x₃)) Let P_k be the number of ways to group k+1 factors x₀x₁...x_k , so that P₀ = P₁ = 1, P₂ = 2, P₃ = 5.
     1. Find a recurrence for P_k as follows. Split P_k into cases, depending on where the outermost parentheses occur. For example, in (x₀x₁)(x₂x₃), the outermost parenthesis is after x₁, and the number of groupings with this property is P₁P₁ = 1. In ((x₀x₁)x₂)x₃ and (x₀(x₁x₂))x₃, the outermost parenthesis is between x₂ and x₃, and the number of groupings with this property is P₂P₀ = 2.
     2. Prove that P_k = C_k . This is obvious from the recurrence, since....
  3. Fractional powers
     1. For a real number α (whole number, fraction, positive, negative...), define: (α | k) = α^k / k! = α(α−1)...(α−k+1) / k! . Prove the Taylor series: (1−x)^α = ∑_k≥0 (α | k) x^k. How does this compare with the Binomial Theorem for positive and negative exponents? Hint: Use Taylor's Formula for the coefficients.
     2. Recall that the Catalan generating function is f(x) = ∑_k≥0 C_kx^k   =   (1 − √(1−4x)) / 2x. Go through Step 2 of the Method for the modified function: h(x) = xf(x)   =   C₀x + C₁x² + C₂x³ + ...   =   ½ − ½√(1−4x). You can find the Taylor series h(x) = ∑_k≥1 a_kx^k directly from Taylor's formula a_k = h^(k)(0) / k!, or use part (a) with α = ½. This gives a formula for C_k = a_k+1. Use this formula to compute C₀,...,C₈, and compare to your result from #1.
  Solutions: 1.

  k	0	1	2	3	4	5	6	7	8
  Ck	1	1	2	5	14	42	132	429	1430

  2a. The groupings with outermost parenthesis after x_i are split into a factor with i+1 variables and one with k−i variables; considering recursively, there are P_iP_k−i−1 such groupings. Thus P_k = P_k−1P₀ + P_k−2P₁ + ... + P₀P_k−1.
  2b. P_k and C_k are computed using exactly the same recursion, starting from the same initial value P₀ = C₀ = 1, so they must be equal.
  Formally, we can prove it by induction. P_k = C_k is definitely true for k = 0. Now assume it is proved up to a given k. Then P_k+1 = P_kP₀ + P_k−1P₁ + ... + P₀P_k. By assumption P₀ = C₀, P₁ = C₁,..., P_k = C_k, so the right hand side equals C_kC₀ + C_k−1C₁ + ... + C₀C_k, which equals C_k+1 by the known recurrence. Thus the equality P_k+1 = C_k+1 also holds, and the induction proceeds. Conclusion: P_k = C_k holds for all k.
  3a. The k^th derivative of (1−x)^α is α(α−1)(α−2)...(α−k+1)(1−x)^{α − k}, so the k^th coefficient of the Taylor series is a_k = α^k / k!.
  3b. Taylor's formula gives: a_k = −(½)(−4)^k(½)^k / k!   =   (−1)^k−12^2k−1(1/2)(−1/2)(−3/2)...(−(2k−3)/2) / k!   =   2^k−1(1)(3)(5)...(2k−3) / k! Thus C_k = a_k+1 = 2^k(1)(3)(5)...(2k−1) / (k+1)!, and we can compute: C₀ = 2⁰ / 1! = 1  ,  C₁ = 2¹(1) / 2! = 1  ,  C₂ = 2²(1)(3) / 3! = 2  ,  C₃ = 2³(1)(3)(5) / 4! = 5  ,  etc. This can be simplified further to give the standard formula for Catalan numbers: C_k =   =   ( 2^k(1)(3)(5)...(2k−1) / (k+1)! )   ( (2)(4)(6)...(2k) / 2^kk! )
    =   (2k)! / (k+1)! k!   =   ¹⁄_(k+1) (2k | k) .

• 2/15: More on Catalan Numbers.
  HW:
  1. The explicit Formula for Catalan numbers is: C_k   =   ¹⁄_(k+1) (2k | k)   =   (2k)! / k!(k+1)! .
     1. Compute C₀,... C₈ using the formula. Does it give the correct answers, comparing with HW 2/13?
     2. Our definition for the Catalan number C_k is equivalent to Catalan paths: these are walks in the plane from (0,1) to (2n,1) which never pass below the line y = 1, and each step goes right by 1 either up or down by 1.
        Problem: Why would you think of (2k | k) in relation to counting paths? There is a fairly natural relation, though it does not fully explain the formula for C_k .
     3. Extra Credit: The Formula looks like a fraction, not a whole number: it seems a "coincidence" that (2k | k) is always divisible by k+1. Can you give an algebraic or combinatorial reason for this?
  2. HHM Ch 2.6.6, p.190 #6. Suppose 2k people are seated around a table. How many ways are there for k pairs to shake hands simultaneously across the table in such a way that no arms cross? Geometrically: mark 2k nodes on a circle, and pair the nodes up by drawing curves between them, so that no two curves cross. Let H_k be the number of handshake-patterns for 2k people. Then H₃ = 5 counts the following patterns:
     
     Find H₄ by drawing out all possible patterns for 8 nodes. Guess a relation of H_k to C_k. Find a Catalan-like recurrence for H_k, which gives a recursive algorithm for drawing patterns, and also proves the relation between H_k and C_k.
     Hint: Given a handshake pattern, saw the table in half along the curve starting at the top node, getting left and right pieces of the table, which can be considered as smaller tables with nodes (guests) around them. Fixing the number of nodes in each piece, how many smaller handshake patterns can be inserted? Sum these to get the recurrence.
  Solutions: 1b. Since the path ends at the same height as it began, half the steps must be down, and half up. Thus every path corresponds to a choice of k positions out of 2k for the up steps; and there are (2k | k) possibilities for such a choice. (See HW 1/11 #4, the city grid problem, where we also had two choices for each step, with fixed start and end points.) However, Catalan paths also require staying above y = 1, and the Formula says that a 1/(k+1) fraction of all the paths satisfy this. Where this fraction comes from is unclear: it is explained in the Wikipedia article.
  2. H₄ = 14, and indeed H_k = C_k for k ≤ 4. This is true for all k, since the table-splitting described in the hint gives the same recurrence as for C_k , namely H_k = H₀H_k−1 + H₁H_k−2 + ... + H_k−1H₀ .

• Old Notes

• Notes 1/13: A multi-set is an unordered collection of objects with repeats allowed, like {1,1,1,3,4,4,5}. The number ((n | k)), pronounced 'n multi-choose k', counts the multi-sets of k elements of n possible kinds. Examples:
  • ((3 | 2)) counts the multi-sets of 2 elements from the three kinds {1,2,3}; they are:   {1,1} {1,2} {1,3} {2,2} {2,3} {3,3}.   Since there are 6 such multi-sets, ((3 | 2)) = 6.
  • ((2 | 3)) counts the multi-sets of 3 elements from the two kinds {1,2}; they are:   {1,1,1} {1,1,2} {1,2,2} {2,2,2}.   Thus ((2 | 3)) = 4.
  • A typical real-world example of a multi-set is a handful of 7 jellybeans taken from a big jar with 5 flavors (Red, Yellow, Green, Blue, White): this is equivalent to a multi-set of 7 elements from 5 kinds. For example, a handful with 3 of R, none of Y, 1 of G, 2 of B, 1 of W, corresponds to the multi-set {R,R,R,G,B,B,W}. The number of different handfuls is thus ((5 | 7)), which we compute below.
  • We can also describe a multi-set by the list of multiplicities for each possible kind. For example, the above multi-set of jelly beans could be described by the multiplicity-list (3,0,1,2,1), and the size is 3+0+1+2+1 = 7.

  The Stretching Transformation changes multi-sets into into ordinary sets, which will allow us to compute ((n | k)). This is a reversible transformation (one-to-one correspondence) defined as follows. We assume the elements of the multi-set M are listed in order: a₁ ≤ a₂ ≤ … ≤ a_k; and we define the elements of the set S by adding 0 to the first entry of M, 1 to the second entry, etc.

  M = {a₁,...,a_k}   →   S = {b₁,...,b_k} = {a₁+0, a₂+1, a₃+2,..., a_k+k−1} . Since 1 ≤ a₁ ≤ a₂ ≤ … ≤ a_k ≤ n, we have: 1 ≤ b₁ < b₂ < … < b_k ≤ n+k−1. The set S is thus a k-element subset of {1, 2,..., n+k−1}

  We show the Stretching Transformation is a one-to-one correspondence by defining its inverse, the Shrinking Transformation, which changes sets back into multi-sets:

  S = {b₁,...,b_k}   →   M = {a₁,...,a_k} = {b₁−0, b₂−1, b₃−2,..., b_k−k+1} . These two transformations clearly undo each other, in either order (Stretching, then Shrinking; or Shrinking, then Stretching).

  Conclusion: the multi-sets counted by ((n | k)) are in one-to-one correspondence with the sets counted by (n + k − 1 | k), meaning that these numbers are equal:

  ((n | k))   =   (n + k − 1 | k) , where we know how to compute the right-hand side. For example, ((5 | 7)) = (5+7−1 | 7) = (11 | 7) = (11 | 4) = 11⁴ / 4! = 330.

• Notes 1/18: The Position Transformation is a reversible way of changing the data of lists into sets, which often makes counting easier.

  Typical example: How many ways to toss a coin 5 times with 3 heads, such as HTTHH? This naturally corresponds to lists like (H,T,T,H,H) with 3 H's and 2 T's, which cannot be easily counted with any of our usual principles or basic problems. Instead, we transform the data by recording the positions of the H's: (H,T,T,H,H) has an H in the first, fourth, and fifth positions, so it corresponds to the set {1,4,5}. Since there were 3 H's in the list, there are 3 elements in the set, which lies inside {1,2,3,4,5}. The transformation has the table:

  list	HHHTT	HHTHT	HHTTH	HTHHT	HTHTH	HTTHH	THHHT	THHTH	THTHH	TTHHH
  set	{1,2,3}	{1,2,4}	{1,2,5}	{1,3,4}	{1,3,5}	{1,4,5}	{2,3,4}	{2,3,5}	{2,4,5}	{3,4,5}

  The point of this transformation is that it outputs all 3-element subsets of {1,2,...,5}, each just once, and we know how to count these: Basic Problem 3 tells us there are (5 | 3) = 10. Of course, in this case we can just write out all the lists and count them, but the argument works in general: the number of ways to get k heads out of n tosses is (n | k).
  We could also record the positions of the 2 T's instead of the 3 H's, but this gives us the same answer, since (5 | 2) = (5 | 3), and in general (n | k) = (n | n−k).

  We have seen the Position Transform in the following problems:

  • Walks on a city grid with 10 North steps and 5 East steps. We transform a walk (a list of N's and E's) by recording the positions of the 5 E's out of the 15 positions. Ans: (15 | 5) = 3003. Note: Recording the 10 N's gives the same number, since (15 | 10) = (15 | 5).
  • Rows of 5 red and 3 black balls. We record the postions of the 3 black balls out of the 8 total positions. Ans: (8 | 3).
  • What is the number of all subsets of an n-element set, S ⊂ {1,2,...,n}? For example, {1,2,3} has the 8 subsets S = {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}. We use the Reverse Position Transformation, which changes the given sets S into lists L = (a₁,...,a_n) with n positions and two kinds of list elements, say + and −. The elements of S give the positions of the +'s. For n = 3, the Reverse Position Transformation has the table:

    set S	{}	{1}	{2}	{3}	{1,2}	{1,3}	{2,3}	{1,2,3}
    list L	(−,−,−)	(+,−,−)	(−,+,−)	(−,−,+)	(+,+,−)	(+,−,+)	(−,+,+)	(+,+,+)

    The output is all lists of three +/− entries, and the Product Principle says there are 2³ = 8 of these. Of course, in this case, we can just write all the sets and count them, but the argument works in general: The number of all subsets of {1,2,...,n} is 2ⁿ.

• Notes 1/27.   Preliminary to generating functions: Direct proof of the Binomial Theorem.
  • The choose number (n | k) is defined as the number of k-element subsets of a n-element set. The Binomial Theorem says that these same numbers appear as coefficients when we expand the expression (x+y)ⁿ into monomials x^ky^n−k. How to explain this coincidence between a counting problem and an algebra problem?
  • We examine the case n = 3. Choosing a subset S from {A,B,C} is equivalent to choosing or not choosing each of the three elements A,B,C. We figure the possiblilities for S by considering the expression:
    (XA or YA) and (XB or YB) and (XC or YC),
    where XA means "A is in S" and YA means "A is not in S", etc. We expand this expression using the logical distributive rule:
    (P or Q) and R   ⇔   (P and R) or (Q and R). Here P,Q,R are simple statements, and the compound statements on the two sides of the equation are logically equivalent. This is analogous to the algebraic distributive rule (p+q)×r = (p×r) + (q×r). We expand until we have an expression like:   (XA and XB and XC) or (XA and XB and YC) or ... or (YA and YB and YC) , in which the 8 terms correspond to the subsets S = {A,B,C}, {A,B}, ... , {} .
  • Now we re-imagine the entire computation:
    • atomic statements XA, XB, XC become the variable x; and YA, YB, YC become the variable y
    • the operation "or" becomes +
    • the operation "and" becomes ×
    • each logical equivalence "⇔" becomes algebraic equality "=", because:
    • These equalities are true because: the logical distributivity law (P or Q) and R  ⇔  (P and R) or (Q and R) becomes the algebraic distributivity law (p+q)×r = (p×r) + (q×r).
  • In the end we have shown that: (x+y)(x+y)(x+y)   =   xxx + xxy + xyx + yxx + ... + yyy , in which the 8 terms again correspond to subsets (encoded by the positions of the x's). Finally we simplify by collecting powers of x and y, and we collect like terms to get a polynomial   a₃ x³ + a₂ x²y + a₁ xy² + a₀ y³ . The coefficient a_k is the number of terms x^ky^n−k, which is just the number of subsets S with k elements (since the number of x's in each term is precisely the number of elements in the corresponding set S). That is, a_k = (3 | k), which explains (and proves) the Binomial Theorem for n = 3, namely: (x+y)³   =   (3 | 3) x³  +  (3 | 2) x²y  +  (3 | 1) xy²  +  (3 | 0) y³ .
  • We can do all this for any n. We do not need to keep track of the intermediate computations in the expansion, since we know the beginning form (x+y)ⁿ and the expanded form   xx...x + ... + yy...y   in which each term corresponds to a subset in a transparent way. For example for n = 5, yyxyx would correspond to S = {3,5}. Then we collect terms x^ky^n−k just as before to get the Binomial Theorem: (x+y)ⁿ = (n | n)xⁿ + (n | n−1)xⁿ⁻¹y + (n | n−2)xⁿ⁻²x² + ... + (n | 1)xyⁿ⁻¹ + (n | 0)yⁿ. Notice that it came out flipped over from the standard form.
  • Note that this argument says nothing about how to compute (n | k). Rather we have proved that whatever the number of k-subsets of an n-set, this is the same as the coefficient of x^ky^n−k in (x+y)ⁿ.

• Notes 1/30: Method of Generating Functions (Ch 2.6).
  Goal:   Get a numerical answer to a counting problem a = |A|, where A is combinatorially interesting class of objects.
  Step 0.   Generalize the problem by seeing a as one of a sequence of similar numbers a₀, a₁, a₂, .... Usually, this means replacing some specific number in the definition of a by the index k = 0,1,2,....
  Step 1.   Define the generating function:

  f(x)   =   a₀ + a₁x + a₂x² + ....   =   ∑_k≥0 a_k x^k .

  This is a polynomial if the sequence {a_k} is finite, or a Taylor series if the sequence is infinite. Use combinatorial properties of the sequence {a_k} to get a simple formula for f(x).
  • The Product Principle for the entire sequence {a_k} can lead to a product formula for f(x). The Product Principle says that choosing an object is equivalent to making a sequence of basic choices. Re-imagine this logical equivalence as an equation by replacing:

    logic	choose object of any size	⇔	basic choice adding size m	or	and
    algebra	f(x) = ∑k≥0 akxk	=	xm	+	×

    This is most often used in choosing certain multi-sets, which is equivalent to choosing the number of each kind, with restrictions; and k is the total size of the multi-set.
  • If we can find f(x) in terms of any known Taylor series, we can replace the series by its function.
  • A recurrence for a_k leads to an equation involving f(x), which can be solved for f(x).
  Step 2.   Given f(x), use algebra and calculus to expand it as a power series, thereby evaluating the coefficients a_k.
  • Taylor's formula: a_k = f ^(k)(0) / k! , where f ^(k)(0) means the k^th derivative of f(x) evaluated at x = 0.
    This is valid for all functions, but is gives useful results only for especially simple functions like f(x) = e^x, sin(x), or (1 ± x)ⁿ for any real number n.
  • Try to write f(x) in terms of functions with known Taylor series.
    Partial fraction decomposition writes a rational function in terms of geometric series.
  Known series
  • Geometric series 1/(1 −x) = 1 + x + x² + ... = ∑_k≥0 x^k .
  • Binomial theorem: (1 + x)ⁿ = ∑_k=0ⁿ (n | k) x^k , where (n | k) = n^k / k! is a binomial coefficient.
  • Binomial with negative power: (1 − x)⁻ⁿ = ∑_k≥0 ((n | k)) x^k , where ((n | k)) = (k+n−1)^k / k! is a multi-choose number.