• [W]  Herbert Wilf, Generatingfunctionology, 2nd ed., free here.
• [HHM]  Harris, Hirst, and Mossinghoff, Combinatorics and graph theory, 2nd ed., free from the MSU Library here or here.
• [S]  Richard Stanley, Enumerative Combinatorics I, 2nd ed., here or here.
• Reinhard Diestel, Graph Theory here.
• Martin Aigner & Günter Ziegler, Proofs from THE BOOK, here.
• Günter Ziegler, Convex Polytopes: Extremal Constructions and f-Vector Shapes, here.
• Jurgen Richter-Gebert, Realization Spaces of Polytopes, here.

• Final Exam:
  • Mon Apr 28, 10am−12noon in our usual classroom Wells A-136.
  • The exam will be 8 or 9 pages: about 9 quizzes put together, or slightly less than two midterms.
  • Study in the same way as for the Midterm Exam: re-do (not just re-read) all quizzes and the Midterm, then compare to the answers. Do the Review 1,2,3 below, as well as the Midterm Review. Re-read the Notes, and re-do the old HW selection below.
  • The Exam will consist of 40% pre-midterm and 60% post-midterm topics.

On this page, I will denote the binomial coefficient (n choose k) as (n | k), and the multi-set number (n multi-choose k) as ((n | k)). Use the standard vertical notation on your papers. Also, the set of the first k positive integers is denoted [k] = {1,2,...,k}.

• Old Homework

• 4/21: Final Review 1: Finite Difference Calculus.
  Notes:
  • We can view a sequence (a_n)_n≥0 as a function a : ℕ → ℝ, since to each input n ∈ ℕ (a discrete variable), it assigns an output a(n) = a_n. There is a close analogy with a function a(x), where x is a real number input (a continuous variable), and many familiar operations on a(x) have analogs for a_n.
  • The derivative operation D = ^d⁄_dx for a(x):

    Da(x)   =   a'(x)   =   lim_h→0 ^{(a(x+h) − a(x))}⁄_h   =   lim_h→0 ^{(a(x) − a(x−h))}⁄_h

    has two analogs for a_n: the advanced and retarded difference operations:

    Δ⁺a_n  =   ^{(a_n+1−a_n)}⁄₁   =   a_n+1 − a_n.

    Δ⁻a_n   =   ^{(a_n−a_n−1)}⁄₁   =   a_n − a_n−1.

    By convention, we always take a_−n = 0 for a negative index −n, so Δ⁻a₀  =  a₀ − a₋₁  =  a₀.
    It turns out that Δ⁻ is more useful, so we will drop the superscript, and simply denote:   Δ = Δ⁻.
  • The integral or anti-derivative operation ∫ a(x)  =  ∫_t=0^x a(t) dt is analogous to the summation operation:

    Σa_n   =   ∑_i=0ⁿ   a_i.

  HW:
  1. Prove the Fundamental Theorem of Difference Calculus: Δ and Σ are inverse operations: that is, Δa_n = b_n  ⇔  a_n = Σb_n . Or equivalently, for any sequence (a_n)_n≥0, we have:

     Δ(Σa_n) = a_n       and       Σ(Δa_n) = a_n .

     Hint: As for any facts about sigma-notation, when in doubt, write out the n terms in dot-dot-dot notation.
  2. Our main tool for analyzing a sequence is to take its generating function:

     (a_n)_n≥0     ↔^ops     f(x)  =  ∑_n≥0 a_nxⁿ.

     Determine the effect of the operations Δ, Δ⁺, Σ on the generating function f(x). That is, if ∑_n≥0 a_nxⁿ = f(x), then write ∑_n≥0 Δa_n xⁿ in terms of f(x), and the same for Δ⁺a_n, Σa_n .   Hint: We have seen such questions long ago in Wilf's Rules 1−5.
  3. Use Prob #2 to give a generating-function proof for the Fundamental Theorem (Prob #1).
  4. Solve the difference equation Δ⁺a_n  =  a_n, by elementary means (just write out what it means), and also by generating functions. Assume the initial value a₀ is an arbitrary constant.
     Compare to the solutions of the corresponding differential equation a'(x) = a(x).
  5. Show that

     Δ⁺Δ⁻a_n   =   Δ⁻Δ⁺a_n   =   a_n+1 + a_n−1 − 2a_n   for n ≥ 1.

     We must be careful about n = 0: we get Δ⁺Δ⁻a₀ = a₁ − 2a₀ , whereas Δ⁻Δ⁺a₀ = a₁ − a₀ .
     This is another way of writing the negative Laplacian operation −L (HW 4/11 #2), which adds the a-values at the neighbors of vertex n, minus the vertex-degree times the value at n.
  6. Solve the difference equation:  Δ⁺Δ⁻a_n  =  −a_n for n ≥ 1, using generating functions. We do not assume any recurrence for n = 0; rather, the initial values a₀, a₁ are arbitrary constants.
     Compare to the solutions of the corresponding differential equation a''(x) = −a(x), which is a version of Hooke's Law.
  7. Recall that, for a fixed whole number k, we have the falling-power sequence a_n  =  n^k  =  n(n−1)⋯(n−k+1). (Also n⁰ = 1.) Find a simple formula for the generating function f(x)  =  ∑_n≥0 n^k xⁿ. Hint: Start with the cases k = 1 and k = 2. Use Wilf's Rules.
  8. Prove by induction that  Δ(n^k) = k(n−1)^k−1  for k ≥ 1 and n ≥ 1. Hint: Is induction needed here, or can you prove it directly?
  9. Reversing the previous problem, we have n^k = k Σ(n−1)^k−1, and iterating, we get n^k = k! Σ^kc_n, where Σ^k means perform the Σ operation k times, and c_n = (n−k)⁰ = 1 for n ≥ k, and c_n = 0 for n < k. Use this and Prob #2 as a different way to find a simple formula for the generating function f(x)  =  ∑_n≥0 n^k xⁿ.
  10. Find a transformation to prove the formula:

      n^k   =   ∑_i=0^k {k | i}n ⁱ ,

      where {k | i} is a Stirling partition number from the Twelvefold Way. Hint: The number n^k naturally counts functions f : [k] → [n], which can be written in two forms: as a list of outputs, or as k marked balls in n ordered bins. Transform the data of such an f into a pair of objects which are naturally counted by {k | i} and n ⁱ , which are entries of the Twelvefold Way.
  Solutions revised

• 4/23: Final Review 2: Deletion transforms, recursive choice algorithms, generating functions
  HW:
  1. Define a language as a set W of words, which are lists of letters, according to specified rules. In our language, a word can be any string of letters a,b, with no two consecutive a's. We let w_n be the number of allowed words with n letters. For example, w₃ = 5 counts the words:

     aba, abb, bab, bba, bbb.

     Use generating functions to determine w_n as a recurrence formula, an exact algebraic formula, an asymptotic formula, and in terms of a well-known sequence.
  2. A theory problem. Suppose we take two convex polyhedra P₁, P₂ and join them along one edge, which becomes a hinge between the two bodies. The resulting union P is clearly not convex, but still has vertices, edges, and faces.
     1. Is the edge-graph of P always planar? If so, explain how to draw it.
     2. Prove or disprove: There exists a convex polyhedron P' with the same edge-graph as P.
  3. Another theory problem. True or false: there exists a convex polyhedron with 100 vertices and 200 edges. Prove your answer using results we have covered.
  Solutions

• 4/25: Final Review 3
  HW: Here is a "greatest hits" list from our HW, keyed to the test topics.
  Note: You should be able to state the definitions and theorems listed below, and apply them to particular cases.
  • Twelvefold Way
    • HW 1/10 #1. Different data structures describing functions.
  • Transformations
    • HW 1/10 #3. Deletion transform ⇒ recurrence.
    • HW 1/13 #3. Deletion transform ⇒ recurrence ⇒ recognize a familiar sequence.
  • Power series manipulations
    HW 1/29 #2. Practice with Wilf's Rules.
  • Ordinary and exponential generating functions, combinatorial families
    • HW 1/15 #1. Multi-choose generating function.
    • HW 1/24 #4. Catalan convolution recurrence ⇒ explicit formula.
    • HW 2/7 #1. Exponential family ⇒ Bell numbers and Stirling partition numbers.
    • HW 2/10 #2. Exponential families, sets vs lists.
    • HW 2/14 #2. Valentine's Day Game, a full example of the method.
    −−−−−− Midterm −−−−−−
  • Trees, recursive families, Lagrange Inversion Formula
    • HW 2/24 #1. Deletion for family trees ⇒ recursive choice algorithm ⇒ generating function.
    • HW 2/26 #1. Apply Lagrange Inversion to the previous example ⇒ Catalan formula.
  • Dlog method and recurrences
    • HW 1/22 #3. Clear denominators of generating function ⇒ recurrences.
    • HW 2/12 #2. xDlog recurrences.
  • Otter's Formula for unrooted trees
    • HW 3/10 #1. xDlog recurrence for rooted trees (unlabeled vs labeled)
    • HW 3/14 #1. Otter's formula example: compute unrooted trees in terms of vertex-rooted and edge-rooted.
  • Tree proofs
    • Math 481 HW 11/6 #1, 2. Definitions and properties of trees.
  • Planar graphs, Euler's Formula
    • HW 4/4 #1. Polyhedral graph formulas.
  • Graph connectivity, Menger's Theorem
    • HW 3/31 #2. Augmenting path algorithm for Menger's Theorem.
  • Polyhedra, standard examples, vector geometry
    • HW 3/19 #1. Standard polyhedra.
    • HW 3/21 #1. Vertex and face definitions of polyhedra.
    • HW 3/24 #2. Steinitz Lemma on f-vectors of polyhedra.
  • Steinitz Theorem, Balinski theorem
    • HW 3/26 #2. Different polyhedra with the same f-vector.
    • HW 3/28 #2. Up/down paths to prove connectivity of G−{v₁,v₂}.
  • Tutte's Rubber Band Model
    • HW 4/11 #1. Laplacian matrix for computing equilibrium position.
  • Maxwell's Lifting Theorem
    • HW 4/16 #1. Compute lifting of an equilibrium graph.
    • HW 4/18 #1. Prove properties of Maxwell's lifting.

• Old Notes
• Math 481: Review.
• Notes 1/8 - 1/13: The Twelvefold Way and other sequences.
• Notes 1/8: Deletion Transform
• Notes 1/10: Number partitions.
• Notes 1/13: Stirling cycle numbers
• Notes 1/15:   Method of Generating Functions Review ([HHM] Ch 2.6).
• Wilf's Rules for generating function manipulation.
• Notes 1/17: Machinery of generating functions for the Fibonacci sequence.
• Notes 1/24−1/27: Formal power series R[[x]]
• Notes 2/3: Exponential Formula introduction: cards, decks, hands
• Notes 2/5: Examples of exponential families
• Notes 2/7: Labeled Product Principle, ordered and unordered exponential families
• HW 2/12: Recurrences and asymptotics from generating functions, Dlog method
  −−−−−− Midterm −−−−−−
• Notes 2/26: Lagrange Inversion Formula
• Notes 2/28: Generating functions for number partitions, Euler's Pentagonal Formula
• Notes 3/10: Generating function for rooted trees.
• Notes 3/12−3/17: Otter's Formula counting unrooted, unlabeled trees
• Graph Notes from Math 481, including Planar Graphs (III) and Polyhedra (IV).
• Notes 3/31: Augmenting Path Algorithm and Menger's Theorem
• Notes 3/26−3/28: Steinitz Lemma, Steinitz Theorem, Balinski Theorem
• Notes 4/7−4/11: Tutte's Stressed Graph Theorem, the Rubber-Band Model. See also Solutions 4/7.
• Notes 4/11: Proof of Tutte's Theorem.
• Notes 4/14−4/18: Maxwell's Lifting Theorem.