Instructor: Brendon Rhoades
Instructor's Email: bprhoades (at) math.ucsd.edu
Instructor's Office: 7250 APM
Instructor's Office Hours: 4:30-5:30pm MF, 10:30-11:30 am W, or by appointment
Lecture Time: 1:00-1:50pm MWF
Lecture Room: 2113 WLH
TA: Benjamin Greenberg
TA's Email: bcgreenberg (at) ucsd.edu
TA's Office: 6436 APM
TA's Office Hours: 2:00pm-4:00pm M
Discussion Time: 8:00-8:50pm Th
Discussion Room: 102 PETER
Final Exam Time: Monday, 12/9/2013, 11:30am - 2:29pm
Final Exam Room: TBA

Syllabus: Please read carefully.

Lectures:

9/27: Syllabus and administrivia. Chapter 1. The pigeon-hole principle. Application: There is a number in the sequence 9, 99, 999, ... divisible by 2013. Application: Given 5 points on a sphere, there is a closed hemisphere containing at least 4 of them.
9/30: Chapter 1. There are two people with the same number of friends on Facebook. The generalized pigeon-hole principle. Given 101 points in a 1x1 square, 26 of them have pairwise distance < 0.8. Chapter 2. The principle of (weak/strong) mathematical induction. Example: 1 + 3 + ... + (2n-1) = n^2. Example: There are 2^n subsets of [n].
10/2: Chapter 2. For n > 0, there are 2^{n-1} ways to tile a 1xn rectangle with tiles 1x1, 1x2, ... , 1xn. Two proofs of this: recursive/inductive and bijective. Chapter 3. Permutations. Linear orderings of sets with repeated entries.
10/4: Chapter 3. Sets and multisets. Multiset permutations. Strings over a finite alphabet. One-to-one, onto, and bijective functions. Examples of bijective enumeration using strings: counting length n lattice walks with no U-turns, counting subsets of [n].
10/7: Chapter 3. Strings without repreated letters. Binomial coefficients. Two proofs of {n \choose k} = {n \choose n-k}: formula manipulation and combinatorial. Example: Valid exam placements. Example: Northeast lattice paths.
10/9: Chapter 3. Choosing k-element multisets from an n-element set. Chapter 4. The binomial theorem and some corollaries. Two types of proof: formula manipulation and combinatorial. Pascal's Triangle. The alternating sum of binomial coefficients is zero. Two proofs: formula manipulation and a sign-reversing involution.
10/11: Chapter 4. The `diagonal-sum' property of Pascal's Triangle. The rows of Pascal's Triangle are unimodal. The Chu-Vandermonde convolution. The combinatorial definition of multinomial coefficients.
10/14: Chapter 4. The Multinomial Theorem. The Binomial Theorem for non-integer exponents. Chapter 5. Compositions and weak compositions.
10/16: Chapter 5. The number of compositions of n. Set partitions and equivalence relations. Arc diagrams. Stirling numbers of the second kind and Bell numbers and their recursions.
10/18: Chapter 5. Counting onto functions f: [n] --> [k]. Integer partitions. The partition numbers p(n) and p_k(n). Ferrers diagrams.
10/21: Chapter 5. The conjugate of a partition. p_k(n) equals the number of partitions of n with first part = k. "Self-conjugate = distinct odd parts". q(n) = p(n+1) - p(n). The type of a set partition.
10/23: Midterm 1.
10/25: Chapter 5. The number of set partitions of a fixed type. The Twelvefold Way. Anonymous course feedback.
10/28: Chapter 6. One-line notation for permutations in S_n. Two-line/bijection definition of permutations in S_n. Permutation multiplication. Cycle notation.
10/30: Chapter 6. The cycle type of a permutation. Counting permutations with a fixed cycle type. (Signless) Stirling numbers of the first kind and their recursion.
11/1: Chapter 6. The relationship between Stirling numbers of the first and second kinds: sS = Ss = I.
11/4: Chapter 6. The canonical cycle form of a permutation in S_n. The Foata map g: S_n ---> S_n (and its inverse). Application of the Foata map: c(n,k) equals the number of permutations p = p_1 ... p_n in S_n whose one-line notation has k left-to-right maxima. Another application: for any n > 1, the probability that a random permutation in S_n has 1,2 in the same cycle is 1/2.
11/6: Chapter 6. For any k <= n, the probability that 1 is an a k-cycle of a random permutation in S_n equals 1/n. Chapter 7. The Principle of Inclusion-Exclusion (a.k.a. the Sieve Formula). Derangements and derangement numbers.
11/8: Chapter 7. The number of derangements in S_n is the nearest integer to n!/e. Alternating sum formula for S(n,k). Alternate form of the PIE in terms of functions f,g: 2^S ---> \RR.
11/13: Midterm 2.
11/15: Chapter 8. Domino tilings of a 2xn rectangle and Fibonacci numbers. A formula for the Fibonacci numbers involving binomial coefficients. The Fibonacci recursion. Ordinary generating functions. The ordinary generating function of the Fibonacci numbers. An explicit formula for the Fibonacci numbers (involving the golden ratio!).
11/18: Chapter 8. Formal power series. Finding ordinary generating functions for some basic sequences. Adding and multiplying formal power series. Combinatorial interpretation of multiplying ordinary generating functions, with example.
11/20: Chapter 8. Another example on products of ordinary generating functinos. A few partition identities.
11/22: Chapter 8. Dyck paths. The Catalan numbers c_n = {2n \choose n}/(n+1) and their generating function. Catalania (triangulations, rooted plane trees, handshake patterns, 321-avoiding permutations).
11/25: Chapter 8. Composing formal power series and generating functions. The combinatorial interpretations of 1/(1-G(x)) and F(G(x)) when F(x) and G(x) are ordinary generating functions and G(0) = 0.
12/2: Chapter 8. Exponential generating functions. Examples: egfs of a_n = 1, n!. Egfs from recursions. The combinatorial interpretation of products of egfs (with example).
12/4: Chapter 8. Compositions of exponential generating functions: the exponential formula. Examples: Bell numbers, the cycle index formula for permutations.
12/6: Wrap up and review.

Homework Assignments:

Homework 1 (There's a to-be-corrected typo here; the homework is due either in class or at 5:00pm on 10/4/2013.)
Homework 2 (Problem 7 postponed to HW 3.)
Homework 3 (Problems 7 and 8 postponed to HW 4.)
Homework 4
Homework 5
Homework 6 (Problem 9 cancelled.)
Homework 7 (Problem 8 cancelled.)

Midterms:

Midterm 1
Solutions and comments
Score Distribution: 94, 80, 78, 76, 72, 71, 70, 70, 69, 69, 68, 66, 65, 65, 64, 63, 61, 61, 61, 59, 59, 59, 58, 55, 55, 51, 49, 46, 46, 45, 45, 42, 40, 39, 31, 30
Mean: 59.22, Standard Deviation: 14.07

Midterm 2
Solutions and comments
Score Distribution: 97, 92, 91, 90, 90, 86, 80, 80, 80, 78, 74, 72, 72, 71, 71, 70, 70, 65, 64, 60, 60, 57, 56, 55, 55, 52, 47, 46, 45, 45, 45, 43, 37, 36
Mean: 65.65, Standard Deviation: 17.24