I have emailed the files already. It is an exam at 8am Thursday Brisbane, Australia time.
Counting the number of ways to select r objects from a list of n distinct objects: No repetition With repetition Ordered selection n! (n− r)! nr Unordered selection ( n r ) = n! (n− r)!r! ( n+ r − 1 r ) Identity 2.8 For r ≥ 1 and n ≥ 0, ( n+ 1 r ) = ( n r ) + ( n r − 1 ) . Identity 2.9 For n ≥ 0 and x, y ∈ R, (x+ y)n = n∑ r=0 ( n r ) xryn−r. Identity 2.10 For n ≥ 0, n∑ r=0 ( n r ) = 2n. Identity 2.11 For r ≥ 1 and n ≥ 0, ( n r ) = n−1∑ i=0 ( i r − 1 ) . Identity 2.12 For n ≥ 1, n∑ r=0 (−1)r ( n r ) = 0. Theorem 3.13 In an election, candidates U and R receive p and q votes respectively, where p > q. The probability that U is strictly ahead of R throughout the vote-count is p− q p+ q . Theorem 3.14 (Inclusion-Exclusion Principle) For finite sets A1, A2, . . . , An, |A1∪A2∪· · ·∪An| =∑ S⊆{1,2,...,n} (−1)|S|+1 ∣∣∣⋂ t∈S At ∣∣∣. Formula 4.15 For each positive integer n, the number of derangements of {1, 2, . . . , n} is n! n∑ r=0 (−1)r r! Formula 4.16 The number of permutations of {1, 2, . . . , n} with exactly k fixed points is n! k! n−k∑ r=0 (−1)r r! Möbius function For each positive integer n ≥ 1 with prime factorisation n = pe11 pe22 . . . perr , we define the Möbius function µ : Z+ → {−1, 0, 1} by µ(n) = 1 if n = 1, 0 if ei > 1 for any i ∈ {1, 2, . . . , r}, (−1)r if e1 = e2 = · · · = er = 1. Theorem 5.17 Taking the sum over all positive divisors d of n, ∑ d|n µ(d) = { 1 if n = 1 0 if n > 1. 1 of 7 Theorem 5.18 (Möbius Inversion Formula) Let f(n) and g(n) be functions with domain Z+ satisfying f(n) = ∑ d|n g(d). Then g(n) = ∑ d|n µ(d)f (n d ) = ∑ d|n f(d)µ (n d ) . Euler’s Totient function φ(n) is defined as: φ(n) = |{x : 1 ≤ x ≤ n and gcd(x, n) = 1}|. Theorem 5.19 For all integers n ≥ 1, n = ∑ d|n φ(d) and φ(n) = ∑ d|n µ(d) n d . The number of circular sequences of length n having period n based on an alphabet of size r is: Mr(n) = 1 n ∑ d|n µ(d)rn/d. The total number of circular sequences of length n based on an alphabet of size r is Tr(n) = ∑ d|n Mr(d). Theorem 6.22 (Dilworth’s Theorem) In a partially ordered set P , the minimum number of chains that partition P is equal to the size of a maximum antichain. Theorem 6.23 In a partially ordered set P , the minumum number of antichains that partition P is equal to the length of a maximum chain in P . Orbits, stabilizers and fixes: orb(x) = {g(x) : g ∈ G}; Stab(x) = {g ∈ G : g(x) = x}; fix(g) = {x ∈ X : g(x) = x}. Theorem 9.36 If y ∈ orb(x) then orb(y) = orb(x). Hence, the orbits of a group action on a set X form a partition of X. Theorem 9.40 (Orbit-Stabilizer Theorem) Suppose a finite group G acts on a set X. Then for each x ∈ X, |orb(x)| × |Stab(x)| = |G|. Theorem 10.42 (The Counting Theorem) Let G be a finite group acting on a finite set X. Then the number t of orbits of the action is given by the formula t = 1 |G| ∑ g∈G |fix(g)|. Geometric Series: ∞∑ r=0 tr = 1 1− t = (1− t)−1. Extended Binomial Theorem For any rational n: (1 + t)n = ∞∑ r=0 ( n r ) tr. For any rational n: ( n r ) = n(n− 1)(n− 2) . . . (n− r + 1) r! . If n is positive then ( −n r ) = (−1)r ( n+ r − 1 r ) . The EGF for selecting an object with unlimited repetition allowed is 1 + t+ t 2 2! + t 3 3! + · · · = et. The EGF for selecting an object at least once is t+ t 2 2! + t 3 3! + t 4 4! + · · · = et − 1. The EGF for selecting an object at least twice is t 2 2! + t 3 3! + t 4 4! + · · · = et − 1− t. The EGF for selecting an object an even number of times is 1 + t 2 2! + t 4 4! + t 6 6! + · · · = et+e−t 2 . 2 of 7 The EGF for selecting an object an odd number of times is t 1 1! + t 3 3! + t 5 5! + · · · = et−e−t 2 . The general method for finding a closed form solution for an r-th order linear recurrence relation ui+r = a1ui+r−1 + a2ui+r−2 + · · ·+ arui is: 1. Write the generating function of the sequence as a function by summing the equations g(t) − a1tg(t)− a2t2g(t)− a3t3g(t)− · · · − artrg(t) 2. Expand g(t) into partial fractions (possibly involving complex coefficients) 3. Use the binomial theorem to write g(t) as the sum of an infinite sequence of explicit terms. The Fibonacci numbers are given by F0 = F1 = 1, Fi+2 = Fi+1 + Fi. The nth Fibonacci number is Fn = (1 + √ 5)n+1 − (1− √ 5)n+1 2n+1 √ 5 . The generating function P (t) of p(n), the number of partitions of n, can be computed as P (t) = ∑ λ∈P t|λ| = ∞∏ i=1 1 1− ti . Theorem 14.61 The number of odd partitions of n equals the number of distinct partitions of n: po(n) = pd(n). Theorem 14.62 The number of partitions of n of length at most r is equal to the number of partitions of n with largest part at most r. Theorem 14.63 The number of partitions of n that are both odd and distinct is equal to the number of self-conjugate partitions of n. Theorem 14.64 The number of partitions of n into parts of consecutive sizes is the same as the number of positive odd divisors of n. Theorem 16.65 The sphere is not homeomorphic to the torus. Theorem 19.66 For any two surfaces S and T , we have χ(S#T ) = χ(S) + χ(T )− 2. Theorem 21.66 Suppose we have closed surfaces S and T , each represented by a single polygon with its edges glued together in pairs. Then we can build a new polygon representing the connected sum S#T by (i) breaking open each original polygon at some vertex on the boundary; and (ii) joining these two “broken” boundaries together to form a single larger polygon, with the same pairs of edges glued together as before. Theorem 21.67 The connected sum of two projective planes is homeomorphic to the Klein bottle. Process to get a word representation of a closed surface S 1. Represent S as a single polygon whose edges are joined together in pairs. (E.g. by triangulating and glueing triangles.) 2. Label the edges of the polygon with arrows and symbols to indicate how they are glued together. Each symbol must appear exactly twice. 3. Choose any starting vertex and any direction (either clockwise or anticlockwise), and read the symbols around the polygon from start to finish. Each time we encounter an arrow pointing forwards 3 of 7 with a symbol x, we write x. Each time we encounter an arrow pointing backwards with a symbol x, we write the “inverse” x−1. The resulting sequence of symbols and/or inverses is a word representation for S. Examples of surfaces and their words: a sphere aa−1; a torus ab−1a−1b; a projective plane aa; a Klein bottle aba−1b; a Klein bottle (obtained as the connected sum of two projective planes) aabb. Rules for changing a word without changing the corresponding surface (sketch) Rule 1: Relabelling edges Rule 2: Cycling edges Rule 3: Reversing the word Rule 4: Merging edges Rule 5: Cancelling xx−1 pairs Rule 6: Moving outside xx pairs Rule 7: Cycling inside xx−1 pairs Rule 7’: Jumping across xx−1 pairs Theorem 23.69 The surface (projective plane # torus) is homeomorphic to the surface (projective plane # Klein bottle). Theorem 24.70 (Classification of surfaces) Every closed surface is homeomorphic to either (i) the sphere (orientable, Euler characteristic 2); (ii) a connected sum of g ≥ 1 tori for some g ∈ Z+ (orientable, Euler characteristic 2− 2g); or (iii) a connected sum of g ≥ 1 projective planes, for some g ∈ Z+ (non-orientable, Euler characteristic 2− g). Moreover, all of these surfaces are distinct (that is, not homeomorphic to each other). Corollary 24.71 Two surfaces S and T are homeomorphic if and only if they have the same ori- entability and Euler characteristic. Theorem 25.74 Let G be a graph with p vertices v1, v2, . . . , vp and q edges. Then p∑ i=1 d(vi) = 2q. Corollary 25.75 Every graph contains an even number of odd vertices. Theorem 25.76 Let ∆ = d1, d2, . . . , dp be a sequence S of nonnegative integers with ∆ = d1 ≥ d2 ≥ · · · ≥ dp, and with p ≥ 2 and ∆ ≥ 1. Then S is graphical if and only if the sequence d2 − 1, d3 − 1, . . . , d∆+1 − 1, d∆+2, d∆+3, . . . , dp is graphical. Theorem 25.77 Two graphs are isomorphic if and only if their complements are isomorphic. Theorem 26.78 Let G be a graph and let u and v be distinct vertices in G. If there is a walk from u to v then there is a path from u to v. Theorem 26.79 A graph with p vertices and p− k edges has at least k components. Theorem 26.80 An edge e of a connected graph G is a bridge if and only if there is no cycle in G that contains e. 4 of 7 Theorem 26.80 A connected graph is Eulerian if and only if each