- Notes 1/11: We use the bins-and-beans correspondence to compute the multi-set number ((n | k)), which counts the multi-sets of k elements of n kinds. We start by picturing the 1's in a multi-set as beans in bin #1, the 2's as beans bin #2, and so on, writing beans as O and bin-dividers as | . There is a total of k beans and n−1 bin-dividers. For example, one multiset in ((5 | 7)) is:{1,1,2,4,4,4,5} ↔ O O | O | | O O O | O
Now, a sequence of O's and |'s is determined by choosing which n−1 of the k+n−1 symbols are | ; this is a subset of n−1 positions chosen from k+n−1 . In the above example k+n−1 = 11 :
O O | O | | O O O | O ↔ {3,5,6,10} ⊂ {1,2,....,11}Conclusion: the multi-sets counted by ((n | k)) are in one-to-one correspondence with the sets counted by (k+n−1 | n−1), meaning that these numbers are equal. Alternatively, we could choose the k positions of the O's, giving a correspondence with (k+n−1 | k) . Thus:
((n | k)) = (k+n−1 | n−1) = (k+n−1 | k) ,which we know how to compute. For example, ((5 | 7)) = (11 | 4) = 330.
- Notes 1/14. We use correspondences to prove combinatorial equations of the form |A| = |B| , where A and B are two interesting sets. A one-to-one correspondence consists of two mappings or transformations, f : A → B and g : B → A . This means each element a ∈ A is transformed into an element b = f(a) ∈ B , and each b ∈ B is transformed into a = g(b) ∈ A . We require that these mappings undo each other: g(f(a)) = a for each a ∈ A and f(g(b)) = b for each b ∈ B .
Example: We proved that (n | k) = (n | n-k) using the following correspondence. First, (n | k) counts A, the collection of all k-element subsets of {1,...,n}; and (n | n-k) counts B, the collection of all (n-k)-element subsets of {1,...,n} . Then for an element S ∈ A , we transform the set S, having k elements, into its complement, having n-k elements:
S' = f(S) := { i s.t. i ∉ S } .For an element S' ∈ B, we use the same recipe to go back:
S = g(S') := { i s.t. i ∉ S' } .Then g(f(S)) is the set of those i not excluded from S, namely g(f(S)) = { i ∈ S } = S . We argue the same way to show f(g(S')) = S' .
- Notes 1/16. Logical algebra and the Binomial Theorem
- Choosing a subset S ⊂ {A,B,C} is equivalent to choosing or not choosing each of the three elements A,B,C. We figure the possiblilities for S by considering the expression:
(XA or YA) and (XB or YB) and (XC or YC),
where XA means "A is not in S" and YA means "A is in S", etc. We expand this expression using the logical distributive rule:
(P or Q) and R = (P and R) or (Q and R).Here P,Q,R are simple statements, and the compound statements on the two sides of the equation are logically equivalent. We expand until we have an expression like: (XA and XB and XC) or (XA and XB and YC) or ... or (YA and YB and YC) ,in which the 8 terms correspond to the subsets S = {}, {C}, ... , {A,B,C} . - Now we rewrite the entire computation, replacing the statements XA, XB, XC by the variable x; the statements YA, YB, YC by the variable y; the operation "or" by + ; and the operation "and" by ×. Notice that each successive logical equality becomes a valid algebraic equality. In the end we have shown that:(x+y)(x+y)(x+y) = xxx + xxy + xyx + yxx + ... + yyy ,in which the 8 terms again correspond to subsets (the subsets record the positions of the y's). Now we simplify by writing powers of x and y, and we collect like terms to get a polynomial a0 x3 + a1 x2y + a2 xy2 + a3 y3 . The coefficient ak is the number of terms x3-kyk, which is just the number of subsets S with k elements (since the power of y in each term is precisely the number of elements in the corresponding set S). That is, ak = (3 | k), which explains (and proves) the Binomial Theorem for n = 3, namely:(x+y)3 = (3 | 0) x3 + (3 | 1) x2y + (3 | 2) xy2 + (3 | 3) y3 .
- We can do all this for any n. We do not need to keep track of the intermediate computations in the expansion, since we know the beginning form (x+y)n and the expanded form xx...x + ... + yy...y in which each term corresponds to a subset in a transparent way. For example for n = 5, xxyxy would correspond to S = {3,5}. Then we group like terms xn-kyk just as before to get the Binomial Theorem.
- Notes 1/25. Method of Generating Functions example.
Problem: How many distinguishable 5-card hands can be dealt from two identical 52-card decks (a double deck)? - Step 0: Generalize the problem into a sequence of numbers {ak} = a0 , a1 ,..., an . For this problem, let ak be the number of k-card hands dealt from a double deck, for k = 0, 1, 2,..., 104. This is useful because a0 + ... + a104 is the number of all hands, which can be easily computed via the product principle.
- Step 1: Write the polynomial in a variable x having coefficients ak : f(x) = a0 + a1 x + a2 x2 + ... + a104 x104 = ∑k=0104 ak xk . Find a simple formula for f(x) using the combinatorial properties of the sequence {ak}. A hand can be chosen according to the logical expression: choose a hand ⇔ (0C1 or 1C1 or 2C1) and ... and (0C52 or 1C52 or 2C52), where 0Ci means "exclude the ith card of the deck", 1Ci means "include 1 of the ith card of the deck", and 2Ci means "include 2 of the ith card of the deck". We turn the logical equivalence into an algebraic equation by replacing as follows:
| logic | choose a hand | ⇔ | 0Ci | 1Ci | 2Ci | or | and |
| algebra | f(x) | = | x0 | x1 | x2 | + | × |
We obtain:
f(x) = (x0 + x1 + x2) × ... × (x0 + x1 + x2) = (1 + x + x2)52 . - Step 2: Use algebra to expand f(x) and compute the coefficients ak . Since we cannot directly apply the Binomial Theorem to powers of 1 + x + x2 , we apply it twice, the first time to 1 and x+x2, the second time to x and x2: f(x) = [1 + (x+x2)]52 = ∑j=052 (52 | j) (x + x2)j = ∑j=052 (52 | j)∑ i=0j (j | i) xj-i (x2)i
= ∑j=052 ∑i=0 52 (52 | j) (j | i) xj+i = ∑k=0104 [ ∑(i,j) (52 | j) (j | i) ] xk .
where the last summation runs over all (i,j) such that 0 ≤ i ≤ j and i + j = k . That is, (i,j) = (0,k), (1,k-1), (2,k-2), ... , (⌊k/2⌋, ⌈k/2⌉) where ⌊ ⌋ means round down and ⌈ ⌉ means round up. We conclude that: ak = ∑i=0⌊k/2⌋ (52 | k-i) (k-i | i) .
For example for k = 2, we have (i,j) = (0,2), (1,1) and a2 = (52 | 2) (2 | 0) + (52 | 1) (1 | 1): this makes sense, since the terms correspond to choosing two distinct cards, or one double card.
For k = 5, we have (i,j) = (0,5), (1,4), (3,2) and:
a5 = (52 | 5) (5 | 0) + (52 | 4) (4 | 1) + (52 | 3) (3 | 2) .Can you explain this directly?
- Notes 2/4−2/6:Method of Generating Functions (Ch 2.4.2 & 2.4.5). Goal: evaluate a combinatorially interesting number a.
Step 0. Generalize the problem by seeing a as one of a sequence of similar numbers a0, a1, a2, .... Generally, this means replacing some specific number in the definition of a by the index k = 0,1,2,....
Step 1. Form 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} to get a simple formula for f(x).- The Product Principle for combinatorial problems can lead to a product formula for f(x).
- A recurrence for ak leads to an equation involving f(x), which can be solved for f(x).
- If we can find f(x) in terms of any known Taylor series, we can replace the series by its function.
Step 2. Given f(x), use algebra and calculus to expand it as a power series, thereby evaluating the coefficients ak.- 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 is gives useful results only for especially simple ones.
- Try to write f(x) in terms of functions with known Taylor series.
Known series - Geometric series 1/(1−x) = 1 + x + x2 + ... = ∑k≥0 xk .
- Binomial theorem: (1 + x)n = ∑k=0n (n | k) xk , where (n | k) = nk / k! is a binomial coefficient.
- Binomial with negative power: (1−x)-n = ∑k≥0 ((n | k)) xk , where ((n | k)) = (k+n-1)k / k! is a multi-choose number.
Examples - Let ak = ((n | k)) be the multi-choose numbers for fixed n. Step 0 is unnecessary.
Step 1: {ak} counts all multisets with n kinds of objects. This is equivalent to n independent choices of how many of each kind. The Product Principle gives: f(x) = (1 + x + x2 + ...)n . Now, f(x) = (1 + x + x2 + ...)n involves the geometric series 1 + x + x2 + ... = 1/(1-x) , so f(x) = 1/(1−x)n .
Step 2: We can apply Taylor's formula to the kth derivative f(k)(x) = (k+n-1)(k+n-2)...n (1-x)-(k+n), getting ak = (k+n-1)k / k! . This is a new way of getting the formula for the multi-choose numbers, and also gives the third of the known series above. - Define a sequence by the recurrence ak = 2ak + 1 for k ≥ 1, and a0 = 0. Step 0 is unnecessary.
Step 1: The recurrence leads to an equation involving f(x).f(x) = a0 + ∑k≥1 ak xk = 0 + ∑k≥1 (2ak-1 + 1)xk = 2x ∑k≥1 ak-1 xk-1 + x ∑k≥1 xk-1 = 2x f(x) + x/(1−x) .
Solving, we get: f(x) = x / (1−x)(1−2x) .
Step 2: We expand f(x) in partial fractions: i.e. we write it as a sum of geometric series terms c / (1− rx) where c is a constant and x = 1/r is a vertical asymptote of f(x). Solving x / (1−x)(1−2x) = b/(1−x) + c/(1−2x) for b and c, we find:f(x) = −1/(1− x) + 1/(1−2x) .Expanding the geometric series, we get: ak = −1 + 2k , which is indeed a correct but non-obvious formula.
- Notes 2/8: We derived the formula for the Fibonacci numbers following Ch 2.4.4. You should carefully go through this and check the details I left out. We start with the definition: F0 = 0 , F1 = 1 , and Fk = Fk-1 + Fk-2 for k ≥ 2 .
- Define the generating series f(x) = F1 x + F2 x2 + F3 x3 + ... . Except for the term F1 x = x , replace Fk xk by Fk-1 xk + Fk-2 xk and deduce the equation:f(x) = x + x f(x) + x2 f(x) . Solve this to get our formula: f(x) = x / (1 - x - x2) .
- Show that the vertical asymptotes of f(x) are x = -φ and x = ψ , where φ = (√5 + 1) / 2 ≈ 1.62 (the Golden Ratio), and ψ = 1/φ = (√5 - 1) / 2 ≈ 0.62 .Thus, we can write 1 - x - x2 = -(x+φ)(x-ψ) = (1 − φx)(1 + ψx) .Hint: Use the quadratic formula to find the zeroes of the denominator. Check the the formulas: φψ = 1 , φ − ψ = 1 and φ + ψ = √5 , and use them to simplify.
- Sketch the graph of f(x), and convince yourself that for any positive constants A and B, the graph of g(x) = A / (1 − φx) + B / (1 + ψx)will look roughly like the graph of f(x): namely, the behavior near the vertical asymptotes is the same. The theory of Partial Fractions guarantees that we can find values of A and B which make g(x) exactly equal to f(x).Find the correct constants A and B by multiplying out the denominator and substituting x = -φ and x = ψ . You should find A = 1/√5 and B = -1/√5, so that:f(x) = [ 1 / (1−φx) − 1 / (1+ψx) ] / √5 .
- Find the Taylor series of f(x) by substituting z = φx and z = −ψx in the geometric series 1/(1-z) = 1 + z + z2 + .... Collect like powers of x to find the coefficient:Fk = (φk - (-ψ)k ) / √5 .
- Notes 2/11: Quiz problem. Give a formula for the numbers defined by the recurrence c0 = 1 , ck = 3ck-1 − 1 for k ≥ 1.Compute: f(x) = 1 + 3x ∑k≥1 ck-1 xk-1 − x ∑k≥1 xk-1 = 1 + 3x f(x) − x/(1-x) ,
so that f(x) = (1−2x)/(1−x)(1−3x) . Expand by partial fractions to get: f(x) = ½( 1/(1−x) + 1/(1−3x) ) .Expand the geometric series to conclude: ck = ½(1 + 3k) .
- Notes 2/15: Given an object X with some structure, a symmetry of X is a one-to-one map of X to itself which preserves the structure. The set of all symmetries is denoted Sym(X). This has the binary operation of composition: doing one symmetry α after symmetry β, producing a new symmetry which we denote α ° β . The set Sym(X) along with the composition operation forms a group, analogous to a number system.
- Example: X = {1,2,...,n} is an unstructured set of n elements, the symmetries being all permutations (one-to-one mappings) π : X → X . We can denote such a symmetry by 2-line or cycle notation, as described in the HW. The set of all symmetries is called the symmetric group, and has the special notation Sym(X) = Sn .
- Example: X = a square in the plane. Since the symmetries are determined by the mapping of the 4 corners to each other, we may consider Sym(X) ⊂ S4 , and dentote any π ∈ Sym(X) by 2-line or cycle notation. The set of all symmetries has the special notation Sym(X) = D4 .
- Example: X = regular n-gon in the plane. Sym(X) = Dn ⊂ Sn . This is called the dihedral group, consisting of n rotations (counting the identity) and n reflections, so |Dn| = 2n.
- Example: X = regular n-gon with only rotations allowed. (Imagine decorating each edge of X with a clockwise arrow, so that a reflection would switch the direction of the arrows instead of taking them to themselves.) Sym(X) = Cn ⊂ Sn . This is called the cyclic group, consisting of n rotations (including the identity), so that |Cn| = n.
The group of symmetries obeys algebraic laws similar to usual multiplication.
- The operation is associative; for any α, β γ, we have:(α ° β) ° γ = α ° (β ° γ), so parentheses don't matter.
- The identity element ι (defined by taking each point of X to itself) behaves like the number 1 in usual multiplication: ι ° α = α ° ι = α
- Every element α has an inverse (reciprocal) β with α ° β = ι and β ° α = ι . We write β = α−1 .
- Unlike multiplication, composition is not usually commutatitive: in generalα ° β ≠ β ° α .
- Notes 2/20: Burnside's Theorem: If a symmetry group G = Sym(X) acts on the set C of colorings of X, and C is the set of symmetry classes of colorings, then the number of such symmetry classes is:|C| = 1/|G| ∑π∈G |Cπ| , where Cπ = {c s.t. π(c) = c} is the set of colorings fixed by π. If there are k colors, and the number of cycles of π on the vertices of X is cyc(π), then |Cπ| = kcyc(π). Proof of Burnside's Theorem.
- Notes 3/10: Theorem: A graph G is bipartite ⇔ G contains no odd cycles. To prove this, we give an algorithm which for any graph gives a bipartite decomposition of the vertices V = V+ ∪ V− , or the algorithm gets stuck and produces an odd cycle.
- Start with a base vertex v and mark it + .
- Given a set of vertices already marked + and − , mark − on all neighbors of + vertices, and mark + on all neighbors of − vertices. Repeat this until you run out of vertices, or until you get stuck because some vertex gets marked both + and − .
- Suppose you mark all vertices without a conflict. This means no + vertex ever has a + vertex for a neighbor, and the same for −, so you have a valid bipartite decomposition. In fact, all the + vertices are an even distance from v, and all the − vertices are an odd distance from v.
- Suppose you get stuck when vertex w, already marked + , gets marked with − . The + mark on w came from a − mark on a previous vertex x1 , and this can be followed back through a path of alternating ± vertices x1 , x2 ,... all the way to the base vertex v. Similarly, the − mark on w can be followed back through a path of alternating vertices y1, y2,.... These two paths certainly meet at their endpoint v, and let v' = xj = yk be the first place they meet. Now G contains the cycle:C = (w, x1, .... , xj−1, v', yk−1, .... , y1) .
- Continuing the previous case, the cycle C has length j + k . Suppose v' is + . The x-path goes back from the + mark on w, so j must be even. The y path goes back from the − mark on w, so k is odd, and j + k is also odd. Similarly, if v' is − , then j + k is still odd. Therefore C is an odd cycle.
- Notes 3/12−14: Basic facts on connectivity, cycles, trees. Let G = (V,E) be a graph.
- A walk is any way of traversing edges of G, with backtracking and double-crossing allowed. Formally: any list of vertices (v1,...,vk) where vivi+1 are edges.
- A path P is a copy of the path graph Pk inside G; i.e., a walk without backtracking or crossing any vertex twice. Formally: P = (v1,...,vk), a list of distinct vertices such that vivi+1 are edges.
- G is connected if any pair of vertices are connected by a path (or a walk).
- Lemma: If there is a walk from x to y, then there is a path. Proof: Remove detours, loops, backtracking from the walk, and what is left is a path.
- Any G is split into connected components: G = G1 ∪ G2 ∪ ... such that Gi are connected, and there are no edges between different Gi's. This is because connectivity between vertices is a transitive property: if x is connected to y and y is connected to z, then x is connected to z. A connected to component is the subgraph on all the vertices connected to a given vertex.
- A cycle is a copy of the cycle graph Ck inside G; i.e., a walk that comes back to its endpoint, with no backtracking or or crossing any vertex twice. Formally, C = (v1,...,vk), a list of distinct vertices such that vivi+1 and vkv1 are edges.
- A tree T is a graph which is connected and acyclic (with no cycles).
- Proposition: If T is a tree with n vertices, then T has n−1 edges. We proved this by induction on n, and you may assume it as a basic fact.
- Notes 3/21: An alternate proof of Cayley's Theorem is given by Joyal's Correspondence. This correspondence starts with a "vertebrate," which is defined to be a tree T with two vertices i,j designated as the head and the tail (possibly the same vertex), written as (T,i,j). The correspondence transforms vertebrates to functions f from the set {1,...,n} to itself. The number of vertebrates is clearly tn × n2 , where tn is the number of trees, and the correspondence shows this is equal to the number of functions, which is nn. We conclude that the tn = nn−2, which is Cayley's Theorem.
Joyal's Correspondence is computed by the following algorithm.
- Given (T,i,j), draw the "spine", the unique path from i to j.
- Consider the sequence of numbered vertices on the spine as a permutation π of these vertices from their numerical order.
- Write the permutation π in cycle form, and draw the corresponding directed graph G with an arrow from each k to its permuted image π(k).
- Each vertex k of the spine in T has a tree Tk of non-spine edges connected to it. Define the directed graph G' by reconnecting each Tk to its corresponding vertex k in G, with all its edges directed toward k.
- Interpret the graph G' as the function graph of some f: namely f(a) = b whenever G' has an edge from a to b.
We can easily define the reverse algorithm taking f to (T,i,j). The main difficulty is how to determine the vertices of the function graph G' which will become the spine of T: they are precisely the values contained in some cycle, i.e. those k such that f(f(...f(k)...)) = k for sufficiently many iterations of f.
- Notes 3/31: Platonic Solids (Ch 1.3.3).
- A Platonic solid is a 3-dimensional shape such that:
- all the faces are the same regular polygon, and
- all the corners have the same number of edges.
- It turns out there are five of these:
- the tetrahedron (or 3-sided pyramid) with 4 triangle faces, 3 at each corner
- the octahedron (two 4-sided pyramids glued at their bases) with 8 triangle faces, 4 at each corner
- the icosahedron with 20 triangle faces, 5 at each corner
- the cube, with 6 square faces, 3 at each corner
- the dodecahedron with 12 pentagon faces, 3 at each corner
- A Platonic graph G is the edge-graph of a Platonic solid. It is defined by the properties:
- G is planar, and all the regions have the same number of boundary edges,deg(R) = g, and
- G is regular, i.e. all the vertices have the same degree deg(v) = d.
- We can construct a Platonic graph just from knowing g and d. First draw the outermost g-gon, then and add d−2 edges inward from each vertex. Connect the ends of these edges to each other or to new vertices as appropriate to make each region have a g-cycle boundary. Continue this until all vertices have degree d and all regions have degree g.
- This construction will work only if (g,d) = (3,3), (3,4), (3,5), (4,3), (5,3) , which gives a complete classification of Platonic graphs and proves the above classification of Platonic solids.
- To prove this, let G be a Platonic graph with n vertices, q edges, r regions, girth g, and vertex degree d. We have:
- d ≥ 3 , g ≥ 3 since G comes from a solid
- n − q + r = 2 (Euler)
- dn = 2q , because ∑ deg(v) = 2q
- gr = 2q , because the basic inequality becomes an equality
Solving the above equations for n, q, and r:- n = 4g / (2d − gd + 2g)
- q = 2dg / (2d − gd + 2g)
- r = 4d / (2d − gd + 2g)
This means 2d − gd + 2g > 0, and for particular values of g ≥ 3:- g = 3: 6 − d > 0 ⇒ d = 3,4,5
- g = 4: 8 − 2d > 0 ⇒ d = 3
- g = 5: 10 − 3d > 0 ⇒ d = 3
- g ≥ 6: 2g > g(d − 2) > 6(d − 2) ⇒ d < 3 ⇒⇐ .
- Notes 4/18: Subgraph Formula for the chromatic polynomial
- We will consider a graph G = (V,E) with n vertices, m edges.
- A k-coloring of a graph G = (V,E) is a function c : V → {1,...,k} giving each vertex a color represented by a number 1,...,k. The coloring is proper if c(i) ≠ c(j) for neighboring vertices i,j (i.e., ij ∈ E).
- Counting function (chromatic polynomial) CG(k) = # proper k-colorings of G.
- A complicated but explicit expression for CG(k) is the Subgraph Formula:
CG(k) = ∑F ⊂ E (−1)|F| kcomp G[F] .
This is a summation with one term for each subset F of the edge set E. An edge set F defines a subgraph G[F] having the same vertices as G, but only the edges in F. Also compG[F] denotes the number of connected components of G[F]. - The Principle of Inclusion-Exclusion (PIE) says that for a big set A and bad subsets A1 ,..., Am , the size of the good set Agood = A − (∪i Ai) is given by:
|Agood| = ∑S (−1)|S| |AS|
where S runs over all subsets S ⊂ {1,...,m} and AS = ∩i∈S Ai , the intersection of all Ai with i ∈ S. - Proof of Subgraph Formula: We apply PIE to the big set A = { all coloring functions c : V → {1,..,k} }. We define a bad set Ae for each edge e = uv, namely Ae = { colorings with c(u) = c(v) }. Then clearly Agood is the set of proper k-colorings and CG(k) = |Agood| .
The bad colorings in AF = ∩e∈F Ae are just those which have a single color on each component of the subgraph G[F]. Thus |AF| = kcomp G[F]. Plugging this into PIE gives the Subgraph Formula.
