### MSU MATHEMATICS

MTH 482 - Spring 2014

Old Assignments

• Instructor:  Prof. Peter Magyar,   magyar@math.msu.edu,   tel. 353-6330,   Wells Hall D-326.
Office hours:  Mon, Wed, Fri 10−11 and after each class. Also Thu afternoon by appointment.
Lecture:  Mon, Wed, Fri 11:30−12:20, Wells A-136.

• Course Information Grading, exam, and homework policies.

• Schedule:  Chapters, tests and administrative deadlines. Check the Announcements below for date changes.

• [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.

• Old Announcements

• Welcome to Math 482. This page will have all assignments and course information. (I will not be using D2L as I had planned, because fubar.)

• Quiz Wed 1/8: The first lecture will start with a quiz on the following questions.
1. Let f be any function from the set {1,2} to the set {1,2,3}. We can write f by listing its outputs: for example, the function f(1) = 3, f(2) = 2 can be written f = (3,2). Write all possible such functions.
2. Rewrite all of the above which are injective (one-to-one) functions.

• Quiz Fri 1/10: The Quiz will be analogous to HW 1/8 #3 in the case of Twelvefold Way Entry #4, the multi-choose numbers. That is, prove the Pascal's Triangle type recurrence for ((n | k)) by means of a transformation.

• Midterm Exam: Fri 2/21, in class. Come 5 min early for extra time.
To study:
• Re-do all quizzes, covering up your previous answers, then check with my answers from class notes. Make sure you understand all mistakes. I can email you any missing quizzes on request.
• Do Midterm Review HW 2/17 & 2/19. You must actually solve these to do any good, not just read the solutions.
• Review old notes, class notes, and the Wilf text.
• Review old homework, and finish problems you didn't do.
• Come to office hours in Wells D-326: Mon, Wed 10−11 and 1−3; Thu 1−3:30 .
Main topics:

• Old Homework:  Do each assignment after the lecture on that date.

I will not collect homework (except problems marked Hand In), but the next daily quiz will be based on it. You may also hand in problems marked Extra Credit, preferably within a week of the HW date. Each problem you give up on is a lost opportunity to learn: only look at the solution after a serious effort.

I will give an extra point to the first person pointing out a significant typo or other error on this page. Corrections and recent revisions are in red. Future assignments, which are tentative and may be revised, are marked in gray.

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}.

• 1/8: Twelvefold Way (1).
1. A shirt has 6 positions for buttons, which you sew on according to each rule below. For each problem, find the correct entry of the Twelvefold Way table which counts the given type of button arrangements. Evaluate this number to solve the problem. =
1. You have a supply of 3 kinds of buttons (Black, White, Red), and you sew on any 6 of them. Example: (B,W,W,W,B,B) where R does not appear.
2. Same as (a), but every color must appear. Example: (B,W,W,W,R,B).
3. Same as (a), but some positions might be left empty (−). Example: (B,−,W,W,B,−).
4. You have 9 distinct buttons (1,2,...,9), and you sew on any 6 of them. Example: (8,4,5,3,1,9).
5. The 6 positions already have 6 distinct buttons (1,2,...,6), and you snip them off and rearrange them. Example: Rearrange to (3,1,5,6,4,2).
6. You sew on 3 identical Black buttons, leaving 3 positions empty (−). Example: (B,−,B,B,−,−).
7. Same as (f), but you may sew several buttons (or none) onto each position: Example: (B,−,BB,−,−,−).
8. You sew on 10 Black buttons, allowing several at each position, but no positions empty. Example: (BBB,B,BB,BB,B,B).
2. For each of the following entries in the Twelvefold Way, compute the equivalent of Pascal's Triangle for 5 rows and columns. Start by using the definition of each number to find obvious values at the boundaries of the triangle; then use the given recurrence to compute the rest of the values. Check your work with the explicit, non-recursive formula for one sample value.
1. Entry #3: compute surj(k,n)  for n ≤ k ≤ 5. Start with surj(k,1) and surj(k,k), which are easy to compute from the definition (i.e. counting functions, not using the PIE formula). Check your work against the PIE formula for surj(5,3).
2. Entry #4: compute ((n | k)) for n,k ≤ 5 (a square of values rather than a triangle). Start with ((n | 0)) and ((1 | k)), which are obvious from the definition (and also from the explicit formula). Check your work against the explicit formula for ((5 | 3)).
3. Extra Credit: You should notice a very, very close relationship between your numbers in (b) for ((n | k)) and the usual Pascal's Triangle for (n | k). Explain how and why this happens. Is there any relation between the numbers in (a) and the usual Pascal Triangle?
3. Entry #6 in the Twelvefold Way counts arrangements of k identical balls into n marked bins with no bin empty, given by ((n | k−n)) = (k−1 | n−1). For this problem only, denote this number by a(k,n).
Problem: Use a transformation to find and prove a Pascal's Triangle type recurrence for a(k,n), similar to those for entries #3,4,5. Make a table showing your transformation for a(5,3).
Hints:
• Transform each arrangement of balls by removing one ball from the nth basket. The resulting arrangements are of two types, counted by smaller numbers of the same kind. Show that the transformation is reversible (give the inverse transformation).
• For the example of a(5,3), make a table with one column being all arrangements of 5 identical balls in 3 bins, with no bin empty: (•••,•,•), (••,••,•), (••,•,••), etc. Next to each, put the transformed arrangement in the second or third column, depending on which of the two types it is.
Solutions:

1. Match shirt-button problems to Twelvefold Way entries.
1. 3 kinds of buttons, sew any 6 of them onto the 6 positions. A choice of buttons corresponds to entry #1, a function f : [6]→{B,W,R}, where each position i is taken to its button-color f(i). The example (B,W,W,W,B,B) corresponds to f with f(1) = B, f(2) = W, f(3) = W, f(4) = W, f(5) = B, f(6) = B. The number of such f is nk = 36.

2. 3 kinds of buttons, sew on any 6 of them so that every color appears. Entry #3, functions f : [6]→{B,W,R} where all 3 outputs appear, meaning f is surjective. The number of such f is surj(6,3) = 3− (3 | 1) 26 + (3 | 2) 16.

3. Give each position one of 3 kinds of buttons or leave empty, which is like a 4th color denoted by −. Entry #1: f : [6]→{B,W,R,−}. The number is 46.

4. 9 distinct buttons (1,2,...,9), sew on any 6 of them. Entry #2, functions f : [6]→[9] with each output appearing at most once, meaning f is injective. The number is 96 = (9)(8)...(4).
5. 6 distinct buttons (1,2,...,6) are rearranged into new positions. This is a function f : [6]→[6], where the button originally at i gets new position f(i). This function must be both surjective and injective (i.e. bijective) since each position gets one and only one button. This is counted either by entry #2, giving 66 = 6! ; or by entry #3, giving surj(6,6) = 66 − (6 | 1)56 + (6 | 2)46 − (6 | 3)36 + (6 | 4)26 − (6 | 5).

These two expressions look very different, but they must give the same number, since f : [6]→[6] is injective if and only if it is surjective (this is known as the Pigeonhole Principle). Try them on Wolfram Alpha, entering (n | k) as binom(n,k), and nk as n^k. Indeed, they are both 720.

6. Sew on 3 Black buttons, leaving 3 positions empty (−). An arrangement corresponds to entry #5, classes of injective functions f : [3]→[6], where it does not matter which input goes to a given output. Thus, we may picture indistinguishable [3] as three identical balls or buttons {•,•,•} tossed into 6 labeled bins or positions, with at most one in each bin. The example: (B,−,B,B,−,−) corresponds to the three values f(1) = f(•) = 1, f(2) = f(•) = 3, f(3) = f(•) = 4. The number of such f is (n | k) = (6 | 3) = (6)(5)(4) / 3! .

7. Same as (e) allowing several buttons at each position. Entry #4, functions f : {•,•,•}→[6] with no restriction. The number is ((6 | 3)) = (6)(7)(8) / 3! .

8. Sew on 10 Black buttons, allowing several at each position, but no positions empty. Entry #6, f :  {•,•,•,•,•,•,•,•,•,•}→[6] with every output appearing, meaning f is surjective. The number is ((6 | 10−6)) = (9 | 5) = (9 | 4) = (9)(8)(7)(6) / 4! .

2. For (a), see here in the Online Encyclopedia of Integer Sequences, where the table of surj(k,n) is written row-by-row in a single sequence, surj(1,1), surj(2,1), surj(2,2), surj(3,1),...

For (b), each 45-degree diagonal of the square of ((n | k))'s is a row of the ordinary Pascal triangle. Why on earth is that??

3. Find a Pascal-type recurrence for a(k,n) = ((n | k−n)) = (k−1 | n−1), which counts arrangements of k identical balls in n marked bins, with no bin empty.

The Tranformation Principle says that if there is a reversible transformation (a one-to-one correspondence, an invertible mapping, a bijection) between all objects of one type and all objects of another, then there is the same number of objects of each type. In our case, we wish to transform an arrangement of type a(k,n) into a smaller arrangement of similar type.

Transform each arrangement of balls by removing one ball from the nth bin. If this empties the nth bin, we drop this bin and get k−1 balls in n−1 bins with no bin empty, of type a(k−1, n−1). We can reconstruct the original arrangement by restoring the nth bin with a single ball.

If the transformation does not empty the nth bin, we get  k−1 balls in n bins with no bin empty, of type a(k−1, n). We can reconstruct the original arrangement by tossing one more ball in the nth bin.

Thus the arrangements of type a(k,n) are reversibly transformed into all those of the types (k−1, n−1) and a(k−1, n), so the Transformation Principle gives:

a(k,n) = a(k−1, n−1) + a(k−1, n).

Example a(5,3) = a(4,2) + a(4,3). The transformation takes any 5 balls in 3 non-empty bins and removes one ball from the third bin, giving either 4 balls in 2 non-empty bins if the third bin is emptied, or otherwise 4 balls in 3 non-empty bins. This is reversed by restoring one more ball to the third bin.

 a(5,3) a(4,2) a(4,3) •••|•|• •••|• ••|••|• ••|•• ••|•|•• ••|•|• •|•••|• •|••• •|••|•• •|••|• •|•|••• •|•|••

• 1/10: Twelvefold Way (2).
• Notes 1/8 - 1/13.
• Stirling set partition numbers {k | n} : [HHM] p. 231−233.
• Partition numbers pn(k): [HHM] p. 218−220.
HW:
1. For the last column of the Twelvefold Way (#3,6,9,12), evaluate each entry for (k,n) = (4,2) by writing out all the objects being counted.
Hints:
• Entry #3 counts all surjective functions, in which both possible outputs {1,2} actually appear. The other entries count some of these functions as the same, if you can get one from the other by permuting the 4 inputs or the 2 outputs (switching 1↔2).
• Write each function f : [4]→[2] by listing its outputs: f = (f(1), f(2), f(3), f(4)). For example, write the function f(1) = 2, f(2) = 2, f(3) = 1, f(4) = 2 as (2,2,1,2). In this list notation, permuting the inputs means reordering the list; permuting the outputs means switching 1↔2 in each entry of the list.
• Alternatively, write f as an arrangement of balls {1,2,3,4} inside 2 output bins. For example, write the above function f(1) = 2, f(2) = 2, f(3) = 1, f(4) = 2 as 3|124. In this bin notation, permuting the inputs means replacing each ball-number with a permuted number; permuting the outputs means switching the two bins.
2. For each problem, find the entry of the Twelvefold Way table which counts the given type of arrangements. Evaluate the answer if there is a known formula.
1. Ways for three candidates (A,B,C) to split 100 votes. Example: A gets 38 votes, B gets 0 votes, C gets 62 votes.
2. Same as (a), but we record only the vote-counts, not linking them the names of the candidates . Example: Winner gets 62 votes, second place gets 38 votes, third place gets 0 votes. (Vote ties are also possible.)
3. Same as (b), but assume each candidate gets at least 1 vote. Example: Winner 62, second place 30, third place 8.
4. Ways for 6 nations (A,B,C,D,E,F) to split into three hostile alliances, so that no nation can belong to more than one.. Example: A,C,F form an alliance, B forms an alliance by itself, and D,E form an alliance. (No alliance can be empty.)
5. Same as (d), but with any number of alliances. Examples: everyone is in one big alliance; or, each nation forms an alliance by itself.
3. Partitions
• Entry #10 counts partitions: arrangements of k identical balls into n exchangeable bins, with the answer denoted by p≤n(k). Since the balls are identical, we only record how many in each bin; and since the bins can be rearranged, we always put the fullest bin first, then the second-fullest bin, etc. For example, the arrangement of balls •••|•|• is denoted (3,1,1), and p≤3(5) = 5 counts the partitions (5,0,0), (4,1,0), (3,2,0), (3,1,1), (2,2,1).
• As with other entries of the table, I will try a transformation to get a Pascal's Triangle type recurrence for p≤n(k). Given a partition (a1,...,an) with a≥ ··· ≥ an ≥ 0 and a1 + ··· + an = k, either we have a= 0, in which case we can drop an and get the partition (a1,...,an-1) of type p≤n-1(k); or we have a> 0, and we can subtract 1 from ato get the partition (a1,...,an-1, an–1) of type p≤n(k–1).
• This transformation can obviously be reversed, so we seem to have:

p≤n(k) ?=? p≤n–1(k) + p≤n(k–1).

• Dismayingly, this equation is false, as you can see by evaluating p≤2(3) = 2, p≤1(3) = 1, p≤2(2) = 2, with 2 ≠ 1 + 2, This illustrates why we need complete rigor in mathematics: the above argument is not precise enough, neglects a subtle point, and leads to a false result.
Problems:
1. Since the equation is false, there must be a step of false reasoning in the proof. Find it!
Hint: Just apply the "proof" to the counter-example. Make a table of the transformation for p≤2(3) ?=? p≤1(3) + p≤2(2), and you will see immediately where the argument is wrong. Try to explain why the obvious reverse transformation is not a true inverse mapping: what does it lack?
2. Extra Credit: Find a correct Pascal's Triangle type recurrence for p≤n(k).
Solutions:

1. From the Twelvefold Way.

Entry #3. There are surj(4,2) = 14 surjective functions f : [4]→[2]. Writing as f = (f(1),..., f(4)), they are:

(1,1,1,2)    (1,1,2,1)    (1,2,1,1)    (2,1,1,1)    (1,1,2,2)    (1,2,1,2)    (1,2,2,1)

(2,2,2,1)    (2,2,1,2)    (2,1,2,2)    (1,2,2,2)    (2,2,1,1)    (2,1,2,1)    (2,1,1,2).

Alternatively, write f as input balls {1,2,3,4} in 2 output bins:

123|4     124|3     134|2     234|1     12|34     13|24     14|23

4|123     3|124     2|134     1|234     34|12     24|13     23|14.

Entry #6. Two of the above functions count as the same if you can get one from the other by rearranging the inputs (entries in the list), for example (1,1,1,2) = (1,1,2,1). There are ((2 | 4–2)) = 3 distinct surjective functions (i.e. 3 symmetry classes of functions):

(1,1,1,2)    (1,1,2,2)    (1,2,2,2)

Alternatively, write f : {•,•,•,•} → [2] as 4 input balls in 2 output bins:

|    |    •|

Another alternative: write the number of balls in each bin (the multiplicity):

3+1    2+2    1+3.

Entry #9. The count for this entry is given by Stirling partition numbers, whose standard vertical notation is given in the Twelvefold Way table. Here I will use a non-standard horizontal notation {k | n} for these numbers, just as I write (n | k) for choose numbers.

Two functions from entry #3 count as the same if you can get one from the other by switching the outputs {1,2}, for example (1,1,1,2) = (2,2,2,1). The count is given by the Stirling number {4 | 2} = 7. distinct surjective functions:

(1,1,1,2)    (1,1,2,1)    (1,2,1,1)    (2,1,1,1)    (1,1,2,2)    (1,2,1,2)    (1,2,2,1).

Alternatively, write a function f : [4]→{•,•} as input balls {1,2,3,4} in 2 output bins, remembering that switching bins gives an equivalent function:

123|4    124|3    134|2    234|1    12|34    13|24    23|14

Entry #12: Two functions count the same if you can get one from the other by a combination of the above two equivalences. Threre are p2(4) = 2 distinct surjective functions:

(1,1,1,2)    (1,1,2,2)

Alternatively, write a function f : {•,•,•,•}→{•,•} as 4 input balls in 2 output bins, remembering that switching bins gives the same function.

•••|•    ••|••

Another alternative: write the number of balls in each bin (the multiplicity):

3+1    2+2.

2. Match word problems to the Twelvefold Way.

1. Three candidates (A,B,C) split 100 votes. Entry #4: 100 identical votes into 3 bins A,B,C. Answer ((3 | 100)).

2. Entry #10: 100 identical votes into 3 exchangeable bins. Answer: p≤3(100), which has no simple formula.

3. Entry #12: 100 identical votes into 3 exchangeable non-empty bins. Answer: p3(100), which has no simple formula.

4. Nations (A,B,C,D,E,F) split into three exclusive non-empty alliances are like 6 marked balls put into 3 non-empty, exchangeable bins. Entry #9:

{6 | 3} = 13! ( 36  – (3 | 1) 26 + (3 | 2) 1).

5. Nations (A,B,C,D,E,F) to split into any number of exclusive non-empty alliances. Entry #7: {6 | 1} + {6 | 2} + ··· + {6 | 6}. This is also the Bell number B(6), at the bottom of the Twelvefold Way.

3. To analyze the false equation p≤2(3) ?=? p≤1(3) + p≤2(2)write the partitions of type p≤2(3) as (a1, a2) with a1  a2 and a1 + a2 = 3. If a= 0, the transformation drops it to give the partition (a1) of type p≤1(3); if a> 0, the transformation subtracts 1 from it to give the partition (a1, a– 1) of type p≤2(2). The table is:

 p≤2(3) p≤1(3) p≤2(2) (3,0) (3) (2,1) (2,0) ?? (1,1)

Clearly the transformation is not fully reversible: the reverse rule will take every output of the transformation back to the input it came from, but this rule does not work on every entry in the output columns. The reverse rule for the second column takes (a1) back to (a1, 0) = (a1, a2); and for the third column, it should take (b1, b2) = (a1, a– 1) back to (b1, b2 + 1) = (a1, a2), meaning (1,1) goes back to (1,2), which is not a valid input.

Thus, the reverse transformation is not defined on the desired set of outputs, and the original transformation is a one-to-one (injective) mapping, but not an onto (surjective) mapping. This will happen in every case with n > 1, so in fact we get the inequality  p≤n(k) < p≤n–1(k) + p≤n(k–1).

• 1/13: Other sequences
1. Stirling cycle numbers
1. Write all the permutations counted by the cycle number [4 | 2] = 11, in both cycle and two-line notation.
2. Write the table of the transformation for [4 | 2] = [3 | 1] + 3 [3 | 2].
2. Let abe the number of sets S ⊂ [n] which do not contain any two consecutive numbers i, i+1. For example, a= 8 counts the sets:

S = {}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4}.

A set like S = {1,3,4} is not counted, since it contains 3,4.
Problem: Use a transformation to find and prove a recurrence for an, and show it equals one of the types of numbers on the Twelvefold Way handout.
3. An unlabeled ordered tree is a schematic family tree starting from an ancestor node at the top, with child nodes attached below it with the eldest at left, then possible grandchild nodes below them, and so on. For example, the unlabeled ordered trees with 4 nodes are:

The difference between the third and fourth trees is whether the grandchild belongs to the older or the younger child. Let on be the number of ordered trees with n nodes, so that the above example counts o4 = 5.
Problem: Use a transformation to find and prove a recurrence for on, and show it equals one of the types of numbers on the Twelvefold Way handout.
Hint: Decompose a tree into a pair of trees by disconnecting the oldest child, and making it the ancestor of its own tree. For each possible size of the new trees, the number of such pairs is a product of two smaller oj's.
4. Extra Credit: [W] Ch 1, Ex 21(a), p 28: Differentiating eex.
Solutions:

1. The transformation table for the Stirling cycle number identity [4 | 2] = [3 | 1] + 3 [3 | 2] is:

 [4 | 2] [3 | 1] 3 [3 | 2] (1)(234) 2 , (1)(23) (1)(243) 3 , (1)(23) (2)(134) 1 , (2)(13) (2)(143) 3 , (2)(13) (3)(124) 1 , (3)(12) (3)(142) 2 , (3)(12) (4)(123) (123) (4)(132) (132) (12)(34) 3 , (12)(3) (13)(24) 2 , (13)(2) (14)(23) 1 , (1)(23)

Note that (1)(432) = (1)(243) and (12)(34) = (12)(43), etc., so there are no more permutations to list in the first column. Also, the third column contains every possible combination of a number 1 ≤ j  ≤ 3 and a permutation τ of type [3 | 2].

2. Deletion transform. A set of type an is S ⊂ [n] containing no consecutive numbers. In case n ∉ S, transform S to S' = S ⊂ [n–1], a set of type an−1. In case n ∈ S, we must have n–1 ∉ S (otherwise S would contain consecutive n–1, n). Transform S by removing n, getting S' = S\{n} ⊂ [n–2] of type an–2. This transformation is reversible, so we get an = an–1 + an–2, the same recurrence as for Fibonacci numbers Fn. Also, the initial values are a= F2 = 1 and a= F3 = 2, so thereafter we continue to get a= Fn+2.

3. Left-right decomposition transform. Let on count unlabeled n-node ordered trees. If we transform such a tree T by disconnecting the oldest (leftmost) child, we get a pair of trees (T1, T2), where T1 is the tree starting from the oldest child, and T2 is what remains of the original tree. Also, any pair (T1, T2) can be re-connected to restore T. If we assume Thas i nodes and Thas n – i nodes, then the number of possible (T1, T2) is oion–i. Summing over all possiblilities for i gives:

on  =  o1on–1 + o2on–2  + o3on–3 + ... + on–1o1

If we define cn = on+1, this means:

cn = on+1   =   o1on + o2on–1 + o3on–2 + ... + ono1   =   c0cn–1  + c1cn–2  + c3cn–3  + ... + cn–1c0

which is precisely the same recurrence as for the Catalan numbers Cn. Also we have the same initial value c0 = o1 = 1 = C0. The same recurrence starting from the same initial value will produce the same numbers: cn = Cn. That is,  on = cn–1 = Cn–1.

• 1/15: Review Method of Generating Functions
• Notes 1/15.
• [HHM] Ch 2.6 p. 164−175.
• 481 HW 9/18−9/25. Dice-throws are discussed in HW 9/23 #1 and 9/25 #3.
HW:
1. Starting with the definition of the multi-choose number ((n | k)), use the Method of Generating Functions to derive an explicit formula for ((n | k)), different from the bins-and-beans formula ((n | k)) = (k+n−1 | k).
• Step 0: Specify a sequence. Fix n to be constant, and consider the sequence ak = ((n | k)), so that the generating function is:
f(x) = ∑k≥0 akxk = ((n | 0)) + ((n | 1))x + ((n | 2))x2 + ...
• Step 1: Using combinatorial properties of {ak}, find a simple formula for the generating function f(x). In this case, we will use the Product Principle for choosing M to get a product formula for f(x).
The multiplicity transform (see 481 Notes 9/6) writes a multi-set by listing how many of each kind. For example, fixing n = 5 kinds, the multiset M = {1,1,1,3,4,4,5} is represented as (3,0,1,2,1), since it has 3 ones, 0 twos, 1 three, 2 fours, 1 five.
This leads to an algorithm for constructing all the multisets M, for arbitrary size k:

(choose M from n kinds, any size)   ⇔   (0 ones or 1 ones or 2 ones or …) and (0 twos or 1 twos or 2 twos or …) and … and (0 n's or 1 n's or 2 n's or …).

Problem: Translate this algorithm into an algebraic formula using the logic-to-algebra chart in today's Notes.
Hint: Choosing mulitplicity j of any kind increases the total size of M by j, so this choice should be translated into xj. Since the logical expression is infinte, the algebraic expression will involve infinte series. Replace these with a simple finite expression, using the Known Series formulas.

• Step 2: Use function theory (algebra, calculus) to find the Taylor series of f(x), giving an explicit formula for the coefficients ak. In this case, you can use Taylor's Formula ak = f(k)(0)k!, where f(k)(x) means the kth derivative of f(x). (This formula is always valid, but hardly ever useful, because the derivates get too complicated. In this case, they are manageable.)
2. We have three kinds of coins: one-euro, gold two-euro, and silver two-euro. Question: How many ways to make a handful of 20 euros from these three kinds of coins? For example, one way is: 6 one-euros, 3 gold two-euros, and 4 silver two-euros. Use the Method of Generating Functions to solve this problem.
Hints:
• Step 0: Replace one of the numbers in the problem with k, getting a natural sequence of problems a0, a1, a2,..., one of which is the orginal problem.
• Step 1: Use the Product Principle for choosing a handful of coins (with any value), then translate logic to algebra. Note that a one-euro coin translates to x1, but a two-euro coin adds 2 to the value of the handful, so it translates to x2.
• Step 2: Use the identity:   1(1−x)  =  (1+x) ⋅ 1(1−x2) . This will allow you to write f(x) as a polynomial times a negative-power binomial from the Known Series. Partial fraction decomposition is possible, but not advisable in this case.
3. We have the same three kinds of coins as in Prob. 2, but now we lay them out in ordered rows, rather than unordered handfuls.
1. Question: How many ways to make a row of 14 coins with value 20 euros? For example, denoting the coins as 1,2g,2s, one possible row is:
(2g,1,1,1,2s,1,1,2g,2s,2s,1,2g,1,1).
Use the Method of Generating Functions to solve this problem.
Hints:
• Step 0: Replace one of the numbers in the problem with k. Replace the number which makes the most natural generalization of the original problem, changing the underlying structure as little as possible.
• Step 1: Product Principle again, but now with 14 successive choices of coin, rather than just 3 choices about how many of each.
• Step 2: Binomial Theorem.
2. Extra Credit: How many ways to make a row of any length with value 20 euros? For example, the shortest row has 10 coins, a mixture of 2g and 2s; and the longest row has 20 coins, all 1's. Use the Method of Generating Functions to solve this problem.
Hints:
• Step 1: The choice algorithm uses the Sum Principle as well as the Product Principal: split into cases, depending on the length of the row.
• Step 2: Partial fractions.
Solutions:

1. A Generating Function formula for multi-choose numbers ak = ((n | k)).
Step 1:
Translating the choice algorithm into algebra according to the chart:
f(x) = (x0 + x1 + x2 + ...) ⋅ (x0 + x1 + x2 + ...) ⋅ ... ⋅ (x0 + x1 + x2 + ...)
= (1 + x + x2 + ⋅⋅⋅)n.
The infinite series in parentheses is a geometric series, which by the Known Series is 1(1−x). Thus f(x) = 1(1−x)n.
Step 2:
Taking derivatives of f(x) = (1−x)−n, mindful of the Chain Rule:
f '(x)  =  (−n)(1−x)−n−1(−1)  =  n(1−x)−n−1,

f ''(x)  =  n(−n−1)(1−x)−n−2(−1)  =  n(n+1)(1−x)−n−2,

f(k)(x) = n(n+1)(n+2)...(n+k−1)(1−x)−n−k

Now Taylor's Formula gives:
ak  =  f(k)(0)k!  =  n(n+1)(n+2)...(n+k−1)(1−0)−n−kk!
=  n(n+1)(n+2)...(n+k−1)k!
Now using the rising-power notation nk = n(n+1)(n+2)...(n+k−1), which is pronounced "n to the k rising", we get:

((n | k))  =  ak  =  nk / k! .

This is of course equivalent to ((n | k)) = (k+n−1 | k), but this form is neater, and nicely analogous to (n | k) = nk / k! .

2. Counting handfuls of three kinds of euro coins (one, gold two, silver two) worth a total of 20 euros. Handfuls are multi-sets, so this will be similar to Prob. 1.

Step 0: Let ak be the number of handfuls of the three kinds of coins worth a total of k euros. This is the natural generalization of the problem, rather than changing the kinds of coins.

Step 1:

Because a handful is unordered, all that matters is how many of each kind of coin. The choice algorithm is:

(choose a handful, any value)   ⇔   (0 ones or 1 ones or 2 ones or …) and (0 golds or 1 golds or 2 golds or …) and (0 silvers or 1 silvers or 2 silvers or …).

Translating into algebra, replacing one by x1, gold and silver by x2:

f(x)  =  (x0 + x1 + x2 + ...) ⋅ (x0 + x2 + x4 + ...) ⋅ (x0 + x2 + x4 + ...)
=  (1 + x + x2 + …)(1 + x2 + x4 + …)2.
Using z = x2 in the known geometric series 1(1−z) = 1 + z + z2 + …, we find 1 + x2 + x4 + … = 1(1−x2). Hence:
f(x)  =  1(1−x)(1−x2)2
Step 2:
The denominator is factorable as (1−x)3 (1+x)2, so a partial fraction expansion would be of the form:
f(x)  =  A(1−x) + B(1−x)2 + C(1−x)3 + D(1+x) + E(1+x)2 .

Yuck! Not worth the trouble! Hard to compute, and the resulting formula would be a mess, anyway.
A much better trick is the following: since 1−x2 = (1−x)(1+x), we can substitute 1(1−x)  =  (1+x) ⋅ 1(1−x2) to consolidate the denominator as a power of a single binomial factor:

f(x)   =   (1+x)(1−x2)1(1−x2)2   =   (1+x) ⋅ 1(1−x2)3

Knowing the negative-power binomial series 1(1−x2)3   =   ∑k≥0 ((3 | k)) x2k, we find:

f(x)   =   (1+x) ⋅ ∑k≥0 ((3 | k)) x2k   =   ∑k≥0 ((3 | k)) x2k  +  ∑k≥0 ((3 | k)) x2k+1

Using ((3 | k)) = (k+2 | k) = (k+2 | 2) = (k+2)(k+1)/2, we simplify:

a2k  =  a2k+1  =  ((3 | k))   =   ½(k+2)(k+1).

The answer to our original problem is therefore:   a20  =  a2(10)  =  ((3 | 10))  =  ½(12)(11)  =  a2k  =  66.

Follow-up: It is wise to check this with Wolfram Alpha (which I should have done originally): the power series of   f(x) = 1(1−x)(1−x2)   is indeed:

f(x)  =  1 + x + 3x2 + 3x3 + 6x4 + 6x5 + 10x6 + 10x7 + 15x8 + 15x9 + 21x10
+ 21x11 + 28x12 + 28x13 + 36x14 + 36x5 + 45x16 + 45x17 + 55x18 + 55x19 + 66x20 + ...

This can be explained combinatorially as follows: to get a total value of 20 euros, we must have an even number of one-euro coins. Grouping the one-euros into pairs, we can think of this as 3 kinds of 2-euro coins: one-euro pair, gold two-euro, silver two-euro. The ways to choose a multi-set of 10 of these 2 kinds is ((3 | 10)). This is much clearer in retrospect, once the Generating Function Method has given us the answer.

3. (a) Counting rows of 14 coins of three kinds (one, gold two, silver two) worth a total of 20 euros. This will be similar to rolling a sequence of dice.

Step 0: Let ak be the number of rows of 14 of the three kinds of coins worth a total of k. This is the natural, minimal generalization of the problem, rather than changing the length of a row or the kinds of coins. It would be possible to replace 14 with k, but this would not yield a tractable generating function.

Step 1:

Because a row is ordered, we must choose the 14 coins one by one. The choice algorithm is:

(choose 14 coins, any total value)   ⇔   (coin 1 is one or gold or silver) and (coin 2 is one or gold or silver) and … and (coin 14 is one or gold or silver)

Translating into algebra:

f(x)   =   (x1 + x2 + x2) ⋅ … ⋅ (x1 + x2 + x2)   =   (x+2x2)14.

Step 2:
Factoring and applying the Binomial Theorem:

f(x)   =   x14 (1+2x)14   =   x14k=014 (14 | k) (2x)k   =   ∑k=014 (14 | k) 2k xk+14.

We want the coefficient of x20, which corresponds to k = 6, i.e.   a20 = (14 | 6) 26.
Follow-up: This can be explained combinatorially as follows: to get a total value of 20 from 14 coins, we must have 8 ones and 6 twos. Choose 6 of the 14 positions for the twos, giving (14 | 6) possibliities; then choose whether each two is a silver or a gold, giving 26 possibilities. Again, this is clear once we know the answer!

• 1/17: Generating functions and recurrences (1)
• Notes 1/15: Memorize the Known Series
• Notes 1/17: The machinery of enumeration for the Fibonacci numbers
• [W] Ch 1, p. 1−11.
• [HHM] Ch 2.6 p. 177−183.
• 481 HW 9/27−9/30
HW:
1. Generating function warmups: [W] Ch 1, p 24, Ex #1(b,g), 3(b,e,h).
2. Problem: For any number r, find an explicit formula for the summation:
ak   =   r + 2r2 + 3r3 + … + krk.
1. Find a simple formula for the Taylor series:   ∑k≥0 rkxk. Hint: Known series, with a substitution.
2. Find a simple formula for the Taylor series:   ∑k≥0 k rkxk. Hint: Perform a suitable operation on the formula from part (a).
3. Step 1: For the sequence ak above, find a simple formula for the generating function f(x) = ∑k≥0 akxk.
4. Step 2: Find the Taylor series of the formula from part (c).
Hint: You will need a partial fraction decomposition of the form:
A(1−x) + B(1−rx) + C(1−rx)2.
3. Goal: Approximate the numbers ak defined by the recurrence:
ak = ak−1 + ak−3   for   k ≥ 3,
with initial values a0 = a1 = a2 = 1.
1. Step 1: Find a simple formula for the generating function:   f(x) = ∑k≥0 akxk.
2. Preliminaries to Step 2. The denominator p(x) = x3 + x − 1 has a real root α and two complex conjugate roots β, γ. Compute α to 5 decimal places. Also, letting |z| denote the length or modulus of a complex number, show that:
|α| < 1 < |β| = |γ|.
Hint: Ask Wolfram Alpha, or use Newton's Method with a spreadsheet or calculator.
3. Note that the above polynomial can be written as:
p(x)  =  x3 + x − 1  =  (x−α) (x−β) (x−γ).
The quotient q(x) = p(x) / (x−α) can thus be written as:
q(x) = (x−β) (x−γ) = x2 − (β+γ)x + βγ.
Problem: Perform long division of polynomials to get a different expression for q(x) = (x3 + x − 1) / (x−α), writing the coefficients in terms of α. (Compute with α just as with any real number, like π or √2, keeping in mind that α3 + α − 1 = 0 by definition.) Then determine β+γ and βγ in terms of α.
4. Step 2: To get the dominant term in the Taylor series of f(x), find the coefficient A in the partial fraction decomposition:
f(x)   =   A(1 − x/α) + B(1 − x/β) + C(1 − x/γ).
Your answer for A should be in terms of α, which was computed in part (b).
5. Explain why we have a good approximation akAαk for large k. Apply this approximation to a10, and compare to the exact value.
4. Extra Credit:
1. For the Fibonacci sequence Fk, peform Step 1 of the Method in a different way, not using the recurrence formula. Start from the combinatorial model:
Fk = #{ (a1,...,ar)  with  r≥1 and a1+...+ar = k−1  and  ai = 1 or 2 }.
Then use the Product and Sum Principles: write a choice algorithm split into cases depending on the value of r, with each case consisting of a sequence of independent choices.
2. From Prob 3 above, consider the sequence defined by the recurrence ak = ak−1 + ak−3 for k ≥ 3, starting from a0 = a1 = a2 = 1. This has generating function f(x)   =   1(1 − x − x3).
Reverse the analysis of part (a) above to get a combinatorial model for an: that is, a set of simple combinatorial objects which are counted by an.
Solutions:

1. See [W] p 197.

2. Summing the series ak = r + 2r2 + 3r3 + ... + krk.
1. Substituting z = rx into the Known Series 1(1−z) = ∑k≥0 zk gives:
k≥0 rkxk   =   ∑k≥0 (rx)k   =   1(1−rx).
2. Taking the left side of the above equation, then differentiating and multiplying by x gives: gives:
x ddxk≥0 rkxk   =   x ∑k≥0 rk kxk−1   =   ∑k≥0 krkxk.
Applying the same operations to the right side of the equation:
x ddx 1(1−rx)   =   rx(1−rx)2.
Hence:
k≥0 krkxk   =   rx(1−rx)2.

3. Now we consider f(x)  =  ∑k≥0 akxk, for ak = ∑j=1k j rj
Step 1: We can define ak by the recurrence for ak = ak−1 + krk for k≥1, starting from a0 = 0. Substituting this into the generating function:
f(x)  =  ∑k≥0 akxk  =  a0 + ∑k≥1 (ak−1 + krk)xk .
Distrubuting the summation and factoring out x, then substituting the definition of f(x) and the series formula from part (b):

f(x)  =  0  +  ∑k≥1 ak−1xk  +  ∑k≥1 krkxk
=  x∑k≥1 ak−1xk−1  +  ∑k≥1 krkxk
=  x f(x)  +  rx(1−rx)2.

That is, we have the equation:
f(x)  =  x f(x)  +  rx(1−rx)2.
Solving:
f(x)  =  rx(1−x)(1−rx)2.

4. Step 2: We want to write f(x) in terms of Known Series, in this case as a partial fraction decomposition:
f(x)  =  rx(1−x)(1−rx)2  =  A(1−x)  +  B(1−rx)  +  C(1−rx)2.
Since the right side has a known Taylor series (substituting z = rx into the Known Series), this will immediately allow us to write:
ak  =  A  +  Brk  +  C ((2 | k)) rk.
All we need is to determine the constants A,B,C.
• Clearing denominators in the equation for f(x) gives:
rx  =  A(1−rx)2 + B(1−x)(1−rx) + C(1−x).
This is an identity of quadratic polynomial functions, which should hold for all values of x. We could expand the right side and equate the 3 coefficients on the two sides, giving 3 linear equations in the 3 variables A,B,C, which we could then solve by Gaussian elimination.
• A quicker way is as follows. Substituting x = 1 makes two of the terms vanish:
r(1)  =  A(1−r)2 + B(0) + C(0),
so A = r(r−1)2. Similarly, substituting x = 1r gives C = r(r−1). Substituting one more value, say x = −1, gives an equation for the remaining unknown B:
r(−1) = A(1+r)2 + B(2)(1+r) + C(2),
which we can solve to get: B = − r2(r−1)2.
• The laziest way is just to ask Wolfram Alpha for: partial fractions rx/((1-x)(1-rx)^2). This is fine, so long as you know how the computer gets its answer: don't use it as a magic oracle of mathematical wisdom.
Anyway, we get, using ((2 | k)) = k+1:
ak   =   A  +  Brk  +  C ((2 | k)) rk.
=   (krk+2 − (k+1)rk+1 + r)(r−1)2
This is messy, but can't be simplified.

Follow-up: Compare this to the sum of a finite geometric series:

1 + r + r2 + ... + rk   =   (rk+1−1) (r−1) .

Once we have our formula, we can prove it very easily, by multiplying out (1−r)2 (r + 2r2 + ... + krk), and finding we can cancel all the terms except for krk+2 − (k+1)rk+1 + r.
We can also check the formula in special cases. For example, for r = 0 we get ak = 0, as expected. For r = 1, we get ak = 1 + 2 + ... + k. Our formula is not valid at r = 1 since the denominator vanishes. However, we can apply L'Hopital's Rule twice as r → 1, giving:

ak   =   (k(k+2)(k+1) − (k+1)(k+1)k)2   =   ½k(k+1),
which is indeed correct.

3. Solve the recurrence: ak = ak−1 + ak−3 for k ≥ 3, starting from a0 = a1 = a2 = 1.
1. Step 1: We again substitute the recurrence into the generating function, to get an algebraic equation involving f(x):
f(x)   =   ∑k≥0 akxk  =  a0 + a1x + a2x2 + ∑k≥3 (ak−1 + ak−3)xk
=   1 + x + x2 + ∑k≥3 ak−1xk + ∑k≥3 ak−3xk
=   1 + x + x2 + x ∑k≥3 ak−1xk−1 + x3k≥3 ak−3xk−3
=   1 + x + x2 + x (f(x) − a0 − a1x) + x3 f(x)
Substituting a0 = a1 = 1 and simplifying, we find that the function f(x) satisfies:
f(x)   =   1 + x f(x) + x3 f(x) .
Solving, we get our simple formula:

f(x)   =   1(1 − x −x3).

This is almost (but not quite!) the same as the Fibonacci generating function x(1 − x −x2) , which is derived in exactly the same way.

2. For the polynomial   p(x) = x3 + x − 1, Wolfram Alpha gives the roots:
α ≅ 0.68233,     β ≅ −0.34116 + 1.16154 i,     γ ≅ −0.34116 − 1.16154 i
The real root is clearly the smallest, with |α| = α < 1, and the pair of complex conjugate roots are larger, with |β| = |γ| ≅ 1.2 > 1.

3. Long division of the form: x−α ) x3 + 0x2 + x − 1  gives the quotient q(x) = x2 + αx + (α2+1), with remainder α3 + α − 1 = 0. Comparing this with q(x) = x2 − (β+γ)x + βγ, we find:
β + γ = −α     and     βγ = α2 + 1.

4. Step 2: To get an explicit formula for ak, we would determine the coefficients of the partial fraction expansion:
f(x)   =   1(1 − x −x3)   =   A(1−x/α)  +  B(1−x/β)  +  C(1−x/γ).
Such an expression exists because the left and right sides have the same horizontal and vertical asymptotes: y = 0 and x = α, β, γ. Note that substituting z = x/α, x/β, x/γ into the geometric series for 1(1−z) this will immediately give the Taylor series of f(x), so that
ak  =  Aαk  +  Bβk  +  Cγk .
However, we would like a neater formula, depending only on the real root α. In part (d), we will show that there is a good approximation akAαk , dropping the last two terms of the above exact formula. To get this, we only need to find A.

Writing the denominator as 1−x− x3 = −(x−α)(x−β)(x−γ) and clearing denominators, we get:

1  =  Aα(x−β)(x−γ) + Bβ(x−α)(x−γ) + Cγ(x−α)(x−β),

and substituting x = α gives A = 1α(α−β)(α−γ), which we can simplify by part (c) as:

A  =  1α(α2 − (β+γ)x + βγ)  =  1α(3α2+1) .

Hence we have the approximation:

ak1(3α2+1)αk+1 ,

where α ≅ 0.68233 is the unique real root of x3 + x − 1 = 0.

5. Follow-up: Why is the above approximation very accurate for large k? Because 1|α| ≅ 1.47, whereas 1|β| = 1|γ| ≅ 0.83. Hence the A term of the exact formula grows exponentially, whereas the B and C terms shrink exponentially to zero.

Applying the above approximation to k = 10, we get a10 ≅ 27.95, whereas the exact value is 28. Not bad!

Let us compare ak to the Fibonacci sequence Fk. We can see from the recurrence that ak grows more slowly than Fk : the reproduction is more delayed in ak. And indeed, ak ≅ const × 1.47k, whereas we previously showed the approximation Fk ≅ const × 1.62k.

• 1/22: Generating functions and recurrences (2)
• [W] Ch 1, p. 11−21.
• Notes 1/17. Generating Functions imply:
• Asymptotic approximations, by taking the dominant term corresponding to the smallest vertical asymptote.
• Recurrences, by clearing denominators and equating coefficients.
HW:
1. In class, we found the generating function of the Stirling partition numbers {n | k} for fixed k ≥ 1:

fk(x)   =   ∑n≥k {n | k} xn   =   xk(1 − x)(1−2x)…(1−kx) .

Work out the constants A1,..., Ak in the partial fraction decomposition:

fk(x)   =   A1(1 − x)  +  A2(1 − 2x)  +  ...  +  Ak(1 − kx) .

Use this to re-derive the PIE formula for Stirling partition numbers from the Twelvefold-Way, combining entries 3 & 9.
2. A set enumeration problem: [W] Ch 1, p 26, Ex #12. Let a(n,k) be the number of k-element subsets S ⊂ [n] which do not contain any two consecutive numbers i, i+1. For example, a(6,3} = 4 counts the sets S = {1,3,5}, {1,3,6}, {1,4,6}, {2,4,6}; but a set like S = {1,3,4} is not counted, since it contains 3,4.
1. Find the Pascal-triangle type recurrence satisfied by these numbers
2. Take a suitable generating function, and find an explicit formula for a(n,k).
Hint: You must decide whether to hold n or k fixed, taking the other as the summation variable. Compare with [W] p. 14−16.
3. Comparing with HW 1/13 #2, give a formula for the Fibonacci numbers Fk in terms of the a(n,k)'s found in part (b).
3. In today's Quiz, we showed that the recurrence sequence ak = 2ak−1 + 1 for k≥1, with a0 = 2, has generating function
f(x)   =   (2−x)(1−2x)(1−x) .
By decomposing the generating function into partial fractions, we obtained the explicit formula ak = 3(2k) − 1.
1. We can also go backwards: knowing the generating function, we can deduce the recurrence formula. Partially clear the denominator to get the equation:
f(x) (1−2x)   =   (2−x)(1−x)   =   1  +  1(1−x) .
Expand into Taylor series on both sides, and equate the coefficient of xk on the left with the corresponding coefficient on the right. Show that this recovers the original recurrence formula: that is, the generating function "knows" the recurrence for the coefficients.
2. Repeat part (a), clearing denominators in different ways, so the left side is f(x)(1−x), or f(x)(1−2x)(1−x). Expanding both sides into Taylor series, derive new, unexpected recurrences for ak.
4. Extra Credit: From HW 1/17 #3, consider the sequence defined by the recurrence ak = ak−1 + ak−3 for k ≥ 3, starting from a0 = a1 = a2 = 1. This has generating function:   f(x)   =   1(1 − x − x3) .
Reverse the analysis of HW 1/17 #4(a): starting with the generating function, find a combinatorial model for an, meaning a set of simple combinatorial objects which are counted by ak.
Solutions:

1. See [W] p 18, where our fk(x) is called Bk(x). Or see [HHM] Ch 2.8.3 p. 234−235.

2. Set enumeration. The coefficients which we denote a(n,k) are called f(n,k) by Wilf. For (a), (b) see [W] Solutions p 199, Ch 1 #12. For (c), see p 200, #13.

3. Generating functions ⇒ recurrences.
1. We expand the equation:
f(x) (1−2x)   =   (2−x)(1−x)   =   1  +  1(1−x)

a0  +  a1x  +  a2x2  +  a3x3  +  ....   =   1 + 1 + x + x2 + x3 + ...
−2a0x − 2a1x2 − 2a2x3 − ...

Since the Taylor coefficients of any function are unique, each coefficient on the left must equal the corresponding coefficient on the right, and we obtain: a0 = 2,   a1 − 2a0 = 1,   a2 − 2a1 = 1, etc., and in general:   ak − 2ak−1 = 1. That is, ak  =  2ak−1 + 1 for k≥1, which is the original recurrence.

2. Clearing denominators in the second way:
f(x) (1−x)   =   (2−x)(1−2x)   =   12  +  (32 ) 1(1−2x)

a0  +  a1x  +  a2x2  +  a3x3  +  ....   =   12 + 32 + 32 (2x) + 32 (22x2) + 32 (23x3) + ...
−a0x  −  a1x2  −  a2x3  −  ...

Equating coefficients, we find  ak − ak−1 = 3(2k−1)  for  k≥1. Unravelling this recurrence, we find, for k≥1:
ak = 5 + 3(2) + 3(22) + 3(23) + ... + 3(2k−1).

Clearing denominators in the third way:

f(x) (1 − 3x + 2x2)   =   f(x) (1−x)(1−2x)   =   2 − x

a0  +  a1x  +  a2x2  +  a3x3  +  ....   =   2 − x + 0x2 + 0x3 + ...
−3a0x − 3a1x2 − 3a2x3 − ...
2a0x2 + 2a1x3 + ...

That is,  ak − 3ak−1 + 2ak−2 = 0  for  k≥2, or:  ak  =  3ak−1 − 2ak−2  for  k≥2. We didn't expect that!

• 1/24: Formal power series
Reading: Notes 1/24 and [W] Ch 2, pp 30-39.
HW:
1. Reciprocals in R[[x]]. To compute 1f(x) , you can work coefficient by coefficient using the recursive formula in the Lemma above. Alternatively, if a0 = 1, substitute the series  z  =  −∑n≥1 anxn  into the geometric series 1(1−z)  =  1 + z + z2 + ⋯ .
1. [W] Ch 2 p 65 Ex #1. Hint: For part (a), start by expanding cos(x) into a Taylor series using Taylor's Formula.
2. Compute the reciprocal of  f(x) = 1 + ∑n≥1 nn xn, up to the x3 term.
3. Prove that if f(x) = a1x + a2x2 + ... has a0 = 0, then f(x) has no reciprocal in R[[x]]: that is, there is no g(x) ∈ R[[x]] with f(x) g(x) = 1.
2. [W] p 24, Ch 1 Ex #1, 3. Hint: You will need to understand Rules 1−5, [W] pp 33−38.
3. Prove that if f(x) = ∑n≥0 anxnR[[x]] satisfies f '(x) = f(x), then:
f(x)   =   c exp(x)   =   c(1 + x + x22! + x33! + ⋯)
Note: You cannot use the usual theory of differential equations, since that is only valid for convergent power series. You must work coefficient by coefficient.
4. Catalan numbers Cn.
Step 1. Show that the Catalan recurrence:
Cn   =   i=0 n−1 CiCn−1−i ,
starting with C0 = 1, imples the generating function equation:
f(x)   =   1 + x f(x)2.
Deduce that:
f(x) = 12x (1−√1−4x ).
Step 2. Find the Taylor series of x f(x)  =  ½ − ½√1−4x , and derive the explicit formula: Cn = 1(n+1) (2n | n).
Hint: Use Taylor's Formula, or the Known Series   (1+z)n   =   ∑k≥0 nkk! zk   with  n = ½  and  z = −4x .
5. Extra Credit: Recall the Axioms 1− 8 of a ring, and also Axiom 9, multiplicative commutativity: ab = ba. Prove all the Axioms 1−9 for R[[x]], showing it is a ring. To prove each equation, you must evaluate the formal series on the left and right sides, according to the definitons of + and , and check that the coefficients are the same.
Solutions:

1. Reciprocals
1. To start the first part, find the series cos(x) = ∑n≥0 anxn via Taylor's Formula an = f(n)(0)n! , applied to the derivatives  cos'(x) = −sin(x),  cos''(x) = −cos(x),  cos'''(x) = sin(x),  cos(4)(x) = cos(x).  Then:
cos(x)  =  1 − x22! + x44! − ⋯ .
Then apply the formula from the Lemma. For the alternative method based on the geometric series, see [W] p 202 Solution #1.

2. Starting with a0 = 1 and an = nn, and using the formula from the Lemma, we get: b0 = 1a0 = 1; and b1 = − a1b0a0 = −1,  then:
b2 = − 1a0(a1b1 + a2b0) = −(−1 + 22) = −3 ,
b3 = − 1a0(a1b2 + a2b1 + a3b0) = −(−3 − 22 + 33) = −20 .
Hence the reciprocal series starts as:  g(x) = 1f(x) = 1 − x − 3x2 − 20x3 − ⋯ . We can verify this by typing into Wolfram Alpha:
power series 1/(1 + x + 2^2 x^2 + 3^3 x^3)
Since the denominator is accurate up to the x3 term, the reciprocal power series will also be accurate up to the x3 term, but no farther.
There is no reason to expect any simple pattern in the bn coefficients, or any simple formula for g(x). However, we know such a g(x) exists, since the bn are defined recursively: a recursive definition is perfectly rigorous, even if it is not very pretty.

3. Proof: Let  f(x) = a1x + a2x2 + ⋯ have  a0 = 0. Then for any  g(x) = b0 + b1x + b2x2 + ⋯, we have:
f(x) g(x)  =  a1b0x + (a1b1+a2b0)x2 + ⋯ .
Since this product has constant term 0, it can never equal 1 = 1 + 0x + 0x2 + ⋯, which has constant term 1. Thus, f(x) g(x) ≠ 1 for any possible series g(x).

2. See [W] p 197, Solutions #1, 3. You should be able to work out the derivatives explicitly, so review.

3. Given an arbitrary unknown f(x) = ∑n≥0 anxnR[[x]], its derivative is f '(x) = ∑n≥1 nanxn−1 = ∑n≥0 (n+1}an+1 xn. By definition, the equation f '(x) = f(x) means that the coefficients on the two sides are equal: that is, an = (n+1)an+1. Thus, we have the recurrence: an+1 = an(n+1) for n≥1, starting from some constant a0 = c. This obviously solves to: an = c 1n!, and f(x) = ∑n≥0 c xnn! = c exp(x) as desired. Here we consider exp(x) = ∑n≥0 xnn! as a known series, or simply a definition of exp(x).

4. Catalan numbers. Step 1. See [HHM] pp 186-187 or [W] p 44.

Step 2. From Math 481 HW 10/4, we recall: h(x) = ½ − ½(1−4x)1/2 ,   h'(x) = (1−4x)−1/2 ,   h''(x) = ½(4)(1−4x)−3/2 ,   h'''(x) = (12)(32)(42)(1−4x)−5/2, and:

h(k)(x) = (12)(32)...(2k−32)(4k−1)(1−4x)−(2k−1)/2,
so  ak   =   h(k)(0) / k! =   (1⁄2)(3⁄2)...(2k−3⁄2) 4k−1 / k! =   (1)(3)(5)...(2k−3) 4k−1 / 2k−1 k! =   (1)(3)(5)...(2k−3) 2k−1(k−1)! / (k−1)! k! =   (1)(3)(5)...(2k−3) (2)(4)(6)...(2k−2) / (k−1)! k! =   (2k−2)! / (k−1)! k!   =   1⁄k (2k−2 | k−1) .
Hence Ck = ak+1 = 1k+1 (2k | k).

• 1/27: Rules to manipulate sequences and generating functions
• [W] Ch 2.2, pp 33-39.
• Notes 1/24−1/27.
• Make sure you can use Rules 1−5, and can compute derivatives.
HW:
1. Re-do HW 1/24 #3,4, explicitly using Wilf's Rules. Hints:
• For #3, modify Rule 2 to apply to Df(x) = f '(x), rather than x Df(x) = x f '(x).
• For #4, start with the recurrence Cn+1 = C0Cn + C1Cn−1 + ⋯   for n≥0.
2. Find the Taylor series of f(x)  =  log(1(1−x))  =  −log(1−x), starting from the fact that Df(x) = 1(1−x).
Hint: Do this by Taylor's Formula, then alternatively using Wilf's Rule #2.
3. [W] p 65, Ch 2 Ex #4.
Hint: A sequence like {1}4 means a0 = ⋯ = a3 = 0, and an = 1 for n≥4.
4. [W] p 65, Ch 2 Ex #6.
Hint: An example of f(n,k) is:
f(4,3)   =   sum of all products (i1)(i2)(i3), where i1,i2,i3 ≥ 1 with i1 + i2 + i3 = 4
=  (2)(1)(1) + (1)(2)(1) + (1)(1)(2)  =  6.
Fix k, and take the generating series fk(x) = ∑n≥0 f(n,k)xn. Apply Rule 4.
Solutions:

1. HW 1/24 #3. For f(x) = ∑n≥0 anxn, we have:
Df(x) = f '(x)  =  ∑n≥0 nanxn−1  =  0a0 + ∑n≥0 (n+1)an+1xn.
Hence the modified Rule 2:
{(n+1)an+1}n≥0  ↔opsDf(x).
(This also follows by combining Rule 2 with Rule 1, seeing as Df(x) = (x Df(x) − 0)x .) Now, if Df(x) = f(x), then (n+1)an+1 = an, which can be immediately solved to give an = cn!, where c = a0, i.e. f(x) = c exp(x).

HW 1/24 #4. We did this in class. Assuming {Cn}  ↔ops  f(x), we apply the ops correspondence to both sides of the recurrence equation: Cn+1 = C0Cn + C1Cn−1 + ⋯ + CnC0  for n≥0. We apply Rule 1 on the left side, Rule 3 or 4 on the right side, and we equate the two generating functions:

(f(x) − C0) x   =   f(x)2.
Rearranging, we get x f(x)2 − f(x) + 1 = 0, which gives the explicit formula for f(x) in the Solution to HW 1/24 #4. Step 2 is as before.

2. Assuming f(x) = −log(1−x) = ∑n≥0 anxn, we get the nth derivative as:
Dn f(x)  =  f (n)(x)  =  (n−1)!(1−x)−n.
Hence, by Taylor's formula, for n≥1:
an  =  f (n)(0)n!  =  (n−1)!n!  =  1n .
Also a0 = f(0) = 0. Thus:
f(x)   =   log(1(1−x))   =   x + x22 + x33 + x44 + ⋯ .
Alternatively, the basic formula f '(x) = 1(1−x) implies x Df(x) = x(1−x). Applying Rule 2 to the left side, and equating the coefficient sequences, we get nan = 1 for n ≥ 1 (also 0a0 = 0). That is, an = 1n , which agrees with the previous calcuation.

3. See [W] p 203, Ch 2 Solution #4.

4. See [W] p 203, Ch 2 Solution #6.

• 1/29: Exponential generating functions
1. More practice with Wilf's Rules 1−5 for  ↔ops . For each sequence, give a formula for the corresponding power series, in terms of x and/or f(x), assuming {an}n≥0  ↔ops  f(x) .
1. {3n}
2. {n2}
3. {n2an}
4. {n23n}
5. { ∑i=0ni23i }
6. { ∑i=0ni23n−i }
7. { ∑i+j+k=n i2 3j ak }n≥0
8. {1n}n≥1
9. {1(n+1)}n≥0
2. [W] p 24, Ex 2, 4.
3. In class, we considered the exponential generating function of the Fibonacci numbers:
F(x)   =   ∑n≥0 Fnn! xn.
We showed this function is a particular solution of the linear, homogeneous, constant-coefficient differential equation:
f ''(x)  −  f '(x)  −  f(x)   =   0.
We wish to prove that the only solutions f(x) ∈ R[[x]] are of the form f(x) = A exp(αx) + B exp(βx), where A,B are arbitrary constants, and r = α, β are the roots of the characteristic polynomial equation r2 − r − 1 = 0. Hence F(x) = A exp(αx) + B exp(βx) for appropriate A,B, which implies the explicit formula Fn = Aαn + Bβn.
1. Prove that f(x) = A exp(αx) + B exp(βx) does indeed satisfy the differential equation.
2. Prove that the entire sequence {an}n≥0 is determined by the two initial values a0 and a1 .
3. For a solution f(x), with any given initial conditions f(0) = a0 and f '(0) = a1 , find the appropriate function A exp(αx) + B exp(βx) which produces the same initial conditions, and show that f(x) = A exp(αx) + B exp(βx) . This is what we wanted to prove.
4. Even more practice with Wilf's Rules 1−5 for  ↔ops .
Generalize Rule 3 to the following Mulitplication Rule (given in class): For any list of power series f(x)  ↔ops  {an}, g(x)  ↔ops  {bn}, h(x)  ↔ops  {cn}, etc., their product has coefficients as follows:
f(x) g(x) h(x) ⋯  ↔ops  {i,j,k,... aibjck}n≥0,
where the sum is over all non-negative integers i,j,k,... which add up to n = i + j + k + ⋯ .
Show how each of the following Wilf Rules is a special case of the Multiplication Rule. That is, explain how to specialize the Multiplication Rule to get the given Wilf Rule.
1. Rule 3
2. Rule 4
3. Rule 5
Solutions:

1. Rules for ops

1. Substituted geometric series: 1(1−3x) .

2. Rule 2 applied to geometric series: (xD)2(1(1−x))   =   (x+x2)(1−x)3 .
Wolfram Alpha input:   x*(d/dx(x*(d/dx(1/(1-x))))) .

3. Rule 2 applied to f(x):    (xD)2f(x)  =  x(x f '(x))'  =  x f '(x) + x2 f ''(x).

4. Rule 2 applied to substituted geometric series from (a): (xD)2(1(1−3x))   =   (3x+9x2)(1−3x)3 .

5. Rule 5 applied to (d):   1(1−x)    (3x+9x2)(1−3x)3   =   (3x+9x2)(1−x)(1−3x)3 .

6. Rule 3 applied to (b) and (a):   (x+x2)(1−x)3    1(1−3x) .

7. Rule 3, generalized to 3 factors:   (x+x2)(1−x)3    1(1−3x)    f(x)

8. HW 1/27 #2:   log 1(1−x) . Note: In mathematical writing, log(x) always means the natural logarithm, with the base-10 logarithm written as log10(x).

9. Rule 1 applied to (h):   (log 1(1−x) − log 1(1−0) )    1x   =   1x log 1(1−x) .

2. See [W] p 197−198, Ch 1 Solutions #2, 4.

3. Fibonacci differential equation.
1. Expand the formula f(x) = A exp(αx) + B exp(βx) into a power series using the definition exp(x) = 1 + x + x22! + x33! + ⋯ . Differentiate term-by-term, as in the definition in the Notes, and find that:
f ''(x)  −  f '(x)  −  f(x)   =   (α2−α−1) A exp(αx) + (β2−β−1) B exp(βx)   =   0,
because α, β are solutions of the characteristic equation.
2. The equation f ''(x)  −  f '(x)  −  f(x)   =   0 is equivalent to the recurrence an+2  =  an+1 + an for n≥0, so that an is clearly determined by the initial values a0, a1.
3. Now suppose f(x)  =  ∑n≥0 anxn is an arbitrary solution of the differential equation, with some initial values a0, a1. Solving:
A + B = a0   and   Aα + Bβ = a1,
we get:
A = (a1−βa0)(α−β)   and   B = (αa1−a0)(α−β) .
Taking these values of A,B gives g(x) = A exp(αx) + B exp(βx) the same initial coefficients a0 and a1 as f(x). The differential equation guarantees the same coefficient recurrence for f(x) and g(x), so they have all the same coefficients; that is, they are the same power series: f(x) = g(x) as desired.

4. The general Multiplication Rule and Wilf's Rules
1. Apply the Multiplication Rule to only two series f(x) and g(x), getting the double summation of aibj over all i,j ≥ 0 with i+j = n, and evaluate this as a single summation of aibn−i over i = 0,...,n. This gives Rule 3.
2. Apply the Multiplication Rule to k factors, each of which is the same series f(x)  ↔ops  {an}. This gives Rule 4.
3. Apply the Multiplication Rule to the two factors f(x)  ↔ops  {an} and 1(1−x)  ↔ops  {1}, and evaluate the double summation of (ai)(1) over all i,j ≥ 0 with i+j = n as the single summation a0 + a1 + ⋯ + an. This gives Rule 5.

• 1/31: Exponential generating functions
• [W] Ch 2.3, pp 39−45. Learn Rules 1'−3'.
HW:
1. Again: [W] p 24, Ex 2, 4.
Hints: For [W] Ex 2(a)−(e), apply Rule 2' to {1}  ↔egf  ex. For [W] Ex 2(f), (g), and some parts of Ex 4, don't use a Rule: just write out the desired power series, and adapt a known exponential power series formula.
2. Bell numbers and exponential generating functions. Recall the Bell numbers, which are sums of Stirling partition numbers:
Bn   =   {n | 1} + {n | 2} + ⋯ + {n | n}.
For example, B3 = 5 counts all ways of putting 3 marked balls in any number of exchangeable baskets:
123     1|23     2|13     3|12     1|2|3 .
Also, we let B0 = 1.
1. Define a suitable Deletion Transform to prove the recurrence formula:
Bn   =   ∑ i=0 n−1   (n−1 | i) Bn−1−i     for n ≥ 1.
Actually, this is rather complicated, so don't spend too much time puzzling over it, unless you want a challenge. Just assume the recurrence, and go on to (b).
2. Rewrite the recurrence by shifting the left side to Bn+1. Perform the  ↔egf  correspondence to both sides of the recurrence. (Use Rule 1' for the left side, and Rule 3' for the right side.) Write the resulting equation involving the exponential generating function B~(x)  = ∑n≥0 Bn xnn!.
3. Solve the above equation to get a simple formula for the exponential generating function B~(x).
3. Extra Credit: The ring of linear differential operators.
• The formal power series form a ring, but we can consider them as a vector space: V = R[[x]]. Namely, we consider the constants c = c + 0x + 0x2 + ⋯ as the scalars, and arbitrary power series f(x) as the vectors. Of course, V is infinite-dimensional.
• Recall that L : V → V is a linear mapping (or linear transformation or linear operator) means L is a function taking vectors to vectors, satisfying, for all scalars c1, c2 and all vectors v1, v2:
L(c1v1 + c2v2)   =   c1L(v1) + c2L(v2) .
(This is a definition you learned in Math 309.) For a finite-dimensional V, the mapping L could be written as a square matrix, but for the infinite-dimensional V, this is not feasible.
• For any two linear mappings L1, L2 : V → V, we can add them to get a new operator L1 + L2 defined by:
(L1 + L2)(v)   =   L1(v) + L2(v).
(On the left is addition of mappings, on the right is addition of vectors.)
• We can also "multiply" them by composition to get a new operator L1L2 defined by:
(L1L2)(v)   =   L1(L2(v)) .
This addition and multiplication makes the set of all linear mappings L : V → V into a ring.
• Consider the derivative operation D : V → V defined by D(f(x)) = f '(x). Also, define the multiplication operation M defined by M(f(x)) = x f(x). You will show below that each of these is a linear mapping from V to V.
• Since D and M are linear mappings, so is any repeated sum or composition of these mappings. For example, L = DMD + 3D − 5, means:

L(f(x))   =   D(M(D(f(x)))) + 3 D(f(x)) − 5 f(x)
=   (x f '(x))' + 3 f '(x) − 5 f(x)
=   f ''(x) + x f '(x) + 3 f '(x) − 5 f(x) .

Wilf's operation xD is another notation for MD.
• Let S be the set of all repeated sums and compositions of D and M, as above. This is clearly a subring of the ring of all linear operators: it is called the Weyl algebra.
Problems:
1. Prove that D and M are linear mappings.
2. What are the additive and multiplicative identities 0,1 of the ring S? Define them as operators, not merely as symbols.
3. Prove that DM = MD + 1. In particular, the ring of operators is not commutatitive (which is not surprising, since the ring of matrix operators is also not commutative).
4. Find a basis for S, thought of as a vector space: that is, an infinite list of operators, such that every element of S can be written uniquely as a linear combination of the basis operators, with constant scalar coefficients.
Solutions:

1. See [W] p 197−198, Ch 1 Solutions #2, 4.

2. Exponential generating function for Bell numbers
1. Deletion transform giving recurrence formula
• We want to prove the identity:
Bn   =   ∑ i=0 n−1   (n−1 | i) Bn−1−i
by transforming the set partitions counted by the left side to some composite objects counted by the right side.
• An informal way to do this is stated in [W] p 25 Ch 1 Ex 7. (The statement is in the problem, without any futher solution.)
• Write a set partition as S1|⋯⋯|Sk : that is, the Sj's are disjoint exchangeable subsets with S1∪⋯∪Sk = [n].
• Define the transform of S1|⋯⋯|Sk by deleting the subset Sj which contains n, and recording S' = Sj\{n} as a separate piece of data at the beginning. Letting |S'| = i, the remaining subsets S1||Sj−1|Sj+1||Sk have n−1−i total elements, but they do not cover [n−1−i] = {1,2,...,n−1−i}; so we tamp them down by applying the unique order-preserving bijection [n] \ Si → [n−1−i]. Tamping down each subset Sm ⊂ [n] to the corresponding S'm ⊂ [n−1−i], we get the completed transformation:

S1|⋯⋯|Sk         ( S'  ,  S'1||S'j−1|S'j+1||S'k )
where n ∈ Sj ,   S' = Sj\{n} ⊂ [n−1],   |Sj| = i   and   S'1∪⋯∪S'k = [n−1−i] .

• The output of the transformation is of type (n−1 | i) Bn−1−i for any i = 1,,..., n−1, meaning this is the obvious formula which counts the possible output objects. If we can prove the transformation is reversible, this will prove the desired recurrence identity.
• Example: Take the set partition of type B7:

S1|S2|S3  =  16|347|25 .

We remove S2 = {3,4,7} containing n = 7, and we record S' = {3,4}. The remaining set partition is S1|S3  =  16|25, which covers [n] \ S2 = {1,2,5,6}. The tamping map {1,2,5,6} → {1,2,3,4} is 1↦1, 2↦2, 5↦3, 6↦4, and applying it to S1 and S3 gives the final set partition S'1|S'3 = 14|23 . The completed transformation is:

S1|S2|S3  =  16|347|25         (S' , S'1|S'3)  =  ({3,4} , 14|23)

• Reverse transform: In the general case, we start with any pair (S', S'1|⋯⋯|S'm), with S' ⊂ [n−1] and S'1∪⋯⋯∪S'm = [r]. First, we recover the original n, which must be n = r + |S'| + 1. Next, we define the spreading map, the unique order-preserving bijection [r] → [n−1] \ S'. Applying the spreading map to S'1,..., S'm recovers all the original sets S1,..., Sm, except for the set containing n, which is just Sm+1 = S' ∪ {n}.
(S', S'1|⋯S'2)  =  ({3,4} , 14|23).
We know S' = {3,4} was removed from [n−1] to leave r = 4 elements, so we must have had n = r + |S'| + 1 = 4 + 2 + 1 = 7. The spreading map thus takes:
{1,2,3,4}   →   [n−1] \ S' = {1,2,3,4,5,6} \ {3,4} = {1,2,5,6} ;
that is, 1↦1, 2↦2, 3↦5, 4↦6. Applying this to S'1 = {1,4} gives S1 = {1,6}, and similarly S2 = {2,5}. The set which was removed was S3 = S' ∪ {n} = {3,4,7}. Hence the original set partition was:
16|25|347 ,
which is indeed correct, except for the exchange of baskets, which is irrelevant.
• Checking that the two transformations reverse each other starting from either side, we have proved the recurrence formula.
• OK, this was a bit much to expect from you, especially the part about tamping and spreading. This is the kind of thing you would encounter in a graduate combinatorics course.

2. Now write the recurrence formula as:
Bn+1   =   ∑i=0 n   (n | i) Bn−i     for n ≥ 0.
Applying Rule 1' (exponential shift of index) to the left side and Rule 3' (exponential convolution formula) the right side, we get:
ddx B~(x)  =  ex B~(x) .

3. Writing y = B~(x), we have: dydx = ex y. This is a separable differential equation, and can easily be solved. We transpose to: 1y dy = ex dx, and integrate:

log(y)  =  ∫ 1y dy  =  ∫ ex dx  =  ex + c

for some constant c. Solving for y gives y  =  B~(x)  =  C exp(ex) for some C = ec > 0. The initial condition B~(0) = B0 = 1 forces C = e−1, so that B~(x) = e(ex − 1) = exp(ex − 1).

• 2/3: Cards, Decks and Hands (1)
1. Prove the following identity discussed in the context of the cooler example, for n = 2m:

(n | 2) (n−2 | 2) ⋯ (2 | 2)   =   (2m)!(2!)m .

This is the number of ways to partition the set [n] into m two-element subsets [n] = S1 ∪ ⋯ ∪ Sm , where the order of the Si's matters.
Extra Credit: Explain directly why the right-hand expression counts such partitions.
2. The "original" example of cards, decks, and hands. Define an exponential family whose pictures are the 4 suits of ordinary playing cards: P = {♠, ♣, ♥, ♦}, each with weight 1. A card C = (j,p) consists of a picture (a suit) p ∈ P and a number label (face value) j = 1,2,3,... . (Let us imagine cards for which these numbers go arbitrarily high.)
1. What sets of cards make a hand for this exponential family? Hint: Carefully read the definition of a hand. It is not just any set of cards: rather, a special kind of set. What kind?
2. How to determine the weight of a hand, according to the definitions?
3. Determine the deck-enumerator series d(x)   =   ∑i≥0 di xii! , where di is the number of pictures with weight i.
Note that according to our definitions, the deck is not the set of all possible cards: there is only one card for each picture (for each suit). What are those cards?
4. Apply the exponential formula to determine the hand-enumerator series h(x)   =   ∑n≥0 hn xnn! , where hn is the number of hands of weight n.
5. Adapt the Notes to prove the above formula for h(x).
6. Use the formula for h(x) to determine hn explicitly.
7. Explain the formula for hn in combinatorial terms
3. Extra Credit: In class, we used exponential generating functions to get the recurrence:
(n+1)!   =     =   ∑i=0n   (n | i) i! (n−i)! .
This is very easy to prove algebraically. However, I would like you to interpret this as a recurrence for the sequence an = n! obtained through a Deletion Transform. That is, given a permutation written as an ordering of [n+1], delete a certain element and produce some data naturally counted by the right-hand side: namely, a subset S ⊂ [n], a permutation of [i], and another permutation of [n−i]. Explain how to recover the original permutation from this data.
Hint: Use an order-preserving tamping and spreading maps.

Solutions:

1. (n | 2) (n−2 | 2) ⋯ (2 | 2)    =    n(n−1)2!  (n−2)(n−3)2!  ⋯  (2)(1)2!    =    n!(2!)m    =    (2m)!(2!)m .

2. Exponential family of playing cards.

1. The labels in a hand must be the numbers {1,2,...,n} = [n], where n is the weight of the hand. In this case, each card has weight 1, so a hand is any set of n cards with each label 1,2,...,n appearing exactly once. (You could call this a straight with low-card 1 and high-card n.) For example, a legal hand is:

{(2,♠), (3,♥), (5,♥), (1♦), (4,♦)}   =   {(1♦), (2,♠), (3,♥), (4,♦), (5,♥)}.

Two types of sets which are illegal, and do not count as hands in this family:

{(1,♦), (2,♠), (2,♥), (4,♦), (5,♥)}     or     {(1♦), (2,♠), (4,♥), (5,♦), (6,♥)}.

2. Each picture has weight 1, and hence so does every card. The weight of a hand is thus simply the number of cards.

3. There are 4 pictures with weight 1, and none with any other weight:  d1 = 4 and di = 0 for i ≠ 1. Hence d(x)  =  4x.
By definition, the deck of this family is not the set of all possible cards: rather, it has just one standard card for each picture: D = {(1,♠), (1,♣), (1,♥), (1,♦)}, i.e. only the ace as a sample of each suit.

4. The exponential formula says:  h(x) = exp d(x) = e4x.

5. We can prove (d) as in the Notes: In a hand of weight n, the set [n] must be partitioned into 4 sets (allowing empty sets); and the number of ways to do this is (as in Ex 1 above):

hn   =   i1,...,i4 (n | i1) (n−i1 | i2) (n−i1−i2 | i3) (n−i1−i2−i3 | i4)

=   i1,...,i4 n!(i1! i2! i3! i4!) ,

where the summation runs over integers i1,...,i4 ≥ 0 with i1 + i2 + i3 + i4 = n. It is easily seen by generalizing [W] Rule 3' (exponential convolution), that this has generating function:

h(x)   =   (i≥0 xii!)4   =   e4x .

6. Since e4x  =  ∑n≥0 4n xnn!, we have an = 4n.

7. Retrospection: Choosing a hand of weight n is equivalent to choosing a suit for each of the labels 1,2,...,n. Each choice is independent with 4 possiblilities, so we use the ordinary Product Principle to get hn = (4)⋯(4) = 4n. This is obvious in hindsight, but we might not notice it if we lay out the cards suit by suit rather than in face value order.

• 2/5: Examples of Exponential Families
1. Exponential family of graphs.
1. Write down all the connected graphs with n = 1,...,4 vertices, which is the most simple-minded way to find c1, ... ,c4. (For c4, group them into types, and just say how many of each type without drawing them all.)
2. Compare the above numbers to g1,..., g4. What percentage of all graphs are connected in each case?
Extra Credit: Look for trends in cngn for larger n (using the online list cn at the OEIS). Can you explain these trends in some way?
3. Work out the exponential formula c(x) = log g(x) up to the x4 term. Do this by hand, and check your work on Wolfram Alpha.
Hints: Recall that g0 = 1, so you can write g(x) = 1 + z and use the power series for log(1+z). In your computation, ignore all terms of degree x5 and higher, which will not affect the coefficients c1,...,c4.
2. Consider the exponential family of set partitions, having the deck-enumerator d(x) = ex − 1, and hand-enumerator:

B(x)  =  ed(x)  =  1 + d(x) + 12! d(x)2 + 13! d(x)3 + ⋯ ..

1. Consider the function f(x)  =  12! d(x)2, which is one of the terms of B(x). Expand this into a Taylor series f(x)  =  ∑n≥0 an xnn!, and give a simple formula for the coefficient an.
2. Using [W] Rule 3', give a more complicated convolution formula for the above coefficients an. Examine this to show that an counts partitions of [n] into exactly 2 non-empty subsets. What is our usual notation for this number?
3. Extra Credit: Find the coefficients of 1n! d(x)n. Interpret the coefficient of xnn! as counting a certain special kind of set partitions of [n]. Justify your interpretation.
Solutions:

1. Exponential family of graphs
1. We have c1 = 1,  c2 = 1,  c3 = 4,  c4 = 38. See the entry in the Online Encyclopedia of Integer Sequences.
• For n = 2, there is c2 = 1 connected graph , and 1 disconnected graph  .
• For n = 3, there are c3 = 4 connected graphs: the three paths , , ; and also the complete graph with all 3 possible edges. Note that there are only 3!2 = 3 paths, because reflecting a path horizontally (or performing any symmetry on a graph) does not make a different graph.
• For n = 4, there are c4 = 38 connected graphs: 42 = 16 trees by Cayley's Theorem; plus 4!8 = 3 four-cycle graphs (since a four-cycle has 2(4) = 8 symmetries); plus 4!2 = 12 graphs consisting of a three-cycle with an extra edge (which has 2 symmetries); and 4!4 = 6 graphs with five edges (a square with a diagonal, which has 4 symmetries); plus 1 complete graph with all possible edges.

2. Proportion of connected graphs to all graphs: cngn > n 1 2 3 4 5 cn / gn 1 1⁄2 1⁄2 19⁄32 91⁄128 1 0.5 0.5 0.59 0.71

3. Letting z  =  x + 2(2 | 2) x22! + 2(3 | 2) x33! + 2(4 | 2) x44! + ⋯ , we get:

c(x)  =  log(1 + z)  =  z − z22 + z33z44 + ⋯
=  x + 12 x2 + 23 x3 + 1912 x4 + ⋯ .
=  1 x + 1 x22! + 4 x33! + 38 x44! + ⋯ .

The Wolfram Alpha input was:

expand z - z^2 / 2 + z^3 / 3 - z^4 / 4
where z = x + 2 x^2 / 2! + 2^3 x^3 / 3! + 2^6 x^4 / 4!
.

2. Exponential family of set partitions
1. f(x)  =  12! d(x)2  =  12!(ex − 1)2  =  12!(e2x − 2ex + 1). Thus, the coefficient of xnn! is an = 2n−1 − 1.

2. an  =  12! i=1n−1(n | i)(1)(1). This is the number of partitions of [n] into just two non-empty subsets. We can see such a partition as choosing the first subset of i elements, then putting the rest into the second subset; we also divide by 2! since the sets are exchangeable.

• 2/7: Quiz 13 Solutions

• 2/7: Proof and analysis of the Exponential Formula
• Notes 2/7.
• [W] Ch 3.4-3.6, pp 78−83. Wilf's approach to the Labeled Product Principle is somewhat different from my Notes, bypassing the discussion of ordered hands. He uses a two-variable generating function H(x,y), where the coefficient of  xnykn!  is  h(n,k) = h(k)n , the number of unordered k-card hands of weight n.
HW:
1. Recall from Notes 2/5 that the Bell numbers Bn count partitions of [n] into any number of subsets, which is equivalent to hands of weight n in the exponential family of set partitions, whose pictures are sets of unlabeled balls. Their generating function is B(x) = exp(ex − 1).
We can refine this to consider only partitions of [n] into k non-empty subsets, which are counted by the Stirling partition numbers {n | k}, so that Bn = {n | 1} + {n | 2} + ⋯ + {n | n}. In terms of the exponential family, k-subset partitions of [n] correspond to k-card hands of weight n, as in Notes 2/7 #3, so that {n | k} = h(k)n .
Problems:
1. Use the analysis in the Notes to find a simple formula for the exponential generating function of the Stirling partition numbers {n | k} for fixed k:
fk(x)   =   ∑n≥0 {n | k} xnn!   =   {1 | k} x1! + {2 | k} x22! + {3 | k} x33! + ⋯ .
2. Use your formula for the generating function to find a formula for {n | k}. Where have you seen this before?
3. Expand the formula B(x) = exp(ex − 1) into a Taylor series by algebraic methods, to obtain a completely new and surprising formula for Bn, different from Bn = {n | 1} + {n | 2} + ⋯ + {n | n}.
2. We saw after Quiz 13 (2/7) that a hand in the exponential family of directed cycles corresponds to the cycle decomposition of a permutation (see also Wilf p. 77). Applying today's Notes to this family, find the exponential generating function of the Stirling cycle numbers [n | k], which count the permutations of [n] having k cycles.
We have seen these before in Notes 1/13, HW 1/13 #1, and see also [HHM] p. 227−230.
3. Extra Credit: Let an be the number of permutations of [n] having only cycles of odd length (no 2-cycles, 4-cycles, etc.). For example, a4 = 9 counts the permutations (in cycle notation):
(1)(2)(3)(4),  (1)(234),  (1)(243),  (2)(134), (2)(143),  (3)(124),  (3)(142),  (4)(123),  (4)(132).
Use the Notes to find the exponential generating function of {an}.
Hint: To extract only the odd terms of the Taylor series of a function f(x), take ½ (f(x) − f(−x)).
Solutions:

1. Formulas for set partitions
1. We know k-subset partitions of [n] correspond to unordered k-card hands of weight n in the exponential family of set partitions, which has deck-enumerator d(x) = ex − 1. Notes 2/7 #3 deals with such hands: Proposition 3 says the generating function is the kth term of h(x) = exp d(x), namely:
fk(x)   =   ∑n≥0 {n | k} xnn!   =   h(k)(x)   =   1k! d(x)k   =   1k! (ex − 1)k

2. Expanding this by the Binomial Theorem gives:
fk(x)   =   1k!j=0k (k | j) ejx (−1)k−j.
Taking the the Taylor series of ejx gives (a flipped form of) the familiar formula from the Twelvefold Way:

{n | k}   =   1k!j=0k (−1)k−j (k | j) jn.

Recall that we also got this formula from a recurrence for the ordinary generating function, in HW 1/22 #1.
3. Given the generating function formula B(x) = exp(ex − 1), the basic method of Step 2 is to get B(x) as a sum of functions with known power series: in this case, in terms of erx. First, we can get rid of the −1 in the exponent: B(x) = 1e exp ex. Next, we expand the exp(z) into a power series, with z = ex and zj = ejx:

B(x)   =   1ej≥0 ejxj!   =   1ej≥0n≥0 (jx)nj!n! .

Collecting the coefficients of xnn!, we get Dobinski's Formula:

Bn   =   1ej≥1 jnj! .

This gives Bn as an infinte series, divided by e !! For example:

B3   =   1e (1 + 232! + 333! + 434! + 535! + ⋯)   =

Checking this on Wolfram Alpha up to the 5th term gives 4.86, and taking up to the 9th term gives 4.99998, confirming the convergence to the correct value B3 = 5.

I don't think we would have thought of this by combinatorial reasoning, do you?

Extra Credit: For general n, how many terms of this series do we need, so that rounding to the nearest integer gives Bn? Are n terms enough, or n/2, or √n? If we knew this, it would give a finite formula for Bn, perhaps even an efficient formula.

For more on Bell numbers, see Wikipedia.

2. A permutation of [n] with exactly k cycles corresponds to an unordered k-card hand of weight n in the family of directed cycles, which has deck-enumerator d(x)  =  log(11−x) . Thus, the Stirling cycle numbers are [n | k] = h(k)n , and again using Notes 2/7 Proposition 3, the generating function for fixed k is:

h(k)(x)   =   ∑n≥0 {n | k} xnn!   =   1k! d(x)k   =   1k! logk(11−x) .

This does not lead to any simple formula for [n | k], but we will see that it can be developed into an aysmptotic approximation.

• 2/10: Exponential Families Wrap-up
1. Recall that the ordered Bell numbers Rn count lists of sets. That is, Rn is the number of ways to partition the set [n] into any number of subsets (S1,..., Sk), where the order of the subsets matters. For example, R3 = 13 counts the partitions:
123       1|23       23|1       2|13       13|2       3|12       12|3
1|2|3       1|3|2       2|1|3       2|3|1       3|1|2       3|2|1
(Compare this to the unordered Bell numbers Bn from last time, which enumerate unordered hands of the family of set partitions.)
1. How many possible outcomes of a race with n horses, allowing ties? For example, for n = 6 horses, we could have 3,6 tied for first place, 4 in second place, and 1,2,5 tied for third place. For general n, give your answer in terms of Rn.
2. Consider the surjection numbers surj(n,k) from the Twelvefold Way: the number of surjective functions f : [n] → [k]. (We have reversed the previous roles of n and k.) Explain why we have:
Rn = surj(n,1) + surj(n,2) + ⋯ + surj(n,n).
Hint: A surjection can be transformed into a list of k subsets of [n].
3. If we consider lists of sets as a family, what is the deck? That is, what are the basic objects which are labeled and combined into a list? Find the deck enumerator function d(x).
4. Find the enumerator function for the surjection numbers surj(n,k) with k fixed. These are the k-card ordered hands of the family: surj(n,k) = ℓ(k)n. So find a simple formula for:
n≥0 surj(n,k) xnn! .   =   ∑n≥0(k)n xnn!   =   ℓ(k)(x) .
Hint: Use Notes 2/7 #2.
5. Find the enumerator function R(x)   =   ∑n≥0 Rn xnn! . Hint: Sum the enumerator functions ℓ(k)(x) for k ≥ 0.
6. Starting with the formula in (e), expand R(x) into a Taylor series, and get an infinite sum formula for Rn similar to Dobinski's Formula for Bn in HW 2/7 #1(c). Hint: Expand into a double summation over k ≥ 0 and n ≥ 0. Put ∑n≥0 on the outside, and factor out xnn! .
2. Sets and lists of singles and pairs. Use exponential families to solve Problems (a)−(d) below.
• Find the appropriate version of decks and hands for the problem.
• Find a simple formula for the exponential generating function using Notes 2/7.
• Expand the generating function into a Taylor series, by algebraic methods if possible, otherwise by brute force (Wolfram Alpha, or try this site).
Problems:
1. Among 10 people working on a project, some work alone, some join up into pairs, in any combination. Example: singles are 2,5,7,10; pairs are 1&9, 3&4, 6&8. How many possible combinations?
2. Same as (a), but now the teams are given rankings for their projects. Example: 1st place team is 3&4; 2nd is 7; 3rd is 10; 4th is 1&9; 5th is 6&8; 6th is 2; 7th is 5. How many possible rankings (including all possible team combinations)?
3. Same as (a), but in each pair, one person is designated the leader. For example, team 1&9 has leader 1; team 9&1 has leader 9.
4. Teams have leaders as in (c), and are ranked as in (b).
Solutions:

1. Ordered Bell numbers
1. Ways to partition the set of n horses into a first subset, a second subset, etc: this just restates the definition of Rn.

2. We can write each function f : [n] → [k] in list notation (f(1),..., f(n)); or in balls-and-bins notation, meaning we record (S1,..., Sk), where Si = {j ∈ [n] with f(j) = i}. (See HW 1/10 #1.) Thus, a surjection f : [n] → [k] is equivalent to a partition of [n] by a list of k subsets: (S1,..., Sk). Thus Rn , the number of partitions of [n] into a list of any number of subsets, equals the sum of the surjection numbers for all k, as desired.

3. The deck is the same as for the family of set partitions: D = { •, ••, •••, .... }, so dn = 1 for n ≥ 1, and d(x) = ex − 1.

4. (k)(x)   =   d(x)k   =  (ex − 1)k

5. Partitons of [n] by lists of k subsets are split into the cases with k = 0,1,2,.... Thus:

R(x)  =  ℓ(x)  =  ∑k≥0(k)(x)  =  ∑k≥0 d(x)k
=  1(1 − d(x))  =  1(1 − (ex−1))  =  1(2 − ex) .

6. We expand the above generating function:

R(x)   =   12   1(1 − ½ex)   =   12k≥0 (½ex)k
=   12k≥0 (12k) ekx   =   12k≥0 (12k)n≥0 knxnn!   =   ∑n≥0 (k≥0 kn2k+1) xnn!

That is: Rn  =  ∑k≥0 kn2k+1  =  1n22 + 2n23 + 3n24 + 4n25 + ⋯ .

2. Sets and lists of singles and pairs.

1. Step 0: First, we generalize the problem to an = number of single/pair team combinations from n people, so that the original problem is a10. This is a set-of-sets model.

Step 1: We want to find the exponential generating function f(x)  =  ∑n≥0 an xnn! . We start with the deck D = {•, ••}, so d(x)  =  x + x22! . A combination of teams corresponds to an unordered hand with any number of cards from D, so by Notes 2/7 #4, the team enumerator is:

f(x)  =  h(x)  =  exp d(x)  =  exp(x + x22!).

This is the same as the family of labeled coolers from Notes 2/3.

Step 2: We could try expanding this using the Taylor series of exp(z), and the binomial theorem for zk = (x + x22!)k, but this does not seem worth it. Wolfram Alpha gives the x10 term of the Taylor series as: (1187453600) x10, so:

a10  =  10! (1187453600)  =  9496.

2. Step 0: This time we let an = number of single/pair team lists from n people. This is a list-of-sets model.

Step 1: To find the exponential generating function f(x)  =  ∑n≥0 an xnn! , we start with the same deck D = {•, ••} with d(x)  =  x + x22! . A list of teams corresponds to an ordered hand with any number of cards from D, so by Notes 2/7 #2, summed over all k into a geometric series, the team list enumerator is:

f(x)  =  ℓ(x)  =  ∑k≥0 d(x)k  =  1(1 − d(x))  =  1(1 − x − ½x2) .

This is similar (but not identical) to the ordinary generating function of the Fibonacci numbers from Notes 1/17.

Step 2: Again, putting the above function into Wolfram Alpha immediately gives:

a10  =  10! (57132)  =  64751400.

This is much bigger than in part (a), because it distinguishes all permutations of a given set of teams.

We could also expand algebraically using a partial fraction expansion of f(x). Letting x = α = −1−√3 and x = β = −1+√3 be the vertical asymptotes, so that 1 − x − ½x2  =  (1 − xα)(1 − xβ), we expand as:

f(x)  =  1(1 − x − ½x2)  =  A(1 − xα)  +  B(1 − xβ)

1α  =  1−√32       1β  =  1+√32       A = 3−√36     B = 3+√36

ann!  =  Aαn  +  Bβn  ≈  Bβn  =  (3+√36) (1+√32)n .

3. Step 0: This time an = number of single/pair team combinations from n people, with a leader in each pair. Thus, each pair is ordered, and this is a set-of-lists model.

Step 1: We want to find the exponential generating function f(x)  =  ∑n≥0 an xnn! . This time the deck must take the order of each pair into account:

D   =   { , , }   or   {() , (,) , (,)},

and d(x)  =  x + 2 x22!  =  x + x2. A combination of teams-with-leader corresponds to an unordered hand with any number of cards from D, so by Notes 2/7 #4, the team enumerator is:

f(x)  =  h(x)  =  exp d(x)  =  exp(x + x2).

Step 2:   a10  =  10! (19093518400)  =  133651.

4. Step 0: Finally, an = number of single/pair team lists from n people, with a leader in each pair. This is a list-of-lists model.

Step 1: The deck is the same as in part (c), so and d(x)  =  x + x2. A list of teams-with-leader corresponds to an ordered hand with any number of cards from D, so as in part (b), the team enumerator is:

f(x)  =  ℓ(x)  =  1(1 − x − x2)

This is exactly the same as the ordinary generating function of the Fibonacci numbers (Notes 1/17), except shifted over by a factor of x.

Step 2: Since the exponential generating function of our sequence {an} is the same as the ordinary generating function of the Fibonacci numbers {Fn+1}, we get:  ann!  =  Fn+1,  i.e. an = n! Fn+1.
Extra Credit: Explain this formula combinatorially. It seems to be saying that one of our team lists can be transformed into a permutation along with a combinatorial model for the Fibonacci numbers. (We gave some models for the Fibonacci numbers in class, or check Wikipedia.)

• 2/12: Recurrences and asymptotics from generating functions
• [W] Ch 1.6 pp 22−23: The x Dlog operation
• [W] Ch 5.2 pp 171−177: Asymptotics of poles
HW:
1. Derangements. Recall the derangement number Dn, which counts permutations of [n] without fixed points: that is, bijections σ : [n] → [n] with σ(i) ≠ i for every i. For example, D3 = 2 counts the permutations σ = (123), (132) (written in cycle notation); all other permutations (1)(2)(3), (12)(3), (13)(2), (1)(23) have a fixed point, which corresponds to a 1-cycle. In fact, the derangements are precisely the permutations with no 1-cycles. In class on 2/7, we used this to find the exponential generating function D(x)   =   ∑n≥0 Dn xnn! . (Do not confuse this with a deck-enumerator function d(x).)
1. From Quiz 13 on 2/7, recall the exponential family of directed cycles with deck-enumerator dn = (n−1)! and d(x) = log 1(1−x) . The unordered hands of this family model the cycle notation for permutations. Remove the 1-cycles from the family to model the derangements, and use the exponential formula to find the derangement generating function D(x).
2. Given D(x)   =   e−x(1−x) , clear denominators to find a recurrence for Dn. (The result is rather mysterious: Extra Credit for a combinatorial explanation.)
3. Find the poles (vertical asymptotes) of D(x) for x in the complex plane. Find the principal part A(1−x/α), and give an asymptotic formula Dnn!A αn.
4. Finally, apply Stirling's approximation for n! to give an asymptotic for Dn. How many digits should there be in D100?
2. Recurrences from x D log. Given a generating function {an}  ↔egf  f(x) where f(x) has no denominator, we need a different approach to finding a recurrence for an. We use the "x Dlog method" ([W] p 22). It says that if
f(x)   =   exp d(x),
then you perform the composite operation x D log f(x) on the left side, and the corresponding operation on the right side. (That is, on each side you take log, then the derivative D = ddx, then multiply by x.) The result is the formula:

x f '(x)f(x)   =   x d'(x) .

1. Explain why the left side is: x D log f(x) = x f '(x)f(x) . Explain why the right side is x D log ed(x) = x d'(x).
2. Clear denominators in the above formula, and convert it into an equation involving Taylor coefficients, using Wilf's  ↔egf  rules (p. 40−42).
3. Apply the x Dlog operation to give a recurrence for the coefficients of ex+x2, which appeared in HW 2/10 #2(c).
4. Apply the x Dlog operation to give a recurrence for the Bell numbers, which have generating function B(x)  =  exp(ex − 1).
5. Try the x Dlog operation on the generating function from #1 above, D(x)   =   e−x(1−x). (Here the right-hand side is not exp of something, but you can still compute x Dlog of it by calculus.) Does this give a better or worse recurrence than clearing denominators?
3. Asymptotics of ordered Bell numbers. Recall the numbers Rn from HW 2/10 #1, with exponential generating function R(x) = 1(2 − ex) . We wish to find a simple asymptotic formula for the coefficients Rn .
1. To find all vertical asymptotes of R(x) in the complex plane, find all the roots of the denominator (including complex ones). Use the fact that exp(x+iy) = ex(cos y + i sin y), so that exp(x+iy) is a posiitve real number only for y = 2πk for k an integer.
2. Find the dominant principal part f(x)  =  A(1 − x/α) + ⋯ , which contributes most to the coefficients. Here x = α is the vertical asymptote closest to the origin (usually on the positive real line). Find the numerator using  A  =  limx→α R(x) (1 − x/α).
3. Since the prinicpal part has a pole (vertical asymptote) closer to the origin than the remainder terms (whatever they may be), the coefficients of R(x) are asymptotic to the coefficients of A(1 − x/α) . Find the asymptotic formula for Rn
Solutions:

1. Derangement numbers
1. Define an exponential family whose pictures are directed cycles of length at least 2 (no 1-cycles). Thus, the deck-enumerator is:

d(x)   =   ∑n≥2 (n−1)! xnn!   =   log 1(1−x)   −   x .

Derangement permutations are unordered hands of these cycles, so the Exponential Formula gives:

D(x)   =   exp d(x)   =   exp(log 1(1−x)) exp(−x)   =   e−x(1−x) .

2. The left side of the equation   (1−x) D(x)  =  e−x  expands into Taylor series as:

(1 − x) ∑n≥0 Dn xnn!   =   ∑n≥0 Dn xnn!  −  ∑n≥0 Dn xn+1n!

=   ∑n≥0 Dn xnn!  −  ∑n≥0 (n+1)Dn xn+1(n+1)!

=   ∑n≥0 Dn xnn!  −  ∑n≥1 n Dn−1 xnn!

Equating coefficients on both sides of the original equation gives:  Dn − nDn−1  =  (−1)n,  and hence  Dn = nDn−1 + (−1)n for n ≥ 1.

3. Since e−x has no poles (vertical asymptotes) for x in the complex plane (it is an entire function), our D(x) has x = 1 as its only pole. The coefficient of its principal part is:

A  =  limx→1 (e−x(1−x)) (1−x)  =  e−1.

Thus D(x)  =  e−1(1−x) + ε(x), where the error term ε(x) has asymptotically negligeable coefficients. Expanding the principal part gives: Dnn!  ≈  e−1(1), or Dn  ≈  n!e−1. This agrees with the exact formula from 2/7:

Dn   =   n!(1 − 11! + 12! ⋯ ± 1n!).

4. Applying Stirling's approximation n!  ≈  √2πn (ne)n, we get:

Dn  ≈  e−12πn (ne)n.

To find the number of base-10 digits of D100, we take log10 of the right-hand side above for n = 100:

log10(e−12π(100) (100e)100)   =   −log10(e) + ½ log10(2π) + 1 + 100(2 − log10(e))   ≈   157.5

Thus, D100 has about 157 digits, and indeed Wolfram Alpha gives derangements 100 as: 3.433 × 10157.

2. The x Dlog method for recurrences
1. We apply the composite operation x D log to both sides of the Exponential Formula  f(x)  =  exp d(x). On the left side, we use log'(z) = 1z and the Chain Rule to get

ddx log f(x)   =   1f(x) f '(x),

so x D log f(x) = x f '(x)f(x). The right side is clearly  x D log ed(x) = x D d(x) = x d'(x).

2. We take coefficients on both sides of x f '(x)  =  x d'(x) f(x). According to Wilf's Rule 2', the left side is x Df(x)  ↔egf  n an. On the right side, x d'(x)  ↔egf  n dn , and the product (x d'(x)) f(x) is an exponential convolution by Rule 3'. Equating the two sides:

n an   =   ∑ i=0n (n | i) i di an−i .

Remembering that d0 = 0, we finally get, for n ≥ 1:

an   =   1n ((n | 1)d1an−1  +  2(n | 2)d2an−2  +  3(n | 3)d3an−3  +  ⋯  +  n(n | n)dna0) .

Rewriting in (n | i)  =  (n−1 | i−1), this becomes:

an   =   d1an−1  +  (n−1 | 1)d2an−2  +  (n−1 | 2)d3an−3  +  ⋯  +  (n−1 | n−1)dna0 .

This can simplify further if some of the di = 0.

3. Letting f(x) = ex+x2 = ed(x) with d(x) = x + 2 (x22!), the functional equation

x f '(x)   =   x (x + 2 x22)' f(x)

implies the coefficient recurrence equation:

n an   =   (n | 1)d1an−1  +  2(n | 2)d2an−2 ,

which works out to:

an   =   an−1  +  2(n−1) an−2 .

This is not too hard to explain in terms of a Deletion Transform on the teams-with-leader arrangements from HW 2/10 #2(c), which is where this sequence came from.

4. For the Bell number enumerator B(x) = exp(ex − 1) = ed(x) with dn = 1 for n ≥ 1, d0 = 0, carrying through the method gives:

Bn   =   Bn−1  +  (n−1 | 1)Bn−2  +  (n−1 | 2)Bn−3  +  ⋯  +  (n−1 | n−1)B0 .

This is the recurrence we proved by a combinatorial Deletion Transform in HW 1/31 #2a.

5. The derangement enumerator D(x)   =   e−x(1−x) does not fit the above pattern, so we need to it work out by specially, performing the x D log operation to both sides:

log D(x)   =   − x + log 1(1−x) ,

Taking x D of both sides gives:

x D'(x)D(x)   =   − x  +  x(1−x)   =   x2(1−x) ,

x D'(x)   =   x2(1−x) D(x) .

Now, x2(1−x)   =   ∑n≥2 n! xnn! , so the right side of the above equation gives an exponential convolution (Rule 3'):

n Dn   =   ∑ i=2n   (n | i) i! Dn−i

Simplifying:

Dn   =   (n−1) Dn−2  +  (n−1)2 Dn−3  +  (n−1)3 Dn−4  +  ⋯  +  (n−1)n−2 D1  +  (n−1)! D0 .

This is pretty weird and inexplicable, and not nearly as efficient a recurrence as in Prob 1(b) above. It's actually rather hard to believe, but we can confirm that: D0 = 1,  D1 = 0,  D2 = 1,  D3 = 2,  D4 = 9,  D5 = 44, and:
44 = (5−1) 2 + (5−1)(5−2) 1 + (5−1)(5−2)(5−3) 0 + (5−1)! 1 .

3. Asymptotics of Rn
1. We have exp(x+iy)  =  ex(cos y + i sin y) = 2 exactly when the radius is ex = 2 and the circular part is cos y + i sin y = 1: that is, x = log(2) and y = 0, ±2π, ±4π,.... Clearly, the smallest of these roots log(2) + iy is when y = 0, that is, α = log(2).

2. Given α = log(2), we use L'Hôpital's Rule to find:

A  =  limx→α R(x) (1 − x/α)  =  limx→α (1 − x/α)(2 − ex)

=  limx→α (− 1/α)(− ex)  =  1αeα  =  12log(2) .

3. Since:

n≥0 Rnn! xn   =   R(x)   ≈   A(1 − x/α)   =   ∑n≥0 Aαn xn ,

we have:   Rnn!   ≈   Aαn   =   12logn+1(2) ,   i.e.   Rn   ≈   n!2logn+1(2) . We could further simplify this with Stirling's Approximation, as in Prob 1(d).

• 2/14: Asymptotics and complex analysis
• [W] Ch 5.2 pp 171−177: Asymptotics of pole singularities (from last time)
• (optional) [W] Ch 2.4 pp 46−49: Taylor series of a complex variable
• (optional) [W] Ch 5.3 pp 181−183: Stirling's Approximation
• (optional) Notes on Stilrling's Approximation from my graduate course.
HW:
1. Recall the Catalan numbers Cn from the Twelvefold Way handout and HW 1/24 #4.
1. Use the exact formula for Cn and Stirling's Approximation to get an asymptotic formula for Cn .
2. How many digits in C100?
3. Check the accuracy of your formula against the exact formula for n = 5, 10, 20. What is the percentage error?
2. Valentine's Day game.
• A group of n people (numbered 1,..., n) play a game. Each person picks a name at random from a basket, and gives that person a gift. If a person picks his own name, he can choose to buy a gift for himself, or no gift.
• Example: n = 9 people:   1 gives to 5 gives to 2 gives to 9 gives to 1;   3 gives to 7 gives to 4 gives to 3;   8 buys himself a gift; and 6 chooses no gift (after shedding a tear).
• Let an be the number of possible gift-arrangements of the Valentine game with n people.
Problems:
1. Should you use an ordinary or exponential generating function for this problem? How can you tell?
2. Step 1: Find a simple formula for the generating function using the appropriate version of the Product Principle.
Hint: A gift-arrangement defines a permutation of [n], since each person is mapped injectively to another person. Consider these permutations in cycle-notation, and take account of the extra choice for each 1-cycle. The Exponential Formula and its variants are the labeled version of the Product Principle.
3. Step 2: Find an explicit formula for an , if this is reasonably possible.
4. Step 2: Find a recurrence (as simple as possible) for computing an.
5. Step 2: Find an asymptotic formula for an.
6. Which is the most satisfactory result of Step 2? Which has the most right to be called "the answer" to the problem?
3. Same as #2, except that if two people choose each other, they can choose to exchange gifts, or to keep the gifts themselves.
Example: n = 9 people: 1 gives to 5 gives to 2 gives to 1;  3 gives to 7 gives to 4 gives to 3; 8 and 9 choose not to exchange gifts; and 6 chooses no gift.
Solutions:

1. Catalan number approximation
1. Cn   =   1(n+1) (2n | n)   =   1(n+1) (2n)!(n!)2   ∼   1n2π2n (2n/e)2n(√2πn)2 (n/e)2n   =   4nn3/2π .
Here we used the asymptotic approximation: 1(n+1)1n and Stirling's Approximation  n!   ∼   √2πn (n/e)n.

2. The number of base-10 digits for n = 100 is:
log10(41001003/2√π)   =   100 log10(4)  −  32 log10 100  −  12 log10 π   ≈   56.96 .
Thus, C100 is a high 56-digit number, in fact C100 ≈ 1056.96 = 9.06618 × 1056.

3. Wolfram Alpha input: Catalannumber(n) for n = 5,10,20  or  binomial(2n,n)/(n+1) for n = 5,10,20 . Output:  n 5 10 20 Cn 42 16796 6564120420 4n⁄n3/2√π 52 18708 6.93 × 109 ratio 1.23 1.11 1.06

Clearly, the percentage error is shrinking toward zero, though the absolute error keeps growing.

2. Valentine game with choice for 1-cycles
1. Since the objects being counted (the gift-arrangements) depend on some arrangement of the labels {1,...,n}, it is the exponential generating function (comparing each an to the permutations n!) which has a better chance to turn out tractable. Thus, we take f(x)   =   ∑n≥0 an xnn! .

2. Step 1. Considering the gift-arrangements in cycle-notation as in the example, they are made up of directed cycles with the labels {1,...,n} distributed among them, as in Quiz 13. The only difference is that there are 2 types of 1-cycles: self-gift and no-gift. Thus, for n ≥ 2, the deck D consists of dn = (n−1)! directed-cycle cards. For n = 1, we have d1 = 2 cards, each with 1 happy or 1 sad person. (As always, d0 = 0.) The deck enumerator is thus:

d(x)   =   2x  +  ∑n≥2 (n−1)! xnn!   =   x + log 1(1−x) .

A gift-arrangement among n people is an unordered hand of weight n in this family (with any number of cards): an = hn. We use the Exponential Formula (Notes 2/7 Proposition 4) to get:

f(x)   =   h(x)   =   ed(x)   =   exp(x + log 1(1−x))   =   ex(1−x) .

This is very similar to the generating function of derangements in HW 2/12 #1, and we can analyze it in just the same way.

3. Step 2: Explicit formula: Wilf's Rule 5 (p 37) applies to formulas like our f(x); but it is a rule for ordinary generating functions, giving the coefficient of xn, which in our case is ann! : Thus, it will find:

ann!  =  1 + 11! + 12! + ⋯ + 1n! ,

so an = n! (1 + 11! + 12! + ⋯ + 1n!).

4. Step 2: Recurrence. Clearing denominators, we get almost the same computation as for derangements (1b), giving:  an  =  n an−1 + 1  for n ≥ 1.

5. Step 2: Asymptotic formula. Again as for derangements (1c), we get an ∼ n! e, which is already clear from the exact explicit formula.

6. You use the different answers for different purposes. The recursive formula computes an efficiently, minimizing the number of operations (which you want for hand and for machine computations). You need the exact explict formula to analyze the detailed properties of an, such as whether it is odd or even. The asymptotic approximation formula gives an estimate of its magnitude.

3. Valentine game with choice for 1- and 2-cycles
1. In principle, this is just like #2, but the details are more intricate, and give you a good technical workout.

2. Now there are two types of 1-cycles and of 2-cycles, so:  d(x)  =  x + x22 + log 1(1−x) , and f(x)  =  exp(x + x2/2)(1−x) .

3. Step 2: Exact formula. The formula  f(x)  =  exex2/2(1−x)  could be expanded with Wilf's Rules, but the result seems too complcated to be of any use: it would be at least a double summation.

4. To get a reasonable recurrence, we want an equation like:  u(x) f(x)  =  v(x) with u(x) and v(x) having simple Taylor series. To make up u(x) and v(x), we have three factors to juggle with:  ex, ex2/2, (1−x). The best equation seems to be:
(1−x) e−x f(x)   =   ex2/2.
Then:
(1−x) e−x   =   ∑n≥0 (−1)n xnn!  −  ∑n≥0 (−1)n xn+1n!
=   ∑n≥0 (−1)n xnn!  +  ∑n≥1 (−1)n xn(n−1)!   =   ∑n≥0 (−1)n(n+1) xnn!

Also,  ex2/2  =  ∑m≥0 (2m)!2m m! x2m(2m)!  =  ∑n≥0 n!odd xnn! , where we invent the notation:  n!odd = (1)(3)(5)⋯(n)  for n odd, and n!odd = 0 for n even. (This appeared in HW 1/24 #4.) Applying Wilf's Rule 3' (p 42):

i=0n (n | i) (−1)i (i+1) an−i   =   n!odd
In other words:
an   =   n!odd  +  ∑ i=1n (n | i) (−1)i+1 (i+1) an−i .
5. The asymptotic formula is just as easy as before, since the only pole (vertical asymptote) is again x = 1. The residue (coeffiicient in the partial fraction decomposition) is:  A  =  limx→1 (1−x) exp(x + x2/2)(1−x)  =  e3/2. Then we know  f(x)  =  A(1−x) + ε(x),  where ε(x) is a correction term with no poles, which means its Taylor coefficients are much smaller than those coming from the geometric series. That is:  ann!  ∼  e3/2,  and  an  ∼  n! e3/2.

• 2/17: Midterm Review 1
HW:
1. Jane's Chocolate Shop sells small boxes for \$1, large boxes for \$2, and deluxe boxes for \$3. Do a full analysis of the following counting problems, computing the generating function (ordinary or exponential), an explicit formula (if possible), a recurrence, and an asymptotic formula.
1. How many ways to sell \$100 worth of chocolates in one day?
Example: 18 small, 29 large, 8 deluxe, for a total sale of 18 + 29(2) + 8(3) = 100.
2. The cash register printout records each transaction in order. How many ways can this come out, selling \$100 worth of chocolates?
Example: small, large, large, small, deluxe,..., giving a total of \$100.
2. Generalizing Prob 1(b), define an = ways to sell \$n worth of \$1, \$2, and \$3 boxes, where the order of transactions matters. Construct a Deletion Transform to discover and prove a recurrence for an. (Is this the recurrence you got from generating functions in the previous problem?)
3. Continuing Prob 1(b), it turns out Jane puts more than chocolate into her brownies. In fact, all the customers that day are Drug Enforcement Agents, buying with dollar bills invisibly marked #1,..., #100. At the end of the day, they raid the store and confiscate the stack of 100 one-dollar bills.
1. How many ways could the 100 bills have been put into the cash register?
Example: First transaction: bills #52, #37. Second transaction: bills #96, #22, #30. Third transaction: bill #16. And so on, until all 100 bills are spent.
2. Compare the answer with Prob 1(b), and combinatorially explain the relationship between them.
4. Same as Prob 3, but with the order of transactions irrelevant, and the order of bills within each transaction irrelevant.
Example: 18 × \$1 boxes, bought with bills #2, #15, #17,.... Also 29 × \$2 boxes bought with bills {#7, #49} and {#77, #98} and .... Also 8 × \$3 boxes bought with bills {#19, #22, #80} and ....
1. How many ways could the 100 bills have been spent?
2. Compare the answer with Prob 1(a), and explain why you do not have the same kind of relationship that you saw in 3(b).
Solutions:

1. Chocolate sales
1. Selling \$100 worth of \$1, \$2, \$3 boxes, with order irrelevant.
• Step 0: Generalize to a sequence: an = number of ways to sell \$n (i.e. n dollars worth).

• Step 1: Find the generating function. Since the outcomes (chocolate sales of \$n) are not objects labeled 1,..., n, we should use ordinary generating functions, summarized in Notes 1/15. There is a simple choice algorithm for producing outcomes of any size:

 (choose any boxes of \$1, \$2, \$3) ⇔ (0×\$1 or 1×\$1 or 2×\$1 or ⋯)   and (0×\$2 or 1×\$2 or 2×\$2 or ⋯)   and (0×\$3 or 1×\$3 or 2×\$3 or ⋯) .

Translating from logic to algebra and simplifying the geometric series:

f(x)   =   ∑n≥0 anxn   =   (x0 + x1 + x2 + ⋯) (x0 + x2 + x4 + ⋯) (x0 + x3 + x6 + ⋯)
=   1(1−x) 1(1−x2) 1(1−x3)   =   1(1−x)(1−x2)(1−x3) .

• Step 2: Brute force. If we only want the Taylor coefficient a100, Wolfram Alpha gives it as: a100 = 844.

• Step 2: Asymptotic formula. This is the easiest way to work out an approximate answer for general n. The poles of f(x) are the complex roots of the denominator: α = 1, β = −1, γ = cos(3) + i sin(3), δ = cos(3) − i sin(3). Now, all of these have |x| = 1, so they might all contribute to the dominant term. However, the root α = 1 has a triple zero in the denominator, and the partial fraction decomposition would be of the form:

f(x)   =   1(1−x) 1(1−x2) 1(1−x3)
=   1(1−x) (1−x)(1+x) (1−x)(1 − x/γ)(1 − x/δ)
=   1(1−x)3 (1+x) (1 − x/γ)(1 − x/δ)
=   A(1−x)3  +  B(1−x)2  +  C(1−x)  +  D(1+x)  +  E(1 − x/γ)  +  F(1 − x/δ) .

That is, x = 1 is the steepest pole at this distance, and should have the largest effect on the Taylor coefficients. Indeed, if we consider the Known Series, we see the first term must have much larger coefficients than the others. Thus we can approximate:

f(x)   ≈   A(1−x)3   =   ∑n≥0 A ((3 | n)) xn ,

and we use L'Hôpital's Rule three times to get:

A   =   limx→1 f(x) (1−x)3   =   limx→1 (1−x)3(1−x)(1−x2)(1−x3)   =   −6−36 .   =   16 .

(Wolfram Alpha input: third derivative (1-x)(1-x^2)(1-x^3) at x = 1.) Therefore:

an   ∼   16 ((3 | n))   =   112 (n+1)(n+2)   ∼   n212

For example, it gives a100100212 ≈ 833.3, or a bit more complicated a100112 (101)(102) ≈ 858.5. Since we saw above that a100 = 884, these have relative error of 6% and 3% respectively.

• Step 2: Explicit formula. The straight partial fraction decomposition will not give a nice formula because of the complex poles we saw above. However, there is a neat trick to compute the Taylor series of this kind of rational function: consolidate the denominator factors into one simple denominator, balancing with a polynomial in the numerator.
We use the identity  1 − zk  =  (1−z) (1 + z + z2 + ⋯ + zk−1), so that 1(1−z)  =  (1+z+z2+⋯+zk−1)(1−zk) . Hence:

f(x)   =   1(1−x) 1(1−x2) 1(1−x3)
=   (1+x+⋯+x5)(1−x6)  (1+x2+x4)(1−x6)  (1+x3)(1−x6)
=   (1+x+2x2+3x3+4x4+5x5+4x6+5x7+ 4x8+3x9+2x10+x11+x12)(1−x6)3.

Now using the Known Series  1(1−z)3  =  ∑m≥0 ((3 | m)) xm  , we get:

f(x)   =   ∑m≥0 ((3 | m)) x6m  +  ∑m≥0 ((3 | m)) x6m+1  +  2 ∑m≥0 ((3 | m)) x6m+2
3 ∑m≥0 ((3 | m)) x6m+3  +  4 ∑m≥0 ((3 | m)) x6m+4  +  5 ∑m≥0 ((3 | m)) x6m+5
4 ∑m≥0 ((3 | m)) x6m+6  +  5 ∑m≥0 ((3 | m)) x6m+7  +  4 ∑m≥0 ((3 | m)) x6m+8
3 ∑m≥0 ((3 | m)) x6m+9  +  2 ∑m≥0 ((3 | m)) x6m+10  +  ∑m≥0 ((3 | m)) x6m+11
+  ∑m≥0 ((3 | m)) x6m+12

Collecting coefficients of xn, where n = 6m, 6m+1,... :

a6m   =   ((3 | m)) + 4((3 | m−1)) + ((3 | m−2))
a6m+1   =   ((3 | m)) + 5((3 | m−1))
a6m+2   =   2((3 | m)) + 4((3 | m−1))
a6m+3   =   3((3 | m)) + 3((3 | m−1))
a6m+4   =   4((3 | m)) + 2((3 | m−1))
a6m+5   =   5((3 | m)) + ((3 | m−1))

For m = 0, it is understood that ((3 | −1)) = 0. Simplifying by: ((3 | m)) = (m+2 | m) = (m+2 | 2) = ½(m+1)(m+2), we get, for m ≥ 1:

a6m   =   3m2 + 3m + 1
a6m+1   =   (m+1)(3m+1)
a6m+2   =   (m+1)(3m+2)
a6m+3   =   3(m+1)2
a6m+4   =   (m+1)(3m+4)
a6m+5   =   (m+1)(3m+5) .

For the original value n = 100 = 6(16) + 4, this gives:

a100 = (16 + 1) (3(16) + 4) = 884.

Note how the asymptotic approximation above brushes aside the detailed differences between n = 6m, 6m+1,..., 6m+5, but it agrees in the leading term 3m2, which is the same for all cases. For example, a6m(6m)212 = 3m2.

• Step 2: Recurrence. We can clear denominators in a couple of ways, giving different recurrences. Clearing everything:

(1−x)(1−x2)(1−x3) f(x)   =   1

(1 − x − x2 + x4 + x5 − x6) ∑n≥0 anxn   =   1 + 0x + 0x2 + ⋯ .

Now, xk f(x)  =  ∑n≥0 an−k xn, always understanding an = 0 for negative n. Taking coefficients of xn for n ≥ 1 in the above equation:

an − an−1 − an−2 + an−4 + an−5 − an−6   =   0

an   =   an−1 + an−2 − an−4 − an−5 + an−6   for   n ≥ 1   (from a0 = 1).

We could get a simpler recurrence by only partially clearing denominators, while leaving a nice power series on the right:

(1−x2)(1−x3) f(x)   =   1(1−x)

(1 − x2 − x3 + x5) ∑n≥0 anxn   =   1 + 1x + 1x2 + ⋯

an − an−2 − an−3 + an−5   =   1

an   =   an−2 + an−3 − an−5 + 1.

This actually holds for all n ≥ 0, understanding an = 0 for negative n.

2. Selling \$100 worth of \$1, \$2, \$3 boxes, where order matters.
• Step 0: Again, let an = number of ways to sell \$n, but now order of the transactions matters.

• Step 1: Find the generating function. Again, the outcomes have no labels 1,..., n, so we use ordinary generating functions. We again get a choice algorithm, this time using both the Product Principle (an outcome is a sequence of independent choices, namely which kind of box sold in each transaction), along with the Sum Principle (split all outcomes into disjoint cases, depending on how many boxes in total):

 (list of k ≥ 0 boxes of \$1, \$2, \$3) ⇔ (0 boxes)  or  (1 box: \$1 or \$2 or \$3)  or  ( 2 boxes: (\$1 or \$2 or \$3) then (\$1 or \$2 or \$3) )  or  ( 3 boxes: (\$1 or \$2 or \$3) then (\$1 or \$2 or \$3) then (\$1 or \$2 or \$3) )  or  ⋯

Translating from logic to algebra and simplifying the geometric series:

f(x)   =   ∑n≥0 anxn   =   1  +  (x1 + x2 + x3)  +  (x1 + x2 + x3)2  +  (x1 + x2 + x3)3  +  ⋯
=   1(1 − (x+x2+x3))   =   1(1−x−x2−x3) .

(In the previous unordered problem, we had: f(x)  =  1(1−x)(1−x2)(1−x3)  =  1(1−x−x2+x4+x5−x6) , so we see that this problem is similar but simpler.)

• Step 2: Brute force. If we only want the Taylor coefficient a100, Wolfram Alpha gives it with no trouble as the 27-digit number:
a100   =   180,396,380,815,100,901,214,157,639
that is, 180 septillion or so. (This is so much larger than the answer in Prob 1(a) because it counts the possible orderings of dozens of transactions.)
How does the computer get these coefficients so quickly (only thinking for a fraction of a second)? Let's see...

• Step 2: Asymptotic formula. Wolfram Alpha gives the poles of f(x) as:

α ≈ 0.54 ,     β ≈ − 0.77 + 1.12i ,     γ ≈ − 0.77 − 1.12i ,

all simple poles (not multiple, as in the previous problem). The partial fraction decomposition is of the form:

f(x)   =   1(1−x−x2−x3)   =   1(1 − x/α)(1 − x/β)(1 − x/γ)
=   A(1 − x/α)  +  B(1 − x/β)  +  C(1 − x/γ) .

Since x = α is the pole closest to x = 0, it has the strongest effect on the Taylor coefficients. In fact, the other poles have |β| = |γ| > 1, so their contributions 1βn and 1γn will shrink exponentially, and give only a tiny correction term. Thus, we can approximate:

f(x)   ≈   A(1 − x/α)   =   ∑n≥0 (Aαn) xn ,

and we use L'Hôpital's Rule to get:

A   =   limx→α f(x) (1 − x/α)   =   limx→α (1 − x/α)(1−x−x2−x3)

=   (−1/α)(−1−2α−3α2)   =   1α(1+2α+3α2) .

Therefore:

an   ∼   Aαn   =   1αn+1(1+2α+3α2) .

This is a useful formula because we can approximate α as well as we want, for example by Newton's Method. Taking α ≈ 0.54368 90126 92076 36157 08560 (25 decimal places), we get a100 ≈ 180,396,380,815,100,901,214,156,685, which is accurate to 23 digits. Because the extra terms shrink exponentially, not only the relative error of the asymptotic formula goes to zero, but the absolute error as well.

• Step 2: Exact explicit formula. We could compute the coefficients B,C in the partial fraction decomposition the same way as A, getting an exact formula  an  =  Aαn + Bβn + Cγn . However, since the last two terms are small corrections in terms of the complex numbers β, γ, this is not any more useful than the asymptotic formula.

• Step 2: Recurrence. Since the denominator is an irreducible polynomial, we must clear it all:

(1−x−x2−x3) f(x)   =   1

(1 − x − x2 − x3) ∑n≥0 anxn   =   1 + 0x + 0x2 + ⋯ .

Recall xk f(x)  =  ∑n≥0 an−k xn, where an = 0 for n < 0. Taking coefficients of xn for n ≥ 1 in the above equation:

an − an−1 − an−2 − an−3   =   0

an   =   an−1 + an−2 + an−3   for   n ≥ 1   (from a0 = 1).

2. Deletion Tranform for an = # ordered sums of \$1, \$2, \$3 with total \$n. For n ≥ 1, delete the last summand: this is either 1, leaving an object of type an−1; or 2, leaving an−2, or 3, leaving an−3. This is reversible, so a bijection. That is, an  =  an−13 + an−2 + an−3 . This is indeed the recurrence we found in Prob. 1(b).

3. Ordered transactions of \$1, \$2, \$3 with one-dollar bills marked 1,...,n. The order of bills within in each transaction also matters.
1. Solve counting problem
• Step 0: Let bn be the number of ordered trnasactions with total \$n in marked one-dollar bills. Since each outcome of size \$n is labeled 1,...,n, we use an exponential generating function g(x)   =   ∑n≥0 bn xnn! .
• Step 1: We construct the appropriate exponential family. Since each transaction chooses a list of 1,2, or 3 labeled dollar bills, it can be considered as a card from the deck of directed paths of length 1,2, or 3:

D   =   { , , , , ,
, , , }

and d(x)  =  x + 2! x22! + 3! x33!  =  x + x2 + x3. A day's worth of marked transactions corresponds to an ordered hand with any number of cards from D, so by Notes 2/7 #5, the enumerator function is:

g(x)  =  ℓ(x)  =  1(1 − d(x))  =  1(1−x−x2−x3) .

2. We notice that the exponential generating function of bn is exactly the same as the ordinary generating function f(x) in Prob 1(b), whose coefficients an count ordered transactions with identical (unmarked) dollar bills. This implies  bnn!  =  an ,  or  bn  =  an n! .
This can be proved combinatorially by a transformation: given an ordered transaction with marked bills, consider the corresponding transaction with unmarked bills, as well as the total order of the 100 marked bills in the cash register. These two pieces of data are independent. The transformation is reversible, since any unmarked transaction shows us how to split up the list of 100 marked bills into individual transactions.
Simply put, each unmarked transaction can have n! possible orders for the marked bills.
4. Unordered transactions with marked bills.
1. This is similar to 3(a). Let the number of undordered marked transactions be cn, with exponential generating function h(x). Since the order of bills in each transaction is irrelevant, the deck is now:

D   =   { , , }

with d(x)  =  x + x22! + x33! . Since the order of transactions is irrelevant, we take unordered hands, and the exponential generating function is:
h(x)   =   exp(x + x22! + x33!) .
We can easily get the x100 coefficient by computer. It is:

c100 = 11527937348312713865082241287737153907730362053400425345132475796235815534719539623297472916358562840576

2. The answer c100 is actually less than 100!, and is definitely not 100! times the answer to the unmarked problem. This is because each unmarked, unordered outcome cannot be marked in 100! ways: most of these ways would count as the same, because order is mostly irrelevant.

• 2/21: Midterm Exam, Friday in class. Come 5 min early for extra time.
To study:
• Re-do all quizzes, covering up your previous answers, then check with my answers from class notes. Make sure you understand all mistakes. I can email you any missing quizzes on request.
• Do Midterm Review HW 2/17 & 2/19. You must actually solve these to do any good, not just read the solutions.
• Review old notes, class notes, and the Wilf text.
• Review old homework, and finish problems you didn't do.
• Come to office hours in Wells D-326: Mon, Wed 10−11 and 1−3; Thu 1−3:30 .
Main topics:

• 2/24: Trees and generating functions
HW:
1. As in class, let an count the number of unlabeled ordered trees (family trees) with n vertices, and let f(x)  =  ∑n≥0 anxn be its ordinary generating function. We applied the same Deletion Transform as in HW 1/13, thinking of it as a recursive choice algorithm. The Sum and Product Principles directly turn this algorithm into the equation:   f(x)  =  f(x)2 + x .
1. Solve the above equation for f(x), and compare it with the generating function of the Catalan numbers. As a result, write an in terms of Cm for some m.
2. For the same an, find a different recurrence coming from a different Deletion Transform. That is, remove the ancestor vertex, leaving a list of any number of smaller ordered trees. Translate this recursive choice algorithm into an equation involving f(x).
3. Show that f(x) is the inverse function of g(x) = x − x2. That is, g(f(x)) = x.
2. Binary trees. Recall from Quiz 4 that an unlabled ordered binary tree has an ancestor vertex at the top, and every vertex has either no children or two children (older and younger).
1. Find a Deletion Transform for the binary trees, deduce an equation for the generating function f(x), and solve it to find f(x) explicitly. If possible, relate the number of binary trees to well-known numbers.
2. Show that the generating function f(x) is the inverse function of g(x) = x(1+x2). That is, g(f(x)) = x.
3. Same as Prob 2, but for ternary trees, in which each vertex has either no children or three children (in age order). For part (b), find an appropriate function g(x) which is the inverse of f(x).
4. In class, we considered rooted Cayley trees: that is, trees on a set of labeled vertices V = {1,...,n}, with some vertex designated as the root. (Identical trees with different roots count as different objects.)
1. Cayley's Theorem tells the number of possible n-vertex Cayley trees without a designated root. Use this to find the number of n-vertex rooted Cayley trees.
2. Give a Deletion Transform for rooted Cayley trees: a tree is equivalent to the root and a set of smaller trees. Give an equation involving the exponential generating function f(x) of rooted Cayley trees. (Why use exponential generating functions here?)
3. Assume  f(x)  =  x + x2 + a3 x33! + a4 x44! + higher terms. Substitute this into the recursive equation  f(x)  =  x ef(x), equate coefficients of x3 and x4, and solve for a3, a4, recovering the combinatorial result of (a).
4. Find a function g(x) which is the inverse function of f(x), so that g(f(x)) = x.
Solutions

• 2/26: Lagrange Inversion Formula
Reading: Notes 2/26, Proof of the Lagrange Inversion Formula
HW:
1. In HW 2/24 #1−4, we got equations for several f(x), the generating functions for the number of trees of various kinds. In each case, use Lagrange Inversion to get an explicit formula for the number of trees. Have we seen any of these answers before?
Hint: Don't use an explicit formula for the generating function f(x). Instead, use the recurrence equation for f(x) to write it as the inverse function of some simple function g(x), and apply the Lagrange Inversion Formula to find the coefficients of f(x) in terms of g(x). (Actually, it is equivalent, but easier to use the second form of Lagrange Inversion.)
2. Conjugal family trees. The matriarch, Grandma Jones, lives in a house with 20 of her descendants and their spouses. Example:
Here a single node indicates an unmarried descendant, and a double node •• indicates a descendant and spouse. In the picture, Grandma has three children, with the eldest and youngest married, but all having children of their own, etc. The most extreme possible example would be 20 generations of single descendants. Also, Grandma may have a spouse herself.
Question: How many possible family trees with 20 people?
1. Generalize to trees with n people. Define a Deletion Transform to get a recursive choice algorithm.
2. Turn the choice algorithm into an equation involving the generating function f(x). Solve the equation to get an explicit formula for f(x).
3. Use Wolfram Alpha to get the explicit answer for 20 people, using the explicit formula for f(x). Would Lagrange Inversion be effective in this case?
4. Show that the generating function in this case is closely related to that for ordered trees (without considering spouses). Exactly what is the relationship?
3. Same as Prob 2, but with the rule that only married spouses can have children.
Solutions

• 2/28: Extra Credit Assignment: Integer Partitions.
• The last entry in the Twelvefold Way chart is pk(n), the number of partitions of n into k parts: i.e. the surjective functions f : [n] → [k] with both [n] and [k] indistinguishable; or the ways to put n unmarked balls into k exchangeable, non-empty bins. (Here we reverse the roles of n and k from the chart, so as to have n ≥ k.)
• If we allow any number of parts, we obtain the partition number:   p(n)  =  p≤n(n)  =  p1(n) + ⋯ + pn(n).
• The integer-partition numbers pk(n) and p(n) are analogous to the corresponding set-partition numbers, the Stirling number {n | k} and the Bell number B(n), which count ways to partition a set of n labeled balls.
• We usually denote partitions by writing the multiplicity of balls in each bin, from most full to least full, using the traditional notation:

λ  =  (λ1, λ2,..., λk)   where   λ1 ≥ λ2 ≥ ⋯ ≥ λk > 0   and   λ1 + λ2 + ⋯ + λk = n.

The λi are called the parts of λ.
• Another useful notation is the Young diagram or Ferrars diagram of λ, in which we draw left-justified rows of dots, first a row of λi, then λ2, etc.
• For example, p(4) = 5 counts the partitions: (4), (3,1), (2,2), (2,1,1), (1,1,1,1), having Young diagrams:
 • • • •
 • • • •
 • • • •
 • • • •
 • • • •

• The (ordinary) generating function of the partition numbers is:

φ(x)   =   ∑n≥0 p(n)xn   =   ∏i≥1 1(1−xi) .

• Euler's Pentagonal Number Theorem states that:

1φ(x)   =   ∏i≥1 (1−xi)   =   1   +   ∑m≥1 (−1)m(x½m(3m−1)  + x½m(3m+1)).

That is, when you multiply out the denominator of φ(x), almost all terms cancel to give zero; but for n equal to a "pentagonal number" ½m(3m±1), one term survives, giving a coefficient of ±1. (By the way, Euler is pronounced "oiler", not "yuler".)
• We proved the Pentagonal Number Theorem by first going backward from the generating function 1φ(x) to a combinatorial model. The coefficients of ∏i≥1 (1−xi)  =  ∑n≥0 anxn are given by:

an   =   #{partitions of n into an even number of distinct parts}
−   #{partitions of n into an odd number of distinct parts}.

The first term in this model counts all λ = (λ1,..., λk) such that k is even, and the parts λi are all distinct: λ1 > λ2 > ⋯ > λk > 0. The second term is the same, but with k odd. For example, n = 9 can be partitioned into a even number of distinct parts in 4 ways as: (8,1), (7,2), (6,3), (5,4); and into an odd number of distinct parts also in 4 ways as: (10), (6,2,1), (5,3,1), (4,3,2).
• To finish the proof of the Theorem, we gave Franklin's Transformation, which takes partitions with an even k to partitions with an odd k, and vice versa. The only exceptions are two special shapes of partitions, having m rows and n = ½m(3m−1) or ½m(3m+1) for m ≥ 1.
Extra Credit HW: You can hand in any of the following problems for Extra Credit.
1. Euler's Pentagonal Number Theorem
1. Compute p(n) for n ≤ 10 from the Pascal-triangle-type recurrence for pk(n). (You will need to set the correct initial values on the boundaries of the triangle.)
2. Prove the following recurrence from the Pentagonal Number Theorem:

p(n)   =   ∑m≥1 (−1)m+1(p(n − ½m(3m−1))  +  p(n − ½m(3m+1))).

3. Use the recurrence to compute p(n) for n ≤ 30. (Show your computations or a spreadsheet with formulas, not just the p(n) results.) Compare the efficiency with the method of part (a).
2. Franklin's Transformation Proof of the Pentagonal Number Theorem.
1. Illustrate Franklin's Transformation for n = 15. That is, make a table of all partitions with an even number of distinct parts, matched with the corresponding partitions with an odd number of distinct parts. There should be 27 partitions in all.
2. Look up the pentagonal numbers (analogous to the triangular and square numbers). The exceptional partitions in Franklin's Transformation are those of the form:

(2m−1, 2m−2,..., m)   and     (2m, 2m−1,..., m+1).

Show that these partitions have weight n = ½m(3m−1) and ½m(3m+1) respectively, which are the generalized pentagonal numbers.
3. The Young diagram of (2m−1, 2m−2,..., m) is a quadrilateral. Nevertheless, give a natural, geometric correspondence between the dots in this partition and the dots in the pentagon defining the mth pentagonal number.
3. Another Euler theorem: The number of partitions of n into distinct parts is equal to the number of partitions of n into odd parts. For example, there are 8 partitions of n = 9 into distinct parts (all λi's different): (9), (8,1), (7,2), (6,3), (6,2,1), (5,4), (5,3,1), (4,3,2); and also 8 partitions of n = 9 into odd parts (all λi's odd numbers): (9), (7,1,1), (5,3,1), (5,1,1,1,1), (3,3,3), (3,3,1,1,1), (3,1,1,1,1,1,1), (1,1,1,1,1,1,1,1,1).
1. Letting an be the number of partitions of n with distinct parts, find the generating function ∑n≥0 anxn.
2. Letting bn be the number of partitions of n with odd parts, find the generating function ∑n≥0 bnxn.
3. Prove the generating functions in (b) and (c) are the same, by algebraic methods.
4. Find a transformation of partitions which reversibly transforms partitions with distinct parts into partitions with odd parts, along with the inverse transformation going the other way.
4. Theorem: The number of partitions of n with at most k parts equals the number of partitions of n whose parts are at most k. For example, there are 5 partitions of n= 9 into at most 2 parts: (9), (8,1), (7,2), (6,3), (5,4); and there are also 5 partitions whose parts are 1 or 2: (2,2,2,2,1), (2,2,2,1,1,1), (2,2,1,1, 1,1,1), (2,1,1,1,1,1,1,1), (1,1,1,1,1,1,1,1,1).
Problem: Give a transformation proof of this Theorem.

• 3/10: Unlabeled rooted trees.
HW:
1. Tree numbers
1. Use the Dlog Recurrence Formula in the Notes III.v to compute rn, the number of distinct unlabeled, rooted, unordered trees, for n = 2,...,10, starting from r0 = 0, r1 = 1. That is:

rn+1   =   1nk=1n    ∑i | k i ri rn−k+1 .

This is not very difficult even by hand, showing the efficiency of the recurrence.
Verify the above computation by drawing all the trees for as large a size as you can. Hint: draw the possible tree shapes for a given size, and see how many distinct possible locations for the root.
2. We might expect that, given an unlabeled, rooted, unordered tree with n vertices, we could put labels on the vertices in n! ways, so that we get a transformation (T, σ)  ↔  L, where T is an unlabeled tree, σ is a permutation of [n], and L is a labeled, rooted, unordered tree. Based on this, we would expect:

rn n!  =??  nn−1,

suince the number of L is nn−1, as we saw in today's Quiz. However, the equation is false because the above transformation is not reversible: the data on the two sides is not equivalent.
Why not? Explain with an example. Are there any values of n for with the equality holds? Is one side always bigger than the other?
2. x D log method.
1. Re-do HW 2/12 #2, which describes the x D log method for producing recurrences from difficult generating functions (when it is not practical to clear denominators).
2. Recall from HW 2/28 that the integer-partition numbers p(n) have the generating function  φ(x)  =  ∏i≥1 1(1−xi). Use the x D log method as in Notes III to derive a recurrence for p(n). Use this recurrence to compute some values of p(n): how efficient is it compared to Euler's Pentagonal Number Recurrence?
3. Extra Credit: Use the x D log method on the generating function of the Fibonacci numbers,  f(x)  =  ∑n≥0 Fn+1xn  =  1(1−x−x2). Obtain a weird recurrence for Fn+1.
3. Naive recurrence for rn .
1. Write the generating function of rn as: x + x2 + r3x3 + r4x4 + (higher terms), and substitute this into the generating function equation of Notes II.iv. Equate coefficients of x3 and x4 on the two sides, and solve for r3 and r4. This shows that in principle, the generating function equality can be used to determine rn .
2. More systematically, expand the right side  ∏i≥1 1(1 − x)ri  as a product of Negative Binomials, getting a product of summations with multi-choose coefficients ((ri | ki)). Here ki ≥ 0 is the index variable of the ith summation.
Figure out which values of k1, k2,... give an exponent of xn. Equating coefficients of xn on the two sides then gives a recurrence for rn+1 as a kind of infinite convolution of multi-choose numbers.
The result is the "Naive" Recurrence Formula (since it follows unimaginatively from the generating function equality).
3. The above recurrence should give:

r5   =  ((r1 | 4)) + ((r1 | 2)) ((r2 | 1)) + ((r2 | 2)) + ((r1 | 1)) ((r3 | 1)) + ((r4 | 1))
=  1 + 1 + 1 + 2 + 4   =  9 .

Verify this using the recursive choice algorithm of Notes II: construct the 9 rooted trees as a root along with multi-sets of smaller rooted trees. For example, the second term of the formula corresponds to the unique multiset M with two 1-vertex trees and one 2-vertex tree:
M   =  { ® , ® , ®−−O } ,
which produces a 5-vertex tree T by attaching a new root to each of the roots in M:

 T   = ®−− ® −−® −−O | ®

Do this for all the other terms.
In fact, the Naive Recurrence Formula is a direct consequence of the combinatorial recurrence: generating functions are not really needed.
4. Super Extra Credit: Can you prove the Dlog Recurrence Formula for rn by a combinatorial correspondence, or in any way without generating functions? You could start by moving the denominator n to the left side, and interpreting each term as counting something, but I have no idea how to do this. Or somehow relate it to Burnside's Theorem, since that starts with 1n?? This would count as original research.
Solutions: Full solutions here.
Also, for 3(b):
• The recurrence is:

rn+1   =   ∑ki≥1 ((ri | ki))   =   ∑k ((r1 | k1)) ((r2 | k2)) ((r3 | k3)) ⋯

where the sum is over all sequences k = (k1, k2, k3,...) such that k1 + 2k2 + 3k3 + ⋯ = n . In fact, only r1,..., rn occur in this formula, so it is a recurrence for rn+1 .
• Example: To compute r5, we sum over k = (4), (2,2), (1,0,1), (0,0,0,1), so that:

r5 = ((r1 | 4)) + ((r1 | 2)) ((r2 | 2)) + ((r1 | 1)) ((r3 | 1)) + ((r4 | 1)) .

Substituting r1 = r2 = 1 , r3 = 2 , r4 = 4 and computing multi-choose numbers gives r5 = 1 + 1 + 1 + 2 + 4 = 9.

• 3/12: Rooted and unrooted trees, Otter's Lemma
1. Trees with n = 6 vertices
1. Draw all the unrooted, unlableled, unordered trees with 6 vertices (by definition, the number of these is t6).
2. For each tree, determine how many symmetries it has, and write down a few (as permutations of the vbertices, in cycle notation).
3. For each tree T, determne pT, the number of distinct symmetry classes of vertices. Also determine qT, the number of symmetry classes of non-symmetric edges (i.e. edges which are not taken to themselves under any symmetry). Finally, draw T, the quotient graph (which is in fact a tree).
4. Compute r6, the number of rooted, unlabeled, unordered trees, as the sum of pT for all the unrooted T.
2. Find the smallest possible unlabeled tree which has no symmetries (other than the identity ε).
3. Consider the following graph G, with vertices V = [18], conisisting of a 9-cycle with vertices {1,...,9}; together with the edges 2,10 and 5,13 and 8,16; and the paths 3,11,12 and 6,14,15 and 9,17,18.
1. Find the symmetries and the quotient graph of G.
2. Extra Credit: Otter's Lemma says that if T is a tree, then the quotient graph T is a also a tree. Is the converse statement true? That is, if G is a graph whose quotient G is a tree, then must G also be a tree?
3. Extra Credit: Prove or disprove: A tree T can never have |Sym(T)| = 3; that is, exactly 2 non-trivial symmetries.
Solutions: Thanks to Amanda and Amy for corrections.

1. Trees with 6 vertices. The trees are:
For each, we write the number of symmetries |Sym(T)|; the number of symmetry classes of vertices and of non-symmetry edges, pT and qT; and the quotient tree T, which for these cases is always a k-vertex path Pk:

T1T2 T3 T4 T5T6
|Sym(T)| 222(4)(2) = 83! = 65! = 60
pT354242
qT243131
T P3P5P4P2P4 P2

Note that T1 and T4 each have a symmetry edge in the middle (taken to itself under a reflection), which does not count in qT nor produces any edge in T.
2. Clearly, all the trees with ≤ 6 vertices have non-trivial symmetries. The only asymmetric tree with 7 vertices is the tree formed by joining paths P2, P3, P4 at a common end point (total 2+3+4−2 = 7 vertices).
3. Symmetries and quotients of graphs
1. Any symmetry must take vertices of degree d to other vertices of degree d, and it is easily seen that the only non-trivial symmetries are ±120° rotation. That is, Sym(G) = {ε, σ, σ2}, where ε is the identity and σ = (1,4,7)(2,5,8)(3,6,9)(10,13,16)(11,14,17)(12,15,18). The quotient graph is:

 12 | 10 11 | | 1 −− 2 −− 3 \ /

2. The quotient in (a) is not a tree, since there is an edge 13. Also, the quotient graph of any cycle Ck is a path point. You have to think more carefully to get a non-trivial tree as the quotient of a graph with cycle.

• 3/14: Rooted and unrooted trees, Otter's Lemma
Reading: HW: This is just the regular HW for last Fri.
1. Continuing HW 3/12 #1, consider unrooted, unlabeled trees with n = 6 vertices.
1. Verify that qT = pT − 1 for each tree.
2. Compute r6 = ∑T pT, the number of vertex-rooted trees, and e6 = ∑T qT, the number of edge-rooted trees, and verify that t6 = r6 − e6.
3. Verify the formula from the Notes IV(v) in this case:   e6  =  ½[ ∑ i=15 ri r6−i  −  r3 ].
4. Make the table of the bijection T" ↔ {T'1, T'2} which proves the above formula in the Notes IV(v). That is, T" is an edge-rooted tree, and {T'1, T'2} is a pair of non-identical vertex-rooted trees with a total of n = 6 vertices.
2. Start working on the Hand-In HW due Fri 3/21.
3. Give an example of a finite graph G with many edges, all of them symmetry edges. That is, for any edge, there is a graph symmetry which flips it over.
4. Infinite trees. According to the Hand-In HW, a finite tree can have only one symmetry edge, but the same is not true of infinite trees. For each condition below, construct an infinite tree T satisfying them, or prove this is impossible.
1. T has infinitely many symmetry edges.
2. T has exactly one symmetry edge.
3. T has exactly two symmetry edges.
Solutions
Quiz 22 on Fri 3/14 was puzzling for almost everyone. I clearly underestimated the difficulty of the ideas around graph symmetry and quotients. We will have another go at this in Monday's quiz. Here is another example for you to study. Pay particular attention to the what kind of structure each object is (mapping, set, set of sets, etc.).
• Consider the graph G = (V,E) with V = [7] and E = {14, 24, 34, 45, 56, 57}. That is, G is a tree with a 2-vertex stem and 3 branches on the left, two branches on the right.
• A symmetry of G is a permutation mapping σ : V to V. That is, you input a vertex to σ, and it outputs an image vertex. Each σ must take edges to edges: that is, if ij is an edge in E, then σ(i) σ(j) must also be in E.
• The symmetry group Sym(G) is the set of all symmetries (a set of mappings).
• I will write the symmetries in cycle notation, but omitting 1-cycles. For example, σ = (132) means (132)(4)(5)(6)(7), the mapping σ(1) = 3, σ(2) = 1, σ(3) = 2, and σ(i) = i otherwise. This graph symmetry is neither a reflection nor a rotation; rather, it permutes the left branches while leaving the right branches fixed. We can check directly that σ takes edges to edges: e.g. 14 goes to σ(1) σ(4) = 34.

Sym(G) = { ε, (12), (13), (23), (123), (132), (67), (12)(67), (13)(67), (23)(67), (123)(67), (132)(67) }

Notice that we can permute the left branches and right branches independently, but we cannot switch left and right because we can't squeeze the 3 edges on the left into the 2 edges on the right.
• To define the quotient graph G = (V,E), we must define its vertices and edges. A vertex x of G is a symmetry class of vertices. That is, x is a set of vertices of G:   x = {σ(x) for all σ ∈ Sym(G)}.   V is the set of all the different x (thus, V is a set of sets).

V = {1, 4, 5, 6}, where 1 = {1,2,3}, 4 = {4}, 5 = {5}, 6 = {6,7}.

Note that 1 = 2 = 3 = {1,2,3}, and we say 1 is a representative of its class.
• Next, two distinct vertices x, y form an edge xy in E whenever there is an edge of G between elements of x and y: i.e. when x'y' in E with x' in x and y' in y. (Thanks to Riley for this simple definition.) E = {14, 45, 56}, so G is a path on 4 vertices.

• 3/17: Finish tree enumeration
• Hand-In HW due Fri 3/21 is announced in its own section below.
• Notes 3/12−3/17: Note especially the proofs in III, which I revised.
• Math 880 Notes on Tree Asymptotics. See how this subject continues at a graduate level.
• Analytic Combinatorics by Flajolet and Sedgewick. An encyclopedic textbook of all aspects of enumeration, especially asymptotic formulas via complex analysis. Their motto: "If you can specify it, you can count it."
HW:
1. Compute some unrooted tree-numbers tn, using the known rooted numbers rn from HW 3/10 #1a, and the Otter's Formula in the Notes IV(v). Compare to the values at the Online Encyclopedia of Integer Sequences (#A000055 and #A000081).
2. Work on the Hand-In HW due Fri 3/21.

• Hand-In HW due Fri 3/21. Prove the following:

 Proposition: Any finite tree T has at most one symmetry edge.

Hints:
• Recall that a symmetry edge of a (finite simple) graph G = (V,E) is e = vw such that v = σ(w) for some symmetry σ ∈ Sym(G). (See Notes 3/12−3/17 II(ii) and II(iii)(c).)
• Experiment by trying to construct a counter-example, a tree with two or more symmetry edges. What prevents this from working? Compare with HW 3/14 #3 & 4.
• The Proof Notes from Math 481, give basic tips on style and content of proofs.
• As a basis for your proof, start from the definitions and theorems in the Graph Notes from Math 481 (only parts I & II are relevant). You may also use the HHM textbook, especially Ch. 1.1.2, p. 5 and Ch. 1.3, p. 30. You may quote and use any of the results in these references.
• You may also quote and use the Claims (i)−(iv) in the Solutions 3/14 #4(c). This problem proves that exactly 2 symmetry edges are impossible, whereas you must prove this for ≥ 2 symmetry edges.
Note: My proof is pretty involved, so do not just try to extend it. The theorem you are proving is actually easier, because it involves only finite graphs.
• Show that removing a symmetry edge e from T leaves two disjoint identical trees related by a symmetry, each having half the vertices of T. If there were another symmetry edge e', it would have all the same properties as the original e. Where could e' be, relative to e?
Conditions:
• The proof will be worth 9 points = 3 quizzes.
• Hand in the first draft on 3/21, and when I hand back corrections, you can incorporate them into a second draft for more credit.

• Hand-In HW due Fri 3/28. Second draft of your proof from last week.
• The top scores on the first draft were 6/9pts. The second draft will raise your score toward the maximum 9/9pts.
Re-submit the first draft together with the second.
• Write clear paragraphs, each stating and reaching some logical goal (e.g. a claim or lemma).
• Omit every word that does not advance the logic toward the conclusion. In particular, the proof should not contain examples, since these cannot prove general statements: put examples in a note before or after the proof.
• A schematic picture can help you and your reader keep track of the argument (but does not substitute for the argument, of course).
• Make sure you explicitly use the properties of a tree (connected, acyclic). Ask: would your argument work just as well for any graph G? If not, exactly where does it use the tree properties? Give explicit references to previously known results whenever used.
• Given a symmetry edge e = σ(e), then any other symmetry τ takes e to some other symmetry edge, but there is no immediate reason to deduce τ(e) = e. This would be obvious only if e were the unique symmetry edge (which is what you are trying to prove).
• Here is a good notation which should clarify your arguments.
• For a graph G, let Gx denote the connected component of the vertex x: the subgraph of all vertices y connected to x by paths in G, and all edges yy' in G between such vertices. We also have Gx = Gy for any y ∈ Gx .
• Thus, for a tree T with distinct edges e = xy,  f = vw, we have the connected components:

T−e   =   (T−e)x ∪ (T−e)y
T−f   =   (T−f)v ∪ (T−f)w

• Also, if we remove both edges, we get components: (T−e−f)x, (T−e−f)y, (T−e−f)v, (T−e−f)w. However, T−e−f has only 3 distinct components, so two of these must be the same; by switching labels, we may assume that (T−e−f)x  =  (T−e−f)w, so that:  T−e−f = (T−e−f)v ∪ (T−e−f)x ∪ (T−e−f)y = (T−e−f)v ∪ (T−e−f)w ∪ (T−e−f)y.
• The key point in one proof-strategy is to show something like (T−f)v ⊂ (T−e)x, or (T−e)x = (T−f)v ∪ (T−e−f)w, or (T−e)y ⊂ (T−f)w. Show such statements from their definitions and the basic properties of trees. Any such statement should lead very quickly to a contradiction, since if e, f are symmetry edges, then each component of T−e or of T−f contains exactly half the vertices of T.
• Another proof strategy involves the set of symmetry edges S in T: we can define edges e,f ∈ S to be adjacent if there is a path from e to f in T containing no other symmetry edge. This makes S into vertices of a graph (that is, the elements of S are edges of T, but count as vertices of the derived graph T~). Show explicitly that this graph T~ is a tree, or some similar statement.
Another way to set up T~ would be as a bipartite graph, having vertices of two kinds: V = S ∪ C, where S is the set of all symmetry edges of T, and C is the set of components of T−S (removing all symmetry edges, but not their end-points). The edges of T~ are pairs of the form ec, where the component c contains an end-point of symmetry edge e.

• 3/19: Start on polyhedra.
1. Consider the following standard polyhedra discussed in class, and illustrated in Wikipedia: cube, octahedron, pyramids, prisms, anti-prisms, and vertex-truncations of these.
1. Practice drawing the above polyhedra in a legible way, clearly showing the vertices, edges, and faces.
2. Draw the edge-graphs of the above polyhedra, as graphs without edge-crossings.
3. Determine the dual polyhedra of the above examples.
2. Work on the Hand-In Proof due next time.
Solutions:

1. Standard polyhedra.
• Drawings and edge-graphs of the regular polyhedra (Platonic solids) are on [HHM] Ch. 1.5.3 p. 82. These polyhedra are dual to each other: the cube and the octahedron; the tetrahedron with itself; the dodecahedron and the icosahedron.
• The edge-graph of a pyramid is a wheel graph: a cycle with an extra vertex in the middle and spoke-edges. The dual polyhedron is the same pyramid (upside-down).
• The edge-graph of a polygonal prism is a double cycle with edges between corresponding pairs of vertices. The dual polyhedron is a bipyramid.
• The edge-graph of an anti-prism is a double cycle with zigzag edges in between. The dual polyhedron is a trapezohedron.
• The effect of a vertex truncation on the edge-graph is to replace the truncated degree-d vertex with a d-cycle of degree-3 vertices. The effect on the dual polyhedron is to add an extra vertex slightly beyond the face corresponding to the truncated vertex; i.e. gluing a polygonal pyramid onto that face.

• 3/21: Vertex and face constructions of polyhedra.
1. For a given vector a and constant c, a line in the plane can be defined as:

La,c   =   {xR2 s.t. a x = c}.

Consider the three lines defined by:

(a, c)   =   ((1,1), 2),  ((-1,1), 2),  (−1,2), 0).

1. The 3 lines have 3 pairwise intersection points. Find these points by solving a pair of equations a x = c.
2. The 3 lines cut out 7 regions of the plane. Find the relations of the form  a x  ≤  c  or  a x  ≥  c  which define each region.
3. There are 8 possible choices of  "≤"  or  "≥"  for the 3 values of (a, c), but only 7 regions. What set does the extra choice define?
4. If we did the same exercise for 4 vectors in R3, how many regions would we get? What would be the shape of the bounded region?
2. Constructions of polyhedra
1. Consider the tetrahedron with vertices:

(0,0,0),  (1,1,1),  (1,2,3),  (−1,1,1).

Find the 4 relations of the form a x  ≤  c which define the tetrahedron.
2. Find the center of gravity of the tetrahedron.
3. Find the relations for a polyhedron obtained by slicing off a small part of the corner near (1,2,3). (You decide the slicing plane and how much to cut off.) What is the name of the resulting polyhedron?
4. Find the vertices of your sliced polyhedron in (c).
5. Find the relations for a polyhedron obtained from the tetrahedron by adding a new vertex a little above the triangular face with corners (0,0,0), (1,1,1), (1,2,3). (You pick the vertex.) What is the name of the resulting polyhedron?
Solutions

• 3/24: f-vectors of polyhedra: (n,q,r)
• Euler's Formula, from Martin Aigner & Günter Ziegler, Proofs from THE BOOK
• Notes: Günter Ziegler, Convex Polytopes: Extremal Constructions and f-Vector Shapes
HW:
1. Dual-tree proof of Euler's Formula (see Aigner & Ziegler). Let P be the polyhedron obtained from the octahedron by truncating a vertex.
1. Draw a Schlegel diagram of P: i.e. a planar drawing of the edge-graph G, obtained from projecting P from a point beyond one of the faces onto a screen on the far side.
Hint: Draw the usual edge-graph of the octahedron (4 triangles at each vertex), and modify it by the cut-off corner. Or try to picture the Schlegel projection.
2. Using another color, superimpose the dual graph G*: in each region Ri of G, draw a vertex vi* of G*; and whenever two regions Ri, Rj of G are adjacent, draw an edge vi*vj* of G*. Note that each vertex of G corresponds to a region of G*.
3. Draw a spanning tree T ⊂ G: i.e. a tree connecting all the vertices of G.
4. Draw the subgraph T* ⊂ G* containing all vertices of vi* and all edges vi*vj* which do not cross any edge of the tree T in (c).
5. Explain why T* must be connected and acyclic, given that T is acyclic and connected.
6. Without counting, find the number of edges q in G as the number of edges of T plus the number of edges in T*:

q  =  (n−1) + (r−1),

where G has n vertices and G* has r vertices. Explain why this is equivalent to Euler's Formula.
2. The f-vector of a polyhedron is the triple (n,q,r) of its vertex, edge, and face numbers. Since q = n + r − 2, it is enough to record (n,r). In the next lecture, we will prove
Steinitz's Lemma: For any polyhedron P, we have:

½ n + 2   ≤   r   ≤   2n − 4.

1. In the (n,r) plane, draw the wedge region defined by the above inequalities, and mark the integer points in this region. These are the f-vectors of all possible polyhedra P.
2. For all the standard polyhedra in HW 3/19 #1, including Platonic solids, pyramids and bipyramids, prisms and anti-prisms, compute the f-vector (n,r), and plot it in the above region. (Include some truncations and multiple truncations.)
3. What distinguishes the polyhedra whose f-vector lies on the upper boundary of the (n,r) region? What about the lower boundary?
4. Can you find polyhedra whose f-vectors give all the (n,r) in your picture (up to some bound on n and r)?
3. Work on the second draft of your proof from last week. See the hints below.
4. Extra Credit: Show that every polyhedron has a triangle face, or a simple vertex (a vertex of degree 3), or both. Even stronger, show that the number of triangle faces plus the number of simple vertices is at least 8, so there are at least 4 triangle faces, or at least 4 simple vertices. Hint: Use Euler's Formula, and the Edge-Vertex and Edge-Region Formulas. (From Ziegler p. 24.)
Solutions

1. Here are two drawings of the edge-graph G of the vertex-truncated octahedron: the upper right drawing is a Schlegel projection from the indicated light source; the lower one is the standard drawing for the octahedron, with the top vertex expanded into a 4-cycle. In each drawing, a spanning tree T of G is traced in green, the dual spanning tree T* of G* is in red.
Note that T* must be connected, since all regions of G are part of the one large connected region cut out by T. Also, T* must be acyclic, since any cycle of vertices of T* would correspond to a cycle of regions in G, which would result in a vertex of G with no edge of T going to it, contradicting the definition of spanning tree.
Clearly, every edge of G is either green, or has a red edge crossing it, so the number of edges of G equals the numbers of edges of T and T*:  thus,  q  =  (n−1) + (r−1); in this case, q = (9−1) + (9−1) = 16.
2. Steinitz Lemma
1. The set of f-vectors (n,r) of polyhedra makes the following cone in the plane:

2. The picture above is marked in red with the f-vectors of various polyhedra.
3. The top line r = 2n − 4 corresponds to "simplicial polyhedra", those whose faces are all triangular and whose edge-graphs are maximal planar. The bottom line corresponds to the "simple polyhedra", the duals of simplicial, whose corners all have 3 edges.
4. We can construct polyhedra with all vectors in the cone. We start with prisms, which give all vertices on the diagonal r = n. Performing truncation at a vertex with 3 edges changes (n,r) to (n+2, r+1); and we can repeat such truncation indefinitely, since every vertex of the new face has 3 edges: this fills the top half of the region (above r = n). Taking dual polyhedra then fills the bottom half. Alternatively, repeatedly stack a pyramid onto a triangular face, changing (n,r) to (n+1, r+2).

• 3/26: Steinitz's Lemma and Steinitz's Theorem
• Notes 3/26−3/28
• Survey: Günter Ziegler, Convex Polytopes: Extremal Constructions and f-Vector Shapes
• Connectivity, 3-connected graphs: R. Diestel, Graph Theory, 4th ed., p.10 and p.62
• Maximal planar graphs (equivalent to triangular polyhedra): Math 481 Graph Notes III.8 and HW 11/15 #3, HW 11/18 #4.
HW:
1. A triangular polyhedron means one with only triangular faces.
1. Use Euler's Formula and the Edge-Region formula ∑R deg(R) = 2q to show that a polyhedron is triangular if and only if it has n vertices, q = 3n−6 edges, and r = 2n−4 vertices. (This numerical condition means (n,r) lies on the upper edge of the Steinitz region, the wedge in the (n,r) plane containing all possible f-vectors.)
2. Find two maximal planar graphs with (n,r) = (6,8), but which are combinatorially inequivalent. Draw polyhedra associated to these graphs.
Hint: One is the edge-graph of a standard polyhedron. The other graph is made from two 3-cycles connected in a non-standard way.
2. Combinatorial types with f-vector (7,7).
Consider the following graph: G is a 5-cycle C5 with consecutive vertices 1,2,3,4,5; and inside the cycle is vertex 6 adjacent to 1,2,3,7; and vertex 7 adjacent to 1,4,5,6.
1. Find a standard polyhedron with (n,r) = (7,7).
2. Show the above graph G is planar and 3-connected with (n,r) = (7,7); but it is not isomorphic to the graph from part (a). Hence G is the edge-graph of a polyhedron combinatorially inequivalent to the one from (a).
3. Draw a sketch of a polyhedron having edge-graph G.
4. Find a third inequivalent graph and polyhedron with (n,r) = (7,7), by modifying the construction of G.
3. Cyclic polyhedron
• For any n ≥ 4, the cyclic polyhedron (usually called the cyclic polytope) P = Cyc(n) is a weird oyster-shape (Ziegler Fig 1.2) which is the convex hull of n vertices: pick any real numbers t1 < ⋯ < tn, and define: vi   =   (ti, ti2, ti3). That is, the vertices are points on the rational normal curve c(t) = (t, t2, t3).
• The convex hull of these vertices is the n-vertex cyclic polyhedron Cyc(n).
• It is known that the faces of Cyc(n) are the triangles with vertices vivjvk, where j = i+1 or k = j+1.
• Here is another picture:
Problems
1. Verify the description of the faces in the two pictures.
2. Determine the number of faces and edges for Cyc(n). (Why was this predictable?)
3. Make a planar drawing of the edge-graph of Cyc(n).
4. Unique polyhedra
1. Prove that any polyhedron with (n,r) = (4,4) is combinatorially equivalent to the tetrahedron.
2. Draw the (combinatorially unique) polyhedron with (n,r) = (5,6); and its dual with (n,r) = (6,5).
5. Convince yourself that all of the above edge-graphs are 3-connected: that is, removing any 2 vertices leaves the graph connected.
6. Work on the second draft of your proof from last week. See the hints below.
Solutions

• 3/28: Balinski's Theorem: Edge-graph of P is 3-connected.
• Notes 3/26−3/28
• Wikipedia. This proof of the Theorem is similar to the one I gave in class.
• I adapted my presentation from Günter Ziegler, Lectures on Polytopes, p. 95.
HW:
1. Can you identify the polyhedron in Dürer's famous picture Melencolia, in terms of our standard polyhedra, their duals, and our construction methods? (Try enlarging for a better view. The shape has a small triangle on top and bottom, and 3+3 non-regular pentagonal sides. It is sort of a triangular version of the dodecahedron.) Hint: The dual is a polyhedron which is fairly easy to visualize.

2. Balinski Proof.
• Balinski's Theorem (for dimension 3): The edge-graph G of a convex 3-dimensional polyhedron P is 3-connected. That is, G−v1−v2, the graph with any two vertices removed, is always a connected graph.
• Case (i): Suppose v1 and v2 lie on a face F of P. Suppose that, for a normal vector a, the plane of F is given by the equation a x = c, so that a x ≤ c for all x ∈ P. The "height" function a x has a maximum value a x = c for x on F, and a minimum value a x = b for x in some "bottom" flat B (a vertex, edge, or face).
Now, any vertex v ∉ B has a lower neighbor w, meaning a w < a v : this is because P contains points lower than v by hypothesis, and P is contained in the cone of v, whose edges are the neighbors of v. Therefore, we can connect v to the bottom B by a strictly decreasing path, which cannot contain v1 or v2 since the path contains at most one point with a x = c. Thus, any two vertices v, v' can be connected to each other in G−v1−v2 by connecting v to some w ∈ B and v' to some w' ∈ B, and connecting w to w' along the edge-graph of B (which is a vertex, an edge, or a cycle).
• Case (ii): Suppose v1 and v2 pass through the interior of P. Then we can take a third vertex v0, so that v0, v1, v2 define a plane, a x = c. By the same reasoning as before, for any vertex v with a v ≤ c, we can connect v by a downward path to the "back flat" B = {x such that a x = min}. Also, for any vertex v with a v ≥ c, there is an upward path to the "front flat" F = {x such that a x = max}. Finally, the middle vertex v0 connects to both F and B, so we can clearly produce the needed paths in G−v1−v2.
Now consider the following polyhedron (with vertex coordinates marked):

1. Let v1 = (½, ½, 32) and v2 = (1,1,1). These lie in the triangular face with vertices v1, v2, and v0 = (1,0,1). Illustrate Case (i) above by computing a normal vector a to this face, and marking all vertices v with their height in the direction a, that is a v. (Hint: You can scale a to any convenient length.) Verify that every vertex in G−v1−v2 can be connected by a decreasing path within G−v1−v2 to the "bottom flat" B (the points x ∈ P where a takes on its minimal value). Show how this connects any two vertices.
2. Now let v1 = (½, ½, 32) and v2 = (1,0,0). Pick another vertex v0 = (0,0,0). Illustrate Case (ii) above by computing a normal vector to the plane containing v0, v1, v2, and marking all v with their a-height. Verify that every v on or below the plane can be connected by a decreasing path to the "back flat" B (the points of minimum a-height); and every v on or above the plane can be connected by an increasing path to the "front flat" F (the points of maximum a-height). Also, v0 can be connected to both B and F. Show how to connect any two vertices in G−v1−v2 by concatenating these paths.
Solutions

1. The dual of a k-gon anti-prism is a k-gon trapezohedron. The pictured solid is a triangular trapezohedron, with the top and bottom vertices truncated. Thus, the solid is the dual of a triangular anti-prism (an octahedron), with small triangular pyramids stacked on top and bottom.
2. Balinski proof
1. Find the normal vector a by taking the cross-product (v1−v0) × (v2−v0), and scaling to clear denominators. The "heights" a v are in green. We consider "up" and "down" relative to the direction a, not the vertical direction.

It is clear that any vertex v ∈ G−v1−v2 can slide downward along edges toward the bottom B, without encountering v1 or v2 (which are at the top). Thus any two such v, v' can be connected by connecting v downward to w ∈ B, horizontally to w' ∈ B, then reversing a downward path back up to v'.
2. Similar to (a).

• 3/31: Augmenting path algorithm
Menger's Theorem: Minimum number of disconnecting points = maximum number of connecting paths
• Notes 3/31
• I adapted my proof from Diestel, Graph Theory, p. 68−71.
• Generalization: independent paths are a special case of flows, and the augmenting path algorithm finds a maximum flow.
HW:
1. Determine the connectivity index κ(G) for the following edge-graphs of the following polyhedra. Also, compare with the minimum vertex-degree δ(G) = min{deg(v) for v ∈ V}. (We always have κ(G) ≤ δ(G), since we can always remove all the neighbors of a vertex to isolate it, disconnecting the graph.)
1. Each of our standard polyhedra from HW 3/19 #1.
2. The k-gonal prism with pyramids stacked on the top and bottom k-gons
3. Two triangular anti-prisms glued top-to-bottom. In the Schlegel diagram below, there are three triangular shells (exterior, intermediate, interior) corresponding to the tops and bottoms of the anti-prisms.
4. Extra Credit: We know by Graph Notes III.9 that any polyhedron graph G (in fact any planar graph) has a vertex of degree at most 5; and G is 3-connected by Balinski's Theorem. Thus:

3 ≤ κ(G) ≤ δ(G) ≤ 5.

Problem: Construct a polyhedron graph with κ(G) = 3 and δ(G) = 5.
Hint for all: To show that κ(G) ≤ k, find k vertices which disconnect G. To show κ(G) ≥ k, find k paths between each pair of vertices. (Do not write all these down, just convince yourself they exist.)
2. Consider the 4 × 4 grid graph G whose vertices are the integer points V = {(i,j) with i,j = 0,1,2,3}; with edges of the form e = (i,j)(i,j+1) or (i,j)(i+1,j) for all i,j.  Let x = (0,1) and y = (3,2), and ℘ = {P1, P2}, the family of two "greedy" paths which connect x and y in the shortest way:

P1 = (0,1)(0,2),(1,2),(2,2),(3,2)   and   P2 = (0,1),(1,1),(2,1),(3,1)(3,2).

These greedy paths block any third independent path, and they are not a maximal family.
1. Apply the Augmenting Path Algorithm to modify the above paths ℘, into a family ℘' of 3 independent xy-paths.
2. Apply the algorithm one more time to find a disconnecting set {v1, v2, v3}.
3. What is the connectivity κ(G)? How can you be sure?
3. Same as the previous for the following example: Let x = (1,1) and y = (0,2), and ℘ = {P1, P2} with:

P1 = (1,1)(2,1),(3,1),(3,0),(2,0)   and   P2 = (1,1),(0,1),(0,2).

Solutions

1. Connectivity index
1. Standard polyhedra: Each polyhedron family is over a k-gon. We compare the connectivity index κ(G) to the minimum vertex degree δ(G) = min{deg(v) for v ∈ V}.  P pyram prism anti-pr bipyr trapezo dodeca icosa κ(G) 3 3 4 4 3 3 5 δ(G) 3 3 4 4 3 3 5
Exception: Bipyr(3) has κ(G) = δ(G) = 3.
2. For P = k-prism with k-pyramids stacked on top and bottom, we have κ(G) = δ(G) = 4 for k ≥ 4, and κ(G) = δ(G) = 3 for k = 3.
3. The 3 vertices of with deg(v) = 6 form a cut-set, and we can find 3 paths between any two vertices, so κ(G) = 3. But δ(G) = 4, so in this case κ(G) < δ(G).
2. Augmenting paths on the 4×4 grid graph G.
1. Below left is one possible augmenting path Q in red, traversing two backward edges of ℘ = {P1, P2}. Erasing the backward edges (below right) unblocks the third xy-path, producing the modified path family ℘' = {P1', P2', P3'}.
2. The red vertices in the picture above right give the cut-set produced in Case (ii) of the Algorithm. For this graph, we have κxy(G) = deg(x) = 3, and the xy-paths use all the edges at x. No more augmenting paths are possible except the 1-point path of x itself, and the cut-set chooses the second vertex on each path, the neighbors of x. (If there do exist augmenting paths, we define vi to be the farthest vertex on Pi reachable by such a path.)
3. The above guarantees that κxy(G) = 3. If we ran the Algorithm for all pairs x,y, it would show that κ(G) = min{κxy(G) for all x,y} = 2. We can see this informally by imagining 2 independent paths between any two vertices, including the corners with deg(v) = 2.

• 4/2: Classifying polyhedra
• Wolfram Mathworld on polyhedral graphs and hexahedra, and Wikipedia on hexahedra. (6-faced polyhedra)
• Numericana on enumerating polyhedra. This chart shows how many combinatorial types correspond to each f-vector (n,r) in the Steinitz region.
• Constructing 3-connected graphs: Diestel Ch. 3.2, p. 68 after Thm 3.2.3.
• Extra reading: Edward Bender, The number of three-dimensional convex polyhedra. This is a difficult counting problem that can be handled by methods similar to the unlabeled trees (but harder). It again shows the tremendous power of generating function methods.
HW: Solutions
1. We apply the construction algorithm described in the problem to produce all possible 5-vertex polyhedral graphs.
1. Starting with the tetrahedron graph Pyr(3) we subdivide one edge to introduce a fifth vertex. (Since all edges are symmetric to each other, it does not matter which edge.) This new vertex is one end of a new edge, and if we want exactly 5 vertices, the other end must be an existing vertex.
2. We cannot create any more vertices (having 5 already), so we can only connect the two existing vertices across the single face which is not a triangle (the outer region in the picture). The result is a maximal planar graph (all regions triangles), so we cannot add any more edges.
See Wolfram Mathworld for drawings of the 2 pentahedral graphs and the 7 hexahedral graphs, and their duals.
2. Mathworld also has the geometric hexahedra. (Note the confusing terminology: the "hexahedral graphs" have 6 vertices, whereas the geometric hexahedra have six faces.) The left and right versions of the chiral hexahedron are shown on Wikipedia and Numerica (the "tetragonal antiwedge").

• 4/4: Properties of polyhedral graphs. Start Rubber-Band Model.
For the next couple of weeks, we will study the proof of Steinitz's Theorem which combines ideas from the graph-theorist Tutte and the physicist Maxwell.
1. Basic formulas for polyhedral graphs with n vertices, q edges, and r regions:
• Vertices have deg(v) ≥ 3; edges adjoin 2 distinct regions; regions have deg(R) ≥ 3.
• Edge-Vertex & Edge-Region:   ∑v deg(v)  =  2q ;  ∑R deg(R)  =  2q.
• Euler: n − q + r  =  2.
Prove the following formulas directly from the above (not by dualizing the corresponding facts about vertices).
1. q ≤ 3r − 6.
2. n ≤ 2r − 4 (one of Steinitz's inequalities).
3. There is some region with deg(R) ≤ 5; that is, every polyhedron has some face which is a triangle, quadrilateral, or pentagon.
2. Potential energy
1. Recall that, given the force F(x) along the x-axis, the potential energy (the amount of work needed to reach a given point x1 from the origin) is the integral:

PE(x1)  =  −0x1F(x) dx .

Find the potential energy for the Hooke's Law force F(x)  =  −x.
2. If we have two Hooke forces pulling toward different centers:

F(x)  =  −(x−a1) − (x−a2),

for constants a1, a2, what is the potential like? It is the sum of two parabolas, so maybe a W-shaped graph? Think again!
3. Show that no matter how many Hooke forces we add, the potential has a unique minimum point x = x0, which is the unique equilibrium point: all the forces cancel, giving F(x0) = 0.
3. Generalize Prob 2 to two dimensions. The vector force field  F(x,y) = −(x,y)  has potential energy given by a line integral

PE(x1,y1)  =  − F(r) dr ,

where r(t) = (x(t), y(t)) is a path from (0,0) to (x1, y1). When this is independent of the choice of path, we say F is a conservative vector field.
1. Compute the potential for the two-dimensional Hooke force field above.
Hint: Use a radial path r(t) = (tx1,ty1) for 0 ≤ t ≤ 1.
2. Extra Credit: Why is this a conservative field?
3. Again show that no matter how many Hooke forces we add, the potential has a unique minimum point which is the unique equilibrium point.
Solutions

• 4/7: Rubber-Band Model.
1. We will find the equilibrium position for the familiar graph:

1. Write appropriate coordinates to record the positions of the mobile vertices v1, while the outer v3, v4, v5 are fixed in convenient positions − not necessarily an equilateral triangle.
2. Write the forces F1, F2 (vector functions depending on the positions of v1, v2) acting on the mobile vertices v1, v2.
3. Solve a system of linear equations to find the equilibrium points.
4. Compute the potential function PE, which represents the work performed against the force when we start with v1, v2 both at (0,0), we move v1 to its given position, then move v2 to its position.
5. Why is it clear that PE has a large positive value whenever v1 or v2 are far from the origin? What does this mean about the critical points of PE?
6. Show that the critical points with ∇PE = (0,...,0) are precisely the equilibrium points of F1,..., F5.
2. Same as #1, but for the chiral hexahedron graph:

Solutions

• 4/9: Rubber-Band Model.
1. Extra Credit: Hand in the answer to HW 4/7 #2. That is, find the equilibrium position for the chiral hexahedron graph:

Assume the outer vertices are in an equilateral triangle: v4 = (12, √32),  v5 = (1,0),   v6 = (0,0). Make your writeup brief, without showing all the calculations. Get exact answers, and also decimal approximations.
Next lecture, I will compare your results to a rubber-band experiment.
Try some other interesting graphs, such as the Platonic graphs. For example, for the octahedron graph, how much smaller is the internal triangle than the external? I would be impressed if you write some software for this.

• 4/11: Finish Rubber-Band Model.
• Example: of the equilibrium computation using incidence matrices (a readable part of Richter-Gebert, p. 138).
• Check out Sam Moore's brilliant rubber-band app!
Controls:
• Click and drag any vertex to move.
• Right click a vertex to toggle whether it is fixed or mobile.
• Add vertex and delete vertex.
• Set edge toggles to & from edge mode, where you click on two vertices to create an edge between them.
• Wikipedia on Laplacian matrix and algebraic connectivity.
HW:
1. Partial Laplacian matrix
• For a graph G = (V,E) with vertices V = {1,...,n}, we denote the position of a vertex by vi = (xi, yi). We designate an external cycle with vertices vk+1,..., vn, and pin them in fixed positions; while we allow the internal vertices v1,..., vk to move to arbitrary positions. An equilibrium position makes the rubber-band forces cancel at each internal vertex:

Fi   =   ∑j ∈ N(i) (vj − vi)   =   (0, 0)     for     i = 1,...,k,

where N(i) means the set of all neighbor vertices of i.
• We now give another way of setting up this linear system of equations. Define a k×k matrix, called the partial graph Laplacian, L = (ℓij), whose entry in row i, column j is:  deg(vi) if i = j, ℓij = −1 if ij ∈ E 0 otherwise.
Let x = (x1,..., xk) and y = (y1,..., yk) be k×1 column-vectors of variables (coordinates of internal vertices). Finally, define b = (b1,..., bk) and c = (c1,..., ck) by:

bi   =   ∑j ∈ XN(i) xj ,           ci   =   −∑j ∈ XN(i) yj ,

the negative sum of the fixed x- and y-coordinates of external neighbors of i; that is, XN(i) means the neighbors j ∈ N(i) with k+1 ≤ j ≤ n.
Problems:
1. Show that v1,..., vk defines an equilibrium position exactly when:

L x   =   b     and     L y   =   c,

where denotes matrix multiplication.
2. Consider the graphs in HW 4/7 #1,2. Use Wolfram Alpha to do Gaussian elimination (row-reduction) on the matrix L, augmented by the constant vectors b and c, and find the equilibrium position. (Command: row reduce {{1,2,3},{4,5,6}} for the 2×3 matrix with rows (1,2,3) and (4,5,6).)
3. Extra Credit: Same as (b) for the icosahedron graph.
2. Full Laplacian matrix
• Continuing with the graph G with n vertices from Prob 1, the adjacency matrix is the n×n matrix A = (aij) whose entry n row i, column j is aij = 1 if ij ∈ E, and aij = 0 otherwise. This is an obvious book-keeping device for the edges and vertices of G: what is amazing is that considering it as a matrix with eigenvalues, etc., gives subtle information about the graph.
• The (full or ordinary) Laplacian of a graph G is the matrix L = D − A, where D is the diagonal matrix with deg(i) in the (i,i) position (and 0 elsewhere). (Thus, the full Laplacian L = (ℓij) has the same entries as in Prob 1, except that it is for all n vertices, not just the mobile vertices 1,...,k.)
• The Laplacian always has an eigenvalue λ = 0: that is the n×1 column vector u1 = (1,...,1) satisfies L u1 = 0 u1 = (0,...,0). Furthermore, it is known that L is diagonalizable with n non-negative eigenvalues 0 = λ1 ≤ λ2 ≤ ⋯ ≤ λn.
• The second eigenvalue λ2 is known as the algebraic connectivity. We have λ2 ≥ 1 if and only if G is connected; and in general, it gives a lower bound for the usual index of connectivity: λ2 ≤ κ(G). (Recall that κ(G) is the minimum number of vertices whose removal disconnect the graph, and this can be computed by the Augmenting Path Algorithm applied to all pairs of vertices.) There are many other results in spectral graph theory, relating the eigenvalues (or spectrum) of L with graph-theory properties of G.
Problems:
1. Let G be the 5-vertex graph in HW 4/7 #1. Write its 5×5 adjacency matrix A and its 5×5 (full) Laplacian L = D − A.
2. For the same G, find the spectrum (set of eigenvalues) of L on Wolfram Alpha. (Example: eigenvalues {{1,2},{3,4}} gives the spectrum of matrix with rows {1,2} and {3,4}.) Verify that λ2 ≤ κ(G) for this graph.
3. Now let G be a general graph, and let u1 = (1,...,1) as above. Prove that L u1 = 0 u1 = (0,...,0).
4. Extra Credit: Prove that if G is not connected, then λ2 = 0. Hint: Find another eigenvector u2 with L u2 = (0,...,0).
3. Extra Credit: Make some rubber-band graphs to hook onto the exterior triangle on my board. For example, make the icosahedron: 12−3 = 9 internal vertices (little rings) and 30−3 = 27 rubber-band edges. It would be especially interesting to compare the experiment with the exact analytic solution computed above.
Practical considerations.
• You have to break in the rubber bands with a few dozen stretches to make their forces uniform.
• To get an accurate model of the Hooke forces, you have to use smaller rubber-bands for the innermost edges, since their natural length is not zero, and they would go slack when their ends are too close.
• In such an arrangement, are there the same Hooke forces from all the different kinds of rubber bands? You might have to use thicker bands, or double up, to make the forces uniform...
4. Proof of Tutte's Theorem.
• In class, we proved the following lemmas, which are part of the proof that an equilibrium position forms a good drawing of any 3-connected planar G, decomposing the exterior into non-overlapping convex polygons.
• We assume an equilibrium position with mobile internal vertex positions v1,..., vk and external vertices vk+1,..., vn forming a fixed convex polygon.
• Lemma 1: Each internal vertex vi is the centroid (vector average) of its neighboring vertices: vi   =   1nj∈N(i) vj.
• Lemma 2: No vertex can have all its neighbors on the same line ℓ.
We proved this by defining a Y-graph as the union of three independent paths in G, joined at a single common endpoint. We showed that if all the neighbors of v are on a line ℓ, then we can construct three Y-graphs, disjoint except for their common leaf vertices a,b,c: one Y-graph on ℓ, one above ℓ, one below ℓ. But this is a contradiction, since these Y-graphs form a subdivision of the complete bipartite graph K3,3, which cannot exist in a planar G by Kuratowski's Theorem.
Problems:
1. For the equilibrium positions found in HW 4/7 #1, 2 and in Prob 1 above, check that each internal vertex vi is the centroid of its neighbors.
2. Extra Credit: Find a counter-example to Lemma 2 if G is allowed to be only 2-connected: that is, find a 2-connected graph whose equilibrium position does have an internal vertex with all neighbors on a single line.
3. Extra Credit: In the proof of Lemma 2, we assumed that all neighbors of the internal vertex vi lay on the line ℓ. One case we skipped is if some of these neighbors of vi are fixed external vertices vj, v'j: these must be of maximum or minimum height with respect to ℓ, so it would not be possible to construct three Y-graphs as before, nullifying the previous contradiction of Kuratowski's Theorem. Nevertheless, why is this case impossible?
Solutions

1. Partial Laplacian matrix to find equilibrium positions
1. From the definiton of matrix multiplication, we immediately see the equivalence of the matrix equation and the linear system for equilibrium position.
2. For the chiral hexahedron graph (6 vertices, with external vertices an equilateral triangle), we compute x-coordinates:

Then y-coordinates:

Thus:

(x1, y1)  =  (13, 12√3 ),     (x2, y2)  =  (1324, 14√3 ),     (x3, y3)  =  (724, 14√3 ).

This matches the experimental rubber-band model quite well.
2. Full Laplacian
1. The adjacency matrix A and the (full) Laplacian L, for the 5-vertex graph in HW 4/7 #1:
 0 1 1 1 1 1 0 0 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 0
 4 −1 −1 −1 −1 −1 3 0 −1 −1 −1 0 3 −1 −1 −1 −1 −1 4 −1 −1 −1 −1 −1 4
2. Wolfram Alpha gives the eigenvalues of L as:

Note that they index the eigenvalues from largest to smallest, so that they write λ4 instead of our notation λ2. That is, the second smallest eigenvalue is: λ2 = 3. This is equal to κ(G), the index of connectivity; and also equal to δ(G), the smallest deg(v) of G.

• 4/14: Begin Maxwell's Lifting Theorem
1. Consider the simplest 3-connected planar graph, G = Pyr(3) = K4, the tetrahedron graph, with equilibrium position:

1. Find the vectors q1, q2, q3 for the 3 internal regions, starting with q1 = (0,0,0).
2. Find q3 in two ways, by starting with q1 = (0,0,0) and following both paths of neighboring regions: verify that the same q3 is produced. Can you explain why? (Hint: It has to do with the special positions of vi.)
3. What is the effect of raising vi to (vi,1) before taking cross products? Why do we get downward-pointing qi's? Try to picture the geometry involved. Hint: Review the right-hand rule for the cross-product.
4. Find h1,..., h4, the heights of all vertices. Again, compute h1 in three ways, corresponding to all 3 regions containing v 1: check that you get the same answer each time.
5. Sketch the polyhedron with corners (vi, hi).
Solutions

• 4/16: Maxwell's Lifting Theorem
• Notes
• Richter-Gebert pp. 133−139. Lemmas 13.1.1−13.1.4 correspond to our Lemmas 1,2,3.
HW:
1. Let G be the chiral hexahedron graph from HW 4/7 #2 and HW 4/11 #1b.

1. For the external vertices, instead of the equilateral triangle coordinates, we choose integer coordinates: v4 = (1,1), v5 = (2,0), v6 = (0,0). Work out the locations of v1, v2, v3 using the partial Laplacian matrix from HW 4/11.
2. Compute Maxwell's qj vectors for the regions using the recursive formula, starting from the triangle R1 with vertices v1v4v6.
3. Determine the height hi = qj (vi,1) of each vertex, producing lifted vertices v'i = (vi, hi) of a convex polyhedron P, the convex hull of v'1,..., v'6.
4. Write all the face-boundaries of P in the form q'j v ≥ dj, where q'j is a normal vector, v = (x,y,z) is a vector variable, and dj is a constant. This specifies P as the vectors of height ≥ dj, with respect to the direction q'j, as in HW 3/21.
Note: q'j is different from qj, though closely related. This corrects a mistake in the Richter-Gebert notes.
Hint: Let qj = (aj, bj, cj). The face above Rj is defined as the set of points v = (x,y,z) with (x,y) ∈ Rj, and height given by z  =  qj (x,y,1), i.e.:

z  =  ajx + bjy + cj .

Rewrite this equation in vector dot-product form q'j v = cj, for an appropriate vector q'j ; then check that the other vertices of P have height  ≥ cj.
5. Show that P is convex, by checking that all P-vertices v'i not adjoining region Rj have q'j u > dj.
2. Prove Lemma 2: If a vertex v is a corner of two regions R,S, then the height hv is well-defined:

hv  =  qR (v,1)  =  qS (v,1)

Hint: First explain why it is enough to do this in case R,S are neighbors, and share an edge uv. Now calculate the height hv with respect to R and to S.
Solutions (revised)

• 4/18: Proof of Maxwell's Lifting Theorem
• Notes
• Richter-Gebert pp. 133−139.
• Review HW 3/21 on planes and cross-products
• Marvelous: George Hart's polyhedron gallery
• First, you need to install the VRML plugin for your browser.
• Table of contents with hundreds of polyhedra, which you can rotate (Examine mode), see close or far (Fly mode), even view from the interior (fly in past the surface).
• Canonical form of a polyhedron is the unique most well-proportioned solid for a given combinatorial type. It is defined by having all edges tangent to a given sphere, and the points of tangency having their centroid at the origin. One really neat feature is that the dual polyhedron has the same points of tangency, with each dual edge perpendicular to the original edge.
HW:
1. Equivalent versions of Lemma 3 from the Notes:
• For each edge uv separating two regions S,R in G, the planes in their lifting form a surface (a lower surface of P) which is concave up (like an open book face up rather than face down).
• For any point w inside the left-hand region S, the R-height is less than the S-height.
• {(w,1), (v,1), (u,1)} is a left-handed coordinate system.
• det((w,1),(v,1), (u,1)) < 0, where ((w,1),(v,1), (u,1)) means the 3×3 matrix with row vectors (w,1),(v,1), (u,1).
In this problem, we prove the last, most algebraic statement.
1. For a plane vector a = (a1,a2) ∈ R2, show that a = (−a2, a1) is 90° counter-clockwise from a. (We make the standard assumption that the y-axis is 90° counter-clockwise from the x-axis.)
2. A right-handed coordinate system in the plane is a pair of non-parallel vectors {a,b} with b counter-clockwise from a. This means that a and b are on the same side of a, or algebraically, a b > 0.
Problem: Prove that {a,b} is a right-handed coordinate system if and only if det(a,b) > 0, where (a,b) is the 2×2 matrix with row vectors a,b.
3. A right-handed coordinate system in 3-dimensional space R3 is a triple {a,b,c} of independent vectors such that the cross-product a×b and c are on the same side of the plane spanned by {a,b}: that is, (a×b) c > 0.
Problem: Prove that {a,b,c} is a right-handed coordinate system if and only if det(a,b,c) > 0.
4. Let S,R,u,v be as described above. Prove the crucial fact for Lemma 3: If w is to the left of the vector from u to v (i.e. on the same side as S), then {(w,1),(v,1),(u,1)} is a left-handed coordinate system (i.e. not right-handed, with det < 0).
2. Finishing HW 4/16 #1e, find the equation of the top surface of the chiral hexahedron (i.e. the lid). Hint: Use HW 3/21 #2.
Solutions revised

• 4/21: Final Review 1: Finite Difference Calculus.
Notes:
• We can view a sequence (an)n≥0 as a function a : ℕ → ℝ, since to each input n ∈ ℕ (a discrete variable), it assigns an output a(n) = an. 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 an.
• The derivative operation D = ddx for a(x):

Da(x)   =   a'(x)   =   limh→0 (a(x+h) − a(x))h   =   limh→0 (a(x) − a(x−h))h

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

Δ+an  =   (an+1−an)1   =   an+1 − an.

Δan   =   (an−an−1)1   =   an − an−1.

By convention, we always take a−n = 0 for a negative index −n, so Δa0  =  a0 − a−1  =  a0.
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=0x a(t) dt is analogous to the summation operation:

Σan   =   ∑i=0n   ai.

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

Δ(Σan) = an       and       Σ(Δan) = an .

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:

(an)n≥0     ↔ops     f(x)  =  ∑n≥0 anxn.

Determine the effect of the operations Δ, Δ+, Σ on the generating function f(x). That is, if ∑n≥0 anxn = f(x), then write ∑n≥0 Δan xn in terms of f(x), and the same for Δ+an, Σan .   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 Δ+an  =  an, by elementary means (just write out what it means), and also by generating functions. Assume the initial value a0 is an arbitrary constant.
Compare to the solutions of the corresponding differential equation a'(x) = a(x).
5. Show that

Δ+Δan   =   ΔΔ+an   =   an+1 + an−1 − 2an   for n ≥ 1.

We must be careful about n = 0: we get Δ+Δa0 = a1 − 2a0 , whereas ΔΔ+a0 = a1 − a0 .
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:  Δ+Δan  =  −an for n ≥ 1, using generating functions. We do not assume any recurrence for n = 0; rather, the initial values a0, a1 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 an  =  nk  =  n(n−1)⋯(n−k+1). (Also n0 = 1.) Find a simple formula for the generating function f(x)  =  ∑n≥0 nk xn. Hint: Start with the cases k = 1 and k = 2. Use Wilf's Rules.
8. Prove by induction that  Δ(nk) = 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 nk = k Σ(n−1)k−1, and iterating, we get nk = k! Σkcn, where Σk means perform the Σ operation k times, and cn = (n−k)0 = 1 for n ≥ k, and cn = 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 nk xn.
10. Find a transformation to prove the formula:

nk   =   ∑i=0k {k | i}n i ,

where {k | i} is a Stirling partition number from the Twelvefold Way. Hint: The number nk 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 i , 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 wn be the number of allowed words with n letters. For example, w3 = 5 counts the words:

aba, abb, bab, bba, bbb.

Use generating functions to determine wn 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 P1, P2 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.
Solution:
1. Words in a,b with no aa's
• Step 1: To get a recursive choice algorithm, delete the the letters up to and including the first b, if any:

Any word w     ⇔     (w = ∅)  or  (w = a)  or  (w = bw' for word w')  or  (w = abw' for word w')

This translates into an equation involving the generating function f(x)  =  ∑n≥0 wnxn :

f(x)   =   1  +  x  +  x f(x)  +  x2 f(x).

Solving gives f(x)  =  (1+x)(1−x−x2) .
• Step 2: To obtain information from the above formula about the coefficients wn.
1. We get a recursive formula by clearing denominators and multiplying out:

(1 − x − x2) ∑n≥0 wnxn   =   ∑n≥0 wnxn  −  ∑n≥0 wnxn+1  −  ∑n≥0 wnxn+2   =   1 + x .

Collecting the coefficient of xn gives:   wn − wn−1 − wn−2  =  0 for n ≥ 2, or wn  =  wn−1 − wn−2 for n ≥ 2, which is the same as the Fibonacci recurrence. The only difference is the initial value: w0 = 1, w1 = 2. In fact, it is clear that wn = Fn+2 for n ≥ 0.
2. To obtain an exact formula, we must write f(x) as a sum of standard functions with known power series. This form will have the same vertical and horizontal asymptotes as f(x), namely the horizontal asymptote y = 0 and the simple vertical asymptotes given by the roots of the denominator: α = ½(√5−1) and β = − ½(√5+1). In fact, 1 − x − x2  =  (1 − x/α) (1 − x/β), and we get:

f(x)   =   A(1 − x/α)  +  B(1 − x/β)

where:

A  =  limx→α (1 − x/α) f(x)  =  limx→α (1 − x/α)(1+x)(1 − x/α)(1 − x/β)  =  (1+α)(1 − α/β)  =  (5+3√5)10 ,

and similarly β  =  (5−3√5)10 . Expanding the two geometric series and taking the coefficient of xn gives the exact formula:  wn  =  A/αn + B/βn.
3. To get an asymptotic formula, we extract the contribution of the vertical asymptote closest to the the origin, namely x = α. That is, wn  ≈  A/αn. Since |1/β| < 1 < |1/α|, the second term of the exact formula is a tiny correction.
2. Hinged polyhedron.
1. Given a planar graph G with an internal region R, we can invert R, flipping all the edges and vertices outside R to the inside. (Geometrically, if we draw G so that R is a unit circle, we flip each point outside R to the reciprocal of its radius.) In the resulting picture, R becomes the outside region.
Now, given the graphs of P1, P2, each with a specified edge, we can do inversion so that each edge is on the exterior of the drawing. Now we can join these edges vertex-to-vertex in the plane, giving a planar drawing of the edge-graph of P.
2. The above graph could not be the edge-graph of a convex polyhedron, because it is not 3-connected: removing the 2 vertices of the join-edge clearly disconnects the graph. But Steinitz's Theorem states that the edge-graph of any convex polyhedron is 3-connected.
3. Can there be a convex polyhedron with n = 100 vertices and q = 200 edges? One simple test is whether q exceeds the number of edges in a maximal planar graph: 200 = q ≤ 3n−6 = 294, which does not disqualify n,q.
Steinitz's Lemma gives the real answer: a simple numerical criterion for the f-vectors of all convex polyhedra. Euler's Formula gives r = 2−n+q = 102, which satisfies:

100 = n  ≤  2r−4 = 200           and           102 = r  ≤  2n−4 = 196.

Thus, there must exist a convex polyhedron with f-vector (n,q,r) = (100, 200, 102)

• 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
• 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
• 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−{v1,v2}.
• 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.

• Notes to supplement the textbooks.

• Old Notes

• Math 481: Review.

• Sigma Summation Notation: Review.

• Notes 1/8 - 1/13: The Twelvefold Way and other sequences.

• Notes 1/8: Deletion Transform
• To prove an identity between algebraic expressions α = β, consider the left side as counting all objects in set A, and the right side as counting all objects in set B: i.e. α = |A| and β = |B|.
Now find a reversible transformation which pairs each object in A with one object in B (formally, define an invertible funciton φ : A → B). This proves |A| = |B|, hence α = β.
• To prove the Pascal's Triangle recurrence formula:
(n | k)  =  (n−1 | k−1) + (n−1 | k),
use the Deletion Transform. Here A is the set of all sets S ⊂ {1,...,n} with size |S| = k, and B is the set of all sets S' ⊂ {1,...,n−1} with size |S'| = k−1 or k. The transform takes each S to the same set with n removed (if it is present):   S' = S\{n}. If n ∈ S, this means |S'| = k−1 ; otherwise S' = S and |S'| = k. This is clearly reversible: given S', we define S = S'∪{n} if |S'| = k−1, and S = S' if |S'| = k.
• Here is a table of the Deletion Transform in the case:
(6 | 3)  =  (5 | 2) + (5 |3).
The top row shows the objects counted by the left side, namely 3-element subsets of [6]. The bottom two rows show the corresponding transformed objects, which are counted by (5 | 2) and (5 | 3).

 S {1,2,3} {1,2,4} {1,2,5} {1,2,6} {1,3,4} {1,3,5} {1,3,6} {1,4,5} {1,4,6} {1,5,6} {2,3,4} {2,3,5} {2,3,6} {2,4,5} {2,4,6} {2,5,6} {3,4,5} {3,4,6} {3,5,6} {4,5,6} S' {1,2} {1,3} {1,4} {1,5} {2,3} {2,4} {2,5} {3,4} {3,5} {4,5} S' {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}

• Notes 1/10: Number partitions. Entry #10 of the Twelvefold Way counts  partitions: arrangements of k identical balls into n exchangeable bins, with the answer denoted by p≤n(k). Since the balls are identical, we only record how many in each bin; and since the bins can be rearranged, we always put the fullest bin first, then the second-fullest bin, etc. For example, the arrangement of balls •••|•|• is denoted (3,1,1), and p≤3(5) = 5 counts the partitions (5,0,0), (4,1,0), (3,2,0), (3,1,1), (2,2,1).

• Notes 1/13: Stirling cycle numbers
• A permutation is a way of switching around n objects (usually the numbers [n] = {1,..., n}). We can formalize this as a bijective function σ : [n]→[n], meaning each number i is moved to the position j = σ(i). We can write a permutation in two-line notation, for example:
which means σ(1) = 2, σ(2) = 4, σ(3) = 6,... That is, 1 gets moved to the place of 2, and 2 gets moved to the place of 4, etc.
• An alternative way to write σ is in cycle notation: σ = (124)(36)(5) means σ moves 1→2→4→1 and 3→6→3 and 5→5. Cycle notation is not unique: we could equally well wirte σ = (63)(5)(241). There are n! possible permutations (which can be considered as Entry #2 of the Twelvefold Way with k = n).
• The Stirling cycle number [n | k] is the number of permutations of [n] having k cycles. For example, the above permutation σ of [6] has 3 cycles (namely (124) and (36) and (5)), so σ contributes to the cycle number [6 | 3].
• The transformation which proves the recurrence [n | k] = [n–1 | k–1] + (n–1) [n–1 | k] is defined as follows. The permutation σ contains n in one of its cycles. In case (n) is a cycle by itself, drop this cycle to get a permutation τ of type [n–1 | k–1]. Otherwise, remove n from its cycle, leaving a shorter cycle in a permutation τ of type  [n–1 | k]. However, to be able to reconstruct σ, we must also record one more piece of data, the value j = σ(n).

In the first case, the output of the transformation is a permutation τ of type  [n–1 | k–1], which can be restored to σ by adding the cycle (n). In the second case, the output is a pair (τ, j), where τ is of type [n–1 | k] and 1 ≤  j ≤  n–1, which can be restored to σ by enlarging the cycle of τ which contains j by inserting n before j. For example, the above σ = (124)(36)(5) would be transformed to the pair (τ, j) where τ = (124)(3)(5) and j = σ(6) = 3. The reverse transformation inserts 6 before j = 3, giving (124)(63)(5), which is another expression for σ.

• Notes 1/15:   Method of Generating Functions Review ([HHM] Ch 2.6).
Goal:   Get a numerical answer to a counting problem a = |A|, where A is a combinatorially interesting class of objects.
Step 0.   Generalize the problem by seeing a as one of a sequence of similar numbers a0, a1, a2, .... 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)   =   a0 + a1x + a2x2 + ....   =   ∑k≥0 ak xk .

This is a polynomial if the sequence {ak} is finite, or a Taylor series if the sequence is infinite.
Use combinatorial properties of the sequence {ak} = {a0, a1, a2,...} to get a simple formula for f(x).
• The Product Principle for the entire sequence {ak} can lead to a product formula for f(x). The Product Principle says that choosing an object is equivalent to making a sequence of independent basic choices. Given such a choice algorithm, translate the logic of repeated choices into the algebraic language of variables and operations:  Logic choose an objectof any size k ≥ 0 ⇔ basic choiceadding size m or and Algebra f(x) = ∑k≥0 akxk = xm + ×
This is most often used in choosing certain sets or multi-sets, which is equivalent to choosing the number of each kind, with restrictions; and k is the total number of elements.
• If we can find f(x) in terms of any known Taylor series, we can replace the series by its function.
• A recurrence for ak leads to an equation involving f(x), which can be solved to give an explicit formula for f(x).
Step 2.   Given f(x), use algebra and calculus to expand it as a power series, thereby evaluating the coefficients ak.
• Multiply out by brute force, using Wolfram Alpha or a similar algebra computation engine.
• Taylor's formula: ak = f (k)(0) / k! , where f (k)(0) means the kth derivative of f(x) evaluated at x = 0.
This is valid for all functions, but it gives useful results only for especially simple functions like f(x) = ex, sin(x), or (1 ± x)n for any real number n.
• Try to write f(x) in terms of functions with known polynomial expansions or Taylor series.
Partial fraction decomposition writes a rational function in terms of geometric series.
Known series: Used by substituting z = an expression in x, such as z = x2.
• Geometric series:  1(1−z)  =  1 + z + z2 + ...  =  ∑k≥0 zk .
• Binomial theorem:  (1+z)n  =  ∑ i=0n (n | k) zk , where (n | k) = nk / k! is a binomial coefficient.
• Binomial with negative power:  (1−z)−n  =  1/(1−z)n  =  ∑k≥0 ((n | k)) zk , where ((n | k)) = (n+k−1 | k) = (n+k−1 | n−1) is a multi-choose number.
• Exponential function:  exp(z)  =  ez  =  ∑n≥0 znn!
• Logarithm:  log 1(1−z)  =  − log(1−z)  =  ∑n≥1 znn

• Notes 1/17: Machinery of generating functions for the Fibonacci sequence.

• Notes 1/24−1/27: Formal power series R[[x]]
• We regard a power series like f(x) = a0 + a1x + a2x2 + ... not as a function, but just as a suggestive notation for the sequence (a0, a1, a2,...), and we write the dictionary correspondence:
f(x) = ∑n≥0 anxn   ↔ops   {an}n≥0 .
Wilf's notation "ops" stands for "ordinary power series".
• Another useful notation is the operation which picks out the xn coefficient of a power series f(x) = ∑n≥0 anxn. We write this operation as:
[xn] f(x)  =  an .
For example, for f(x) = (1+x)4, we have: [x2] f(x)  =  [x2] (1+x)4  =  6, since (1+x)4  =  1 + 4x + 6x2 + 4x3 + x4. More generally, [xn] (1+x)m = (m | n), a binomial coefficient, if n ≤ m; and [xn] (1+x)m  =  0 for n > m.
• Since a formal power series is really nothing but a sequence of coefficients, we can take such a series with any coefficients at all, regardless of convergence. For example:
f(x)  =  x + 22x2 + 33x3 + 44x4 + ...  =  ∑n≥0 nnxn
is a valid formal power series, but the sum diverges to infinity for any value x ≠ 0, so it does not give any kind of function. It is meaningless to substitute any x-value into f(x), other than f(0) = 0.
• We define R[[x]] to be the set of all formal power-series with real-number coefficients, in analogy with R[x], the set of all polynomial functions which you learned about in Math 310. That is, we think of power series as infinite polynomials.
• Polynomial and other elementary functions have Taylor series, and thus correspond to elements in R[[x]]. Also, many series R[[x]] are convergent Taylor series which define new analytic functions without common names. However, as we saw above, there are many series in R[[x]] which diverge for all x ≠ 0, and do not define functions.
• Although formal power series do not necessarily define functions, we can use the same algebraic rules to add and multiply them: if f(x) = ∑n≥0 anxn and g(x) = ∑n≥0 bnxn, then we define the sum and product as the series:
f(x) + g(x)   =   ∑n≥0 (an+bn) xn           and           f(x)g(x)   =   ∑n≥0 (i=0naibn−i) xn.
In Wilf's notation: if f(x)  ↔ops  {an}n≥0  and g(x)  ↔ops  {bn}n≥0 , then:
f(x) + g(x)   ↔ops   {an + bn}n≥0           and           f(x)g(x)   ↔ops   {i=0naibn−i}n≥0 .
• Lemma: A series f(x) = ∑n≥0 anxnR[[x]] has reciprocal g(x) ∈ R[[x]] with f(x) g(x) = 1, if and only if a0 ≠ 0.
Proof: (⇒) We can define the coefficients of the reciprocal recursively starting with b0 = 1a0 :
bn = − 1a0 i=1naibn−i .
• We can also define the formal derivative of any f(x) = ∑n≥0 anxnR[[x]] as follows:
f '(x)   =   ddx f(x)   =   ∑n≥1 n an xn−1   =   ∑n≥0 (n+1}an+1 xn.
Again, this definition is valid whether or not f(x) converges to give a function. All the usual rules for differentiating functions also hold for power series (though this requires a bit of proof).
In Wilf's notation:  if f(x)  ↔ops  {an}n≥0  then:
Df(x) = f '(x)   ↔ops   {(n+1)an+1}n≥0
• The operation xD = x ddx takes the derivative of f(x), then multiplies by x. Its effect on f(x)  ↔ops  {an} is especially nice:
xD f(x) = x f '(x)  ↔ops  {nan}.
• Rules 1−5 in [W] pp 33−38 give other correspondences between operations on generating functions f(x) and operations on their coefficient sequences {an}.
For example, Rule 2, p 35, deals with operations like (xD)2, which means to do xD twice. For a polynomial like P(z) = z2 − 5z + 3, the operation P(xD) means:

P(xD) f(x)  =  (xD)2 f(x) − 5 xD f(x) + 3 f(x)

=  x ddx(x ddx f(x)) − 5x ddx f(x) + 3 f(x) .

According to Rule 2, this means, if f(x)  ↔ops  {an}, then:
P(xD) f(x)  ↔ops  { (n2 − 5n + 3)an }.

• Notes 2/3: Cards, Decks, and Hands; the Exponential Formula.
1. An exponential family is a class of labeled objects, each having n "vertices" or "slots" which are labeled 1,2,...,n.
• We start with a set P of pictures, each p ∈ P having a weight, i.e. some number i of "vertices" or "slots".
• A card is a pair C = (S,p), where p is a picture, and S is a set of i numbers labeling the i slots of p. The weight of a card is its number of slots: wt(C) = i. We say a card is standard if its label set is [i] = {1,...,i}.
• The deck D of the family is a set of standard cards, C = ([i],p), one for each picture. We let di be the number of pictures of weight i, with exponential generating function d(x)   =   ∑n≥0 di xii! .
• A hand is a set of cards H = {C1,..., Ck} for any k, with combined label set [n] = {1,2,...,n}, where n = wt(C1) + ⋯ + wt(Ck) . That is, Cj = (Sj, pj}, with a disjoint union:

S1 ∪ ⋯ ∪ Sk = [n].

The weight of hand is the total weight of its cards: wt(H) = n = wt(C1) + ⋯ + wt(Ck).
• We will be interested in the enumeration sequence:

hn = #{hands H with wt(H) = n}

and its exponential generating function: h(x)   =   ∑n≥0 hn xnn! .
2. The toy example of labeled coolers is a simple exponential family.
• We fill a cooler with cans of pop: either single cans of Coke, or 2-packs of Pepsi; and we label the cans in the order we intend to drink them. The cans and 2-packs are unordered (exchangeable), and so are the 2 Pepsis within each 2-pack. We want to determine hn, the number of ways to choose a labeled cooler with n cans.
• For example, h4 = 10 counts the following labeled coolers:

 ℂ ℂ ℂ ℂ 1 2 3 4

 ℂ ℂ ℙℙ 1 2 34
 ℂ ℂ ℙℙ 1 3 24
 ℂ ℂ ℙℙ 1 4 23
 ℂ ℂ ℙℙ 2 3 14
 ℂ ℂ ℙℙ 2 4 13
 ℂ ℂ ℙℙ 3 4 12

 ℙℙ ℙℙ 12 34
 ℙℙ ℙℙ 13 24
 ℙℙ ℙℙ 14 23

• In this case there are two pictures, a single can of Coke and a 2-pack of Pepsi:  P = {ℂ, ℙℙ}. The deck D = {C1 , C2} has two standard cards:
C1  =  ({1},ℂ)  =    ℂ 1
C2  =  ({1,2},ℙℙ)  =    ℙℙ 12
A hand is the same thing as a labeled cooler.
3. The Exponential Formula: For any exponential family, the hand-enumerator series h(x) is equal to the exponential of the deck-enumerator series d(x):

h(x)  =  exp d(x)  =  ed(x)

We illustrate this formula and its proof for the toy example.
• Since the deck has only two cards, its exponential generating function is:  d(x)  =  1(x) + 1(x22!).
• To enumerate the hands (labeled coolers), we first consider those with n cans of ℂ only: there is just 1 such, giving the exponential generating function ∑n≥0 1(xnn!) = ex.
• Next, let bn be the number of distinct labeled coolers with n = 2m cans of ℙ only: that is, m 2-packs ℙℙ. The number of ways to split up the label set [n] into m pairs is: (n | 2) (n−2 | 2) ⋯ (2 | 2)   =   (2m)!(2!)m. . However, the 2-packs are exchangeable: re-ordering them in any of the m! possible ways counts as the same labeled cooler, so we must divide by m! to find the number of distinct coolers:

bn   =   b2m   =   n!m!(2!)m ,

giving the exponential generating function:

m≥0 b2m(x2m(2m)!)   =   ∑m≥0 (2m)!m!(2!)m (x2m(2m)!)

=   ∑m≥0 1m! (x22!)m   =   exp(x22!)   =   ex2 / 2!.

• Now, to get a cooler with n cans, combined from i cans of ℂ and n − i cans of ℙ, we must choose a set of i labels S ⊂ [n] for the ℂ 's, which completely determines the ℂ-labeling; then distribute the remaining n − i labels among the ℙ 's. That is, the number of coolers is:

hn   =   ∑i=0n   (n | i) (1) bn−i .

This is precisely the exponential convolution formula, so the hand-enumerator series must be the product of the enumerator series of the ℂ-only and the ℙ-only coolers, which we determined above. That is:

h(x)   =   ∑n≥0 hnxnn! .   =   ex ex2/2!   =   exp(x + x22!)   =   exp d(x).

• Notes 2/5: Examples of exponential families
• Exponential family of set partitions
• Pictures: one picture of each weight n, depicting n unmarked balls:   P = { • , •• , ••• , ... }.
• Cards represent sets: C = (S,p), where |S| = n and p = n balls, just represents the set S.
• Hands represent set partitions, so that the hand-counting sequence is identical to the Bell numbers: hn = Bn. (See HW 1/31 #2.)
• The deck contains one card of each weight: dn = 1 for all n ≥ 1, with d0 = 0 as always.
• The exponential formula relates the hand enumerator h(x)  =  B(x)  =  ∑n≥0 Bn xnn! to the deck enumerator d(x)  =  ∑n≥1 (1) xnn!  =  ex − 1:

B(x)   =   ed(x)   =   eex−1   =   exp(ex − 1).

We got this formula previously from a recurrence in HW 1/31 #2.
• Exponential family of graphs.
• Recall that a graph is defined by the data G = (V,E), where V = {1,...,n} is the set of vertices, and E is a the set of edges, which are unordered pairs of vertices e = ij for some i,j ∈ V. A graph is connected if there are paths along edges from any vertex to any other.
• Since the number of possible edges is (n | 2), and each possible edge can be on or off, the number of possible graphs on n vertices is gn = 2(n | 2). Let cn be the number of possible connected graphs. For example, trees are connected, so cn > nn−2, which is the number of trees on n vertices. Still, cn is quite a mysterious number: there is no known explicit formula, and it is not at all clear how to get a recurrence for it.
• In order to find cn (or at least its generating function), we define the exponential family of graphs. The pictures of this family are all connected graphs:

P = { K = (V,E), where V = [i] for some i ≥ 1, and K is a connected graph }.

• A card is a pair C = (S, K), where S is a set of natural number labels, and K is a connected graph with standard labels [i]. The labels in S substitute for the standard vertex-labels in K, by means of a spreading map (the unique order-preserving bijection [i] → S). For example:

C = ( S = {2,5,6}, K = )

represents the graph K' with vertex set S = {2,5,6} substituted for the standard labels {1,2,3} by means of the spreading map: 1 ↦ 2,   2 ↦ 5,   3 ↦ 6.

C         K' =

• A hand H is a set of cards with total label set [n]. Then H naturally represents the graph G with vertex set [n] whose connected components are given by the cards.
For example, the graph G = (V,E) with V = [6], E = {14, 26, 56}:

G   =

is represented by the hand H = {C1, C2, C3}, where C1 = {{3},),   C2 = ({1,4}, ),   C3 = {{2,5,6}, }.
• The deck in this case is just the set of pictures with the standard labels: i.e., it is practically the same thing as the set of pictures, and the deck-counting numbers are dn = cn. Also the number of hands is the same as the number of all graphs: hn = gn = 2(n | 2).
• The point is to apply the Exponential Formula to compute the exponential generating function of {cn}n≥1 from that of the known sequence {gn}n≥0. Letting c(x)   =   ∑n≥0 cn xnn!  and  g(x)   =   ∑n≥0 gn xnn!, and applying the Exponential Formula:

g(x)  =  ec(x)     ⇒     c(x)  =  log g(x)  =  log ∑n≥0 2(n | 2) xnn! .

(Recall that we always use log to mean the natural logarithm.)

• 2/7: Quiz 13 Solutions: Exponential family of directed cycles (equivalent to permutations).

• Notes 2/7: Proof of the Exponential Formula and the Labeled Product Principle. We will build up an exponential family in four steps, analyzing the generating function at each step.
1. Labeled product of two decks.
• Let D(1), D(2) be the decks of two exponential families. We define the labeled product of D(1) and D(2):
L  =  D(1)  ×~  D(2) .
L consists of ordered hands with one card from each family: that is, (C1, C2) where C1 = (S1, p1) is a card of the D(1) family; C2 = (S2, p2) is a card of the D(2) family; and the total label set is S1∪S2 = [n], the standard label set, where n = wt(C1) + wt(C2).
• Proposition 1: (Labeled Product Principle) Let ℓn be the number of two-card ordered hands of weight n in the family L, with exponential generating function ℓ(x); and let d(1)(x), d(2)(x) be the exponential deck-enumerators for D(1) and D(2). Then we have:

ℓ(x)   =   d(1)(x) d(2)(x).

• Proof: The product of the generating functions is (by [W] Rule 3'):
d(1)(x) d(2)(x)   =   ∑n≥0 dn(1)  xnn!    ∑n≥0 dn(2)  xnn!
=   ∑n≥0 (i=0n (n | i) di(1) dn−i(2) ) xnn!
The convolution in parentheses counts triples (S1, p1, p2), where S1 ⊂ [n] is an i-element label set; and p1 ∈ D(1), p2 ∈ D(2) are pictures of the two families with total weight n.
By transformation, such triples (S1, p1, p2) are in bijection with pairs of cards (C1, C2) ∈ L. The only information missing from the triple is the label set of C2, but this is just S2 = [n] \ S1.
This transformation shows that  ∑i=0n (n | i) di(1) dn−i(2)   =   ℓn , and therefore  d(1)(x) d(2)(x)   =   ℓ(x)  as desired.
2. Ordered hands with k cards.
• The next step is to define the kth labeled power of a single deck D:
L(k)  =  D  ×~  ⋯  ×~  D     (with k factors).
This consists of ordered k-card hands, meaning lists (C1,...,Ck), where each entry is a card of the family D, and the total label set is the standard [n]. That is, Ci = (Si, pi) with S1 ∪ ⋯ ∪ Sk = [n].
• Proposition 2: Let ℓn(k) be the number of k-card ordered hands of weight n in the family L(k), with exponential generating function ℓ(k)(x); and let d(x) be the exponential deck-enumerator for D. Then we have:

(k)(x)   =   d(x)k.

• Proof: Induction on k ≥ 2. For k = 2, this is Proposition 1 above. Now inductively assume the desired formula is true for a given k ≥ 2. Then the family L(k+1) is in bijection with the labeled product L(k)  ×~  D, since we can obviously rewrite a (k+1)-list as a k-list next to a single entry:
(C1,...,Ck+1)   ↔   ((C1,...,Ck), Ck+1)
The left side has enumerator function ℓ(k+1)(x), and this must be equal to the enumerator of the right-hand side, which is ℓ(k)(x) d(x) by Proposition 1 applied to D(1) = L(k) and D(2) = D. This in turn is equal to d(x)k d(x) by the inductive assumption:
(k+1)(x)   =   ℓ(k)(x) d(x)   =   d(x)k d(x)   =   d(x)k+1,
which shows the desired formula for the case of k+1 factors. Thus, by induction, the Proposition holds for all k ≥ 2.
3. Unordered hands with k cards.
• Next, consider the family H(k) of unordered k-card hands from the family D: that is, a set of k cards {C1,...,Ck} with total label set [n]. These are almost the same as the ordered hands in #2 above, but the k! permutations of the k cards are considered as the same unordered hand. Since every permutation of a list moves around the labels to give a different list (the ordered hand has no symmetries), the number of unordered hands is just the number of ordered hands divided by k!:
h(k)n   =   1k!(k)n
The same is true of the enumerator functions.
• Proposition 3: The enumerator function of unordered k-card hands is:

h(k)(x)   =   1k!(k)(x)   =   1k! d(x)k.

4. Full exponential family: unordered hands of with any number of cards
• Finally, we consider the full family H, consisting of all unordered hands in our previous sense.
• Proposition 4: (Exponential Formula) The hand-enumerator of an exponential family of unordered hands from the deck D is:

h(x)   =   ed(x)   =   exp d(x).

• Proof: Summing the cases of unordered k-card hands from Proposition 3 for every k ≥ 0, the left-hand side is clearly:
h(x)   =   ∑k≥0 h(k)(x)   =   ∑k≥0 1k! d(x)k   =   exp d(x),
which is the desired formula.
5. Ordered hands with any number of cards
• The family L of all ordered hands is the union of all the L(k) for k ≥ 0 (counting L(0) as a single empty hand).
• Proposition 5: Let ℓn be the number of ordered hands of weight n, with any number of cards, from the deck D. The enumerator function of ordered hands is:

h(x)   =   1(1 − d(x)) .

• Proof: The Sum Principle gives the generating function:

ℓ(x)   =   ∑k≥0(k)(x)   =   ∑k≥0 d(x)k   =   1(1 − d(x)) ,

using the Geometric Series formula  ∑n≥0 zn  =  1(1−z) .

• Notes 2/26: Proof of the Lagrange Inversion Formula

• Notes 2/28: Integer Partitions
• The last entry in the Twelvefold Way chart is pk(n), the number of partitions of n into k parts: i.e. the surjective functions f : [n] → [k] with both [n] and [k] indistinguishable; or the ways to put n unmarked balls into k exchangeable, non-empty bins. (Here we reverse the roles of n and k from the chart, so as to have n ≥ k.)
• If we allow any number of parts, we obtain the partition number:   p(n)  =  p≤n(n)  =  p1(n) + ⋯ + pn(n).
• The integer-partition numbers pk(n) and p(n) are analogous to the corresponding set-partition numbers, the Stirling number {n | k} and the Bell number B(n), which count ways to partition a set of n labeled balls.
• We usually denote partitions by writing the multiplicity of balls in each bin, from most full to least full, using the traditional notation:

λ  =  (λ1, λ2,..., λk)   where   λ1 ≥ λ2 ≥ ⋯ ≥ λk > 0   and   λ1 + λ2 + ⋯ + λk = n.

The λi are called the parts of λ.
• Another useful notation is the Young diagram or Ferrars diagram of λ, in which we draw left-justified rows of dots, first a row of λi, then λ2, etc.
• For example, p(4) = 5 counts the partitions: (4), (3,1), (2,2), (2,1,1), (1,1,1,1), having Young diagrams:
 • • • •
 • • • •
 • • • •
 • • • •
 • • • •

• The (ordinary) generating function of the partition numbers is:

φ(x)   =   ∑n≥0 p(n)xn   =   ∏i≥1 1(1−xi) .

• Euler's Pentagonal Number Theorem states that:

1φ(x)   =   ∏i≥1 (1−xi)   =   1   +   ∑m≥1 (−1)m(x½m(3m−1)  + x½m(3m+1)).

That is, when you multiply out the denominator of φ(x), almost all terms cancel to give zero; but for n equal to a "pentagonal number" ½m(3m±1), one term survives, giving a coefficient of ±1. (By the way, Euler is pronounced "oiler", not "yuler".)
• We proved the Pentagonal Number Theorem by first going backward from the generating function 1φ(x) to a combinatorial model. The coefficients of ∏i≥1 (1−xi)  =  ∑n≥0 anxn are given by:

an   =   #{partitions of n into an even number of distinct parts}
−   #{partitions of n into an odd number of distinct parts}.

The first term in this model counts all λ = (λ1,..., λk) such that k is even, and the parts λi are all distinct: λ1 > λ2 > ⋯ > λk > 0. The second term is the same, but with k odd. For example, n = 9 can be partitioned into a even number of distinct parts in 4 ways as: (8,1), (7,2), (6,3), (5,4); and into an odd number of distinct parts also in 4 ways as: (10), (6,2,1), (5,3,1), (4,3,2).
• To finish the proof of the Theorem, we gave Franklin's Transformation, which takes partitions with an even k to partitions with an odd k, and vice versa. The only exceptions are two special shapes of partitions, having m rows and n = ½m(3m−1) or ½m(3m+1) for m ≥ 1.

• Notes 3/10: Generating function for rooted trees.
1. Definition
1. Let rn be the number of rooted, unlabeled, unordered trees. That is, the vertices are identical dots; one of the vertices is designated as the root or ancestor; and there is no distinction of older or younger children of each vertex. Two such trees are considered the same if one can bijectively map vertices to vertices, root to root, and edges to edges.
2. Example: By definition r1 = 0, and trivially r1 = r2 = 1.
3. Example: We have r3 = 2, counting the rooted trees:
®−−O−−O       O−−®−−O
Note that if the root is on the last vertex, this is symmetric to (and hence the same as) the first example.
4. Example: To compute r4 , consider that the path-tree can have its root either on an end or an inner vertex, and the 3-branch star-tree can have the root either in the center or on a branch, so that r4 = 2 + 2 = 4.
5. No one has found an explicit formula for rn , and it is pretty clear there is none. Our goal is to find an efficient recurrence.
2. Generating function equation
1. Our trees satisfy a recursive choice algorithm which leads to an equation involving the generating function. Removing the root, we mark each neighbor of the root as a new root, giving a set of smaller rooted trees: {T', T'',...}. Some of these child trees might be identical, so it is really a multi-set of trees.
2. Our choice algorithm for multisets (for example, integer-partitions in HW 2/28) was to independently choose the multiplicity of each kind of element. Here, the kinds are just all the distinct trees. Indeed, let us designate all the trees of size n as: Tn,1, Tn,2,..., Tn,rn. For example:

T1,1  =  ®,      T2,1  =  ®−−O,      T3,1  =  ®−−O−−O      T3,2  =  O−−®−−O.

For higher n, not all the trees are paths, of course, and we do not yet know a way to generate them all. We are simply imaginging the set of all possible trees, and numbering them arbitrarily.
3. We thus obtain the choice algorithm:

 Choose T ⇔ (root) and (0 T1,1's or 1 T1,1's or 2 T1,1's or ⋯) and (0 T2,1's or 1 T2,1's or 2 T2,1's or ⋯) and (0 T3,1's or 1 T3,1's or 2 T3,1's or ⋯) and (0 T3,2's or 1 T3,2's or 2 T3,2's or ⋯) and   ⋯

This gives an effective way to construct the trees T up to a given size (see HW 3/10 #3).
4. Translating into algebra, we replace the choice of each Ti,j , where 1 ≤ j ≤ ri , by x i, since this choice adds i vertices to the original T. The result is:

n≥1 rnxn   =   x ∏i≥1 (1 + xi + x2i + ...)ri   =   x  ∏i≥1 1(1 − x)ri

We cannot easily write this in terms of f(x)  =  ∑n≥0 rnxn, but it does lead to a recursive contruction algorithm for all the trees T, and to a very messy recurrence (see HW 3/10 #3).
3. Recurrence using x D log method.
1. Starting with the above equation of generating functions, we derive a fairly efficient recurrence for the sequence {rn}. Now, log(x g(x)) is not defined as a formal power series in R[[x]], for any g(x), so we start by dividing both sides by x, getting:

n≥0 rn+1xn   =   ∑n≥1 rnxn−1   =   ∏i≥1 1(1 − x)ri

2. Left side: applying the x D log operation to f(x)  =  ∑n≥0 rn+1xn, we get: x d/dx log f(x) = x f '(x) / f(x), that is:

n≥1 n rn+1 xn ∑n≥0 rn+1 xn

3. Right side: We have log(uv) = log(u) + log(v), and thus log( ∏i uiri ) = ∑i ri log ui . Also log 1(1−x) = ∑j≥1 1/j xj . Hence:

log  ∏i≥1 1(1 − x)ri   =   ∑i≥1 rj log 1(1−xi)

=   ∑i≥1j≥1 rij  xij   =   ∑k≥1 (i | k irik) xk,

where in the third equality we substitute k = ij, so that rij  =  ri(k/i)  =  irik ; and the inner summation is over all whole-number divisors i of k. Taking x D cancels the denominator k, giving:

k≥1 (i | k iri) xk.

4. Now equating the left and right sides, clearing the denominator, and collecting xn terms, we get:

n≥1 n rn+1 xn   =   ∑k≥1 (i | k iri) xk    ∑m≥0 rm+1 xm

=   ∑n≥1 (k=1n   ∑i | k i ri rn−k+1 ) xn,

where in the second equality we substitute n = k + m , so that m+1 = n−k+1.
5. Dlog Recurrence Formula: Equating the coefficients of xn on the two sides, we obtain the double summation formula:

 rn+1   =   1⁄n ∑k=1n    ∑i | k i ri rn−k+1 .

The inner summation is over all whole-number divisors i of k. This recurrence is extremely mysterious: it is not even clear why the right side should be an integer. It shows how much deeper the Generating Function Method is than our own combinatorial insight.
6. Example: To compute r5 , we sum over k = 1,2,3,4 and i running over all divisors of k: that is, (i,k) = (1,1), (1,2), (2,2), (1,3), (3,3), (1,4), (2,4), (4,4),

r5 = 1/4 ( 1r1r4 + 1r1r3 + 2r2r3 + 1r1r2 + 3r3r2 + 1r1r1 + 2r2r1 + 4r4r1 )
= 1/4 (4 + 2 + 4 + 1 + 6 + 1 + 2 + 16) = 9

• Notes 3/12−3/17: Otter's Formula counting unrooted, unlabeled trees
1. Unrooted vs. rooted trees
1. Goal: Compute tn = # unrooted unlabeled trees (OEIS), from known values of rn = # rooted unlabeled trees. (At least we know a recurrence to compute rn, whereas none of our techniques can touch tn. See OEIS.)
2. For each unrooted tree T, there are n possible vertices to mark as a root, but vertices which are symmetric to each other give the same rooted tree. Thus, rn is generally not a multiple of tn , because the number of non-symmetric vertices is not the same for each unrooted T. The analysis of symmetries will be crucial in relating unrooted and rooted trees.
2. Symmetries and quotient of a tree
1. The symmetry group of T = (V,E) is:

Γ = ΓT = Sym(T) = { one-to-one σ : V→V   s.t. uv ∈ E ⇒ σ(u)σ(v) ∈ E },

i.e., those permutations of the vertices which take edges of T to edges of T.
A symmetry class of vertices is a set v = { σ(v) s.t. σ ∈ Γ }, all the vertices symmetric to a vertex v.
2. Define the quotient graph of T as: T = (V, E), with vertices: V := { v s.t. v ∈ V }, and edges:

E := { e = u v,  such that  uv,  and u'v' ∈ E  for some u' ∈ u and v' ∈ v}.

These e collect symmetry classes of edges of T, omitting the symmetry edges e = uv with v = σ(u) which would lead to loop-edges u v = u u in T.
3. Example:  T   = 1  −− 2 −− 3 −− 4 | | 5 6

1. The symmetries of T are: the transposition of vertices 1, 5; the transposition of vertices 4, 6; the reflection which flips the whole tree horizontally; and all compositions of these. For example, doing the reflection (14)(23)(56) after the transposition (15)(2)(3)(4)(6) gives σ = (1654)(23).
2. There are |Γ| = 8 symmetries in all.
Proof: It is easy to write down at least 8 symmetries by composing the known ones. There are at most 8 symmetries bcause any symmetry σ must take 1 to σ(1) = one of the 4 leaves, and this determines σ(2), σ(3), σ(5). The only remaining choice is σ(4), which must be one of the 2 remaining leaves. This gives at most 4×2 = 8 choices for σ.
3. The edge 23 is a symmetry edge, since 2 = 3 = {2,3}, so this edge is excluded from the quotient graph. Also 1 = {1,5,4,6}, since all of these vertices are symmetric to each other under various symmetries. The quotient graph is: T  =  1  −−  2 .
3. Otter's Lemma: If T is a tree, then its quotient graph T is also a tree.
Also, every edge of T corresponds to a single symmetry class of edges of T.
Proof:
1. By hypothesis, we suppose T is a tree, i.e. connected and acyclic (no cycles).
2. To see that T is connected, note that a path P from u to v in T corresponds to a path P from u to v in T. (The only exception is when P contains a symmetry edge e = uv with u v = u u, in which case we replace uu in P with the single vertex u.) Since paths connect any two vertices of T, the same is true of T.
3. To see that T is acyclic, suppose instead that T had a cycle C = (u,v,w,...,z,u) . Then we could lift this to a path of distinct vertices (u,v,w,...,z) in T, and then continue as the walk: (u,v,...,z,u',v',....) where u' ∈ u is some vertex of T symmetric to u, and v' ∈ v, etc. Recall that a walk can have repeated vertices, so we can continue this walk indefinitely. If the walk ever came to a repeated a vertex (for example if u' = u), this would make a cycle in T, which is impossible since T is acyclic. Thus, the walk must actually be an infinite path of distinct vertices, which is impossible since T is finite. The contradiction proves there can be no cycles in T.
4. Since T is connected and acyclic, it is a tree, completing the proof of the first statement.
5. Finally, we want to show that if u v is an edge of T corresponding to edges uv and σ(u) τ(v) in T, then σ(u) = τ(u) or σ(v) = τ(v).
• Suppose to the contrary that σ(u) ≠ τ(u) and σ(v) ≠ τ(v). Then the inverse symmetry σ−1 takes σ(u) τ(v) to the edge, u ρ(v), where ρ = σ−1τ and u ≠ ρ(u),  v ≠ ρ(v).
• Applying ρ to the edges uv and u ρ(v), we get edges ρ(u) ρ(v),  ρ(u) ρ(ρ(v)), and in fact ρk(u) ρk(v),  ρk(u) ρk+1(v) for all k ≥ 0. Hence T contains the walk u, ρ(v), ρ(u), ρ2(v), σ2(u),.... Since T is finite, this bipartite walk must contain repeated vertices with at least 4 edges between them, creating a cycle, which is impossible since T is a tree.
• Thus our initial supposition was false, and all edges corresponding to u v are of the form σ(u)σ(v) for all symmetries σ.
6. Note: The above reasoning is not just BS to make an obvious fact seem impressive. The contrary situations imagined in the proof really could happen, if we loosened the hypothesis that T be a finite tree.
For example, let T be the infinite tree consisting of an infinite path ...v−2v−1v0v1v2...., together with short side branches: v3i+1xi and v3i+2yizi for every integer i. Then the only symmetries of T are powers of the translation τ which takes τ(vi) = vi+3, τ(xi) = xi+1, τ(yi) = yi+1, τ(zi) = zi+1. (That is, τ moves each vertex over by 3 units.) In the quotient graph T, the infinite path then coils down into a 3-cycle: v0v1v2v0 (with short side branches).
That is, the quotient of the tree T is not a tree, because T really does have a cycle which lifts to an infinite path of T.
4. Relation between rooted and unrooted tree numbers
1. For a tree T with quotient T = (V, E), let pT = |V| and qT = |E|, the number of symmetry classes of vertices and of non-symmetry edges of T.
2. For T a given unrooted tree, pT is the number of distinct ways to choose a root vertex, since putting the root at v counts the same as putting it at a symmetric vertex σ(v). Thus, letting rn be the number of rooted trees with n vertices, we have:   rn  =  ∑T pT,  where T runs over all n-vertex unrooted trees.
3. We define an edge-rooted tree to be a tree with one non-symmetry edge e marked as the root edge (instead of a root vertex). Let en be the number of edge-rooted trees with n vertices. Analogously to the previous, for T a given unrooted tree, qT = |E|, the number of symmetry classes of non-symmetry edges of T. By the same reasoning as before, qT is the number of distinct ways to choose a root edge, and we have:   en  =  ∑T qT,  where T runs over all n-vertex unrooted trees.
4. Claim: en  =  ½[ ∑ i=1n−1 ri rn−i  −  rn/2 ] .
Proof: Given an edge-rooted T" with n vertices, we can remove the root-edge e and make the endpoints into vertex-roots, obtaining a set {T'1, T'2} of vertex-rooted trees with a total of n vertices. Furthermore, since e was not a symmetry edge, T'1 and T'2 are distinct rooted trees (not the same T' twice). Thus we get a reversible transformation T" ↔ {T'1, T'2}. The number of ordered pairs (T'1, T'2) with i and j vertices respectively is ri rj ; but we must remove the pairs (T', T') consisting of the same T' twice, whose number is rn/2; so the number of unordered sets of distinct trees is given by the desired formula. (If n is odd, we take rn/2 = 0.) Finally, the number of unordered pairs of distinct elements is 12! times the number of ordered pairs. We combine the above reasoning to get:
5. Otter's Formula:

tn  =  rn  −  ½[ ∑ i=1n−1 ri rn−i  −  rn/2 ] .

Note that if we could write the ri values on the right in terms of ti's, this would give a recurrence for tn by itself, but there is no such formula known.

• Proof Notes from Math 481, giving basic tips on style and content of proofs.

• Graph Notes from Math 481, including Planar Graphs (III) and Polyhedra (IV).

• Notes 3/26: Steinitz Lemma and Steinitz Theorem
• I based my lectures on:
• Book: Jurgen Richter-Gebert, Realization Spaces of Polytopes, Part IV, pp. 120−143.
• Günter Ziegler, Convex Polytopes: Extremal Constructions and f-Vector Shapes, here.
• The f-vector of a polyhedron is the triple (n,q,r) of its vertex, edge, and face numbers.
• Steinitz Lemma: A triple (n,q,r) is the f-vector of a convex 3-dimensional polyhedron P if and only if: q = n + r − 2,  r ≤ 2n−4, and n ≤ 2r−4.
• Since q = n + r − 2 we usually ignore it, and record only (n,r) . The region of the (n,r) plane defined by the Steinitz inequalities is a wedge lying between two lines:

½ n + 2   ≤   r   ≤   2n − 4.

The f-vectors (n,r) are exactly the integer points in this region:

Note that many different polyhedra (Numericana) can have the same f-vector, so the above diagram is far from a good classification of all polyhedra.
• Steinitz Theorem: A graph G is the edge-graph of a convex 3-dimensional polyhedron if and only if G is planar and 3-connected.
Planar means G can be drawn in the plane without edge-crossings. 3-connected means we must remove at least 3 vertices from G to make it disconnected; that is, G−v1−v2, the graph with any two vertices removed, is always a connected graph.
• The (⇒) direction is known as Balinski's Theorem for dimension 3. We will prove the (⇐) direction by combinining Tutte's Stressed Graph Theorem and Maxwell's Lifting Theorem.

• Notes 3/28: Balinski's Theorem
• Balinski's Theorem for dimension 3: The edge-graph G of a convex 3-dimensional polyhedron P is 3-connected, meaning G−v1−v2, is always connected.
• Proof. Case 1: Suppose v1 and v2 lie on a face F of P. Suppose that, for a normal vector a, the plane of F is given by the equation a x = c, so that a x ≤ c for all x ∈ P. The "height" function a x has a maximum value a x = c for x on F, and a minimum value a x = b for x in some "bottom" flat B (a vertex, edge, or face).
Now, any vertex v ∉ B has a lower neighbor w, meaning a w < a v : this is because P contains points lower than v by hypothesis, and P is contained in the cone of v, whose edges are the neighbors of v. Therefore, we can connect v to the bottom B by a strictly decreasing path, which cannot contain v1 or v2 since the path contains at most one point with a x = c. Thus, any two vertices v, v' can be connected to each other in G−v1−v2 by connecting v to some w ∈ B and v' to some w' ∈ B, and connecting w to w' along the edge-graph of B (which is a vertex, an edge, or a cycle).
• Case 2: Suppose v1 and v2 pass through the interior of P. Then we can take a third vertex v0, so that v0, v1, v2 define a plane, a x = c. By the same reasoning as before, for any vertex v with a v ≤ c, we can connect v by a downward path to the "back flat" B = {x such that a x = min}. Also, for any vertex v with a v ≥ c, there is an upward path to the "front flat" F = {x such that a x = max}. Finally, the middle vertex v0 connects to both F and B, so we can clearly produce the needed paths in G−v1−v2.

• Notes 3/31: Augmenting Path Algorithm and Menger's Theorem
• Connectivity and independent paths.
• Let G by any graph (not necessarily a polyhedron graph). A cut-set is a set of vertices {v1,...,vk} whose removal disconnects G: that is, G−{v1,...,vk} has two or more connected components.
• The index of connectivity κ(G) is the minimum number of vertices which form a cut-set G. That is, κ(G) = k means that G − {v1,..., vk−1} is connected for any set of k−1 vertices; but there is some choice of k vertices such that G − {v1,..., vk} is disconnected. (By convention, for the complete graph we define κ(Kn) = n−1.) We say G is k-connected if κ(G) ≥ k; that is, it takes at least k vertices to disconnect G.
• We say P1, P2 are independent xy-paths if their only common vertices are their endpoints x and y.
• A computationally efficient way to determine the connectivity of a graph is the Ford-Fulkerson Augmenting Path Algorithm. For any non-adjacent vertices x,y in G, a full run of the algorithm produces two things:
1. A family of k of independent xy-paths, ℘ = {P1,..., Pk};
2. a cut-set of k vertices which disconnect x from y in G − {v1,..., vk}.
For now, let us assume these results.
• Claim: Let kxy be the number of paths (or of vertices) produced by the algorithm, and let κxy(G) be the minimum number of vertices needed to disconnect x from y in G. Then kxy = κxy(G).
Proof: For a given x,y, the cut-set of kxy vertices must have at least κxy(G) elements, so k ≥ κxy(G). On the other hand, each of the independent paths between x and y requires at least one vertex removed to block it, so kxy ≤ κxy(G).
• To determine the global quantity κ(G), we simply take the minimum over all non-adjacent x,y of κxy(G) = kxy.
• The algorithm also immediately proves the following classic result:
Menger's Theorem:
• The minumum number of vertices needed to disconnect G equals the maximum number of independent paths which can be found between every pair of vertices.
• Equivalently, G is k-connected  ⇔  G has at least k independent xy-paths for every pair of vertices x,y.
• Augmenting Path Algorithm.
• Starting with an empty family of no paths, each iteration produces a larger family of modified independent xy-paths, until eventually the algorithm gets stuck, blocked by a set of disconnecting vertices.
• Specifically, given a (possibly empty) family of independent xy-paths ℘ = {P1,..., Pj}, we attempt to find an augmenting path Q = Qj+1 from x to y. Such Q is allowed to traverse all edges of G not used by any path in ℘; and Q may also traverse edges in ℘, but only in the backwards direction, away from y, toward x. (Also, Q is not allowed to cross a vertex in ℘ without at least one backward step along ℘.) To construct such a path Q, we start at x and take successive neighbors along permitted edges, until either:
1. the path Q reaches y; or
2. no more neighbors can be added, and no Q can reach y
• Case (i): If the augmenting path Q reaches y, we define a new set of j+1 paths ℘' as follows. We consider the subgraph P' ⊂ G which is the union of all vertices and edges of ℘ and Q, but removing all the edges (not vertices) where Q backtracked along a path in ℘.
Then P' contains:
• j+1 edges at x and at y, since Q adds another edge to those in ℘;
• 2 edges at every other vertex, since a vertex where Q meets ℘ has an outgoing edge in ℘, and the incoming edge in ℘ is a backward edge of Q and is removed. (Similarly at a vertex where Q leaves ℘.)
Thus, the graph P' can be uniquely split into family ℘' of (j+1) xy-paths: after an initial step from x, there is only one way to step within P' until we reach y.

In the figure, the initial family ℘ of 3 independent xy-paths admits an augmenting xy-path Q, which has three stretches of backwards motion along the previous paths. By removing these backward edges, we obtain a set of edges which can easily be split up into a new family ℘' of 4 independent xy-paths.
• Case (ii): If no augmenting path Q can reach y, then there is a subgraph G' ⊂ G−y, consisting of all vertices which can be reached by some path Q obeying the augmenting path rules. Let ℘ = {P1,..., Pk}, and for each Pi , let vi be the last vertex of Pi lying in G'. (If x is the only vertex of Pi ∩ G', then take vi to be the second vertex of Pi.)
Claim: Any xy-path R in G must contain some vi , so that G − {v1,...,vk} is disconnected. Indeed, consider the edge wz where R steps out of G', meaning w ∈ G', z ∉ G'. If w is not on any path Pi, then we could take an augmenting path xQw and extend it to the augmenting path Q' = xQwz, giving the contradiction that z ∈ G'. If w ∈ Pi but w is not the last vertex of Pi in G', then we can take an augmenting xQvi and extend it backward to an augmenting path Q' = xQviPwz, again giving the contradicition z ∈ G'. The remaining possibilities are w = vi or wz = xvi , so R must contain vi .

• Notes 4/7−4/11: Tutte's Stressed Graph Theorem, the rubber-band model for drawing graphs in equilibrium position. See also Solutions 4/7.

• Notes 4/14−4/18: Maxwell's Lifting Theorem.
• My lectures follow Richter-Gebert pp. 133−139.
• Let G = (V,E) be a 3-connected planar graph with n vertices in equilibrium positions v1,..., vn, where vi = (xi, yi). The last n−k+1 vertices vk+1,..., vn are arranged in an external convex polygon, while v1,..., vk are internal vertices which satisfy the equilibrium (Laplacian vanishing) condition: for each internal vi, we have: ∑j∈N(i) (vj−vi)   =   0. Also assume that the interior regions are listed as R1,..., Rr−1, where r is the number of regions of G (including the infinite region).
• Now we work with 3-dimensional vectors. First, we raise the vertices to level 1:  (vi,1) = (xi, yi, 1). Now, for region Rj, we recursively define a 3-dimensional vector qj. We start with q1 = (0,0,0). Suppose S and R are two regions with a common border edge e = uv, and if we look from u to v, then S is on the left, R is on the right:

If we know the vector qS, we define qR by the recursive rule:

qR   =   qS + (v,1)×(u,1).

Because of the cross-product property that a×b = − b×a, this is equivalent to:

qS   =   qR + (u,1)×(v,1).

• The rule allows us to define qj for each region Rj, using the recursive rule to go from one region to its neighbors. There might be several paths of neighboring regions by which to define a given qj, and we will prove later that they all give the same vector. That is, qj is well-defined.
• We will use qj to define a height for each vertex vi. For a vertex vi which is a corner of region Rj, we let:

hi   =  (vi,1) qj.

Again there is an ambiguity: a given vi will be the corner of several regions; but the definition will always produce the same height hi. Thus we get a 3-dimensional vertex, a corner of a convex polyhedron P:

(vi, hi) = (xi, yi, hi).

• The heights will always be positive (though this is not obvious), and the polyhedron will lie above the xy-plane. Each internal region Rj of G will be a shadow of a small face of the polyhedron P, while the outer polygon of G will correspond to a large extra face (a lid) on top of P. We will assume that the outer face is a triangle, so that its corners (vn−2, hn−2), (vn−1, hn−1), (vn, hn) automatically lie in a common plane. If there is no triangular face of G to use as the outer face, we instead pass to the dual graph G*. This must possess a triangular face by a previous lemma (Graph Notes IV.4), so we can lift G* to a polyhedron P*, and take the dual polyhedron P to correspond to the original G.
• We need three results to validate the above constructions.
Lemma 1: The q-vectors are well-defined, giving the same qi along any two paths of neighboring regions joining R1 to Ri.
Proof: Consider the vector increments (v,1)×(u,1) which appear in the recursive formula as one goes around any cycle of neighboring regions (a cycle in the dual graph of G). I claim these increments always sum to the zero vector. To see this, we can split a large cycle into a sum of small cycles, each around one vertex of G. Now, the sum of vector increments for the edges around a given vertex add to zero because of the equilibrium condition and the basic properties of cross products. (See Solutions 4/14 end of #1a,b.)
• Lemma 2: The height of each point is well-defined, giving the same h(v) = (v,1) qR for any region R containing v.
Proof: It suffices to prove this for a vertex v which is the corner of two adjacent regions S,R separated by an edge uv, as in the recursive formula. In this case:

hR(v)  =  (v,1) qR  =  (v,1) qS + (v,1) (v,1)×(u,1)  =  (v,1) qS  =  hS(v),

since (v,1)×(u,1) is perpendicular to (v,1), so their dot product is zero. (See Solutions 4/16 #2.)
• Lemma 3: The polyhedron P is convex.
Proof: It is enough to prove that, for each edge uv separating two regions S,R in G, the planes in their lifting form a surface (a lower surface of P) which is concave up (like an open book face up rather than face down). This means that, for any point w inside the lefthand region S, the R-height is less than the S-height. That is, we want:

hR(w)  =  (w,1) qR + (w,1) ((v,1)×(u,1))  ?<?   hS(w)   =   (w,1) qS,

meaning:

0 ?>? (w,1) ((v,1)×(u,1))   =   det((w,1), (v,1), (u,1)),

where det((w,1), (v,1), (u,1)) means the determinant of the 3×3 matrix with row vectors (w,1), (v,1), (u,1). This will happen exactly when {(w,1), (v,1), (u,1)} form a left-handed coordinate system. But given our assumptions about w,v,u, we can see that for any choice of the origin (0,0,0), we can point the left index finger toward (w,1) and the middle finger toward (v,1), and the thumb toward (u,1). For an algebraic proof, see Solutions 4/18.

• Math 482, Spring 2008 (mostly different topics).