Math 184A: Combinatorics
Fall 2017

Instructor: Brendon Rhoades
Instructor's Email: bprhoades (at) math.ucsd.edu
Instructor's Office: 7250 APM
Instructor's Office Hours: 10:00-10:50am MWF, or by appointment.
Lecture Time: 11:00-11:50am MWF
Lecture Room: B-210 MANDE
TA: Daniël Kroes and Kyle Meyer
TA's Email: dkroes (at) ucsd.edu abd kpmeyer (at) ucsd.edu
TA's Office: 6414 APM (Kroes) and 6444 APM (Meyer)
TA's Office Hours: 3:00-5:00pm M, 2:00-4:00pm Tu (Kroes) and 1:00-3:00pm W, 12:00-2:00 pm F (Meyer)
Discussion Time: 8:00-8:50am Tu (A01), 9:00-9:50am Tu (A02), 10:00-10:50am Tu (A03), 11:00-11:50am Tu (A04)
Discussion Room: 5402 APM
Final Exam Time: Tuesday, 12/12/2017, 11:30am - 2:29pm
Final Exam Room: TBA

Syllabus: Please read carefully.

Lectures:

9/29: Administrivia. Chapter 1. The Pigeonhole Principle. Example: At a party with 100 people, there are two people with the same number of friends. Example: Given five points in a square S of side length 1, two of these points have distance < 0.8. Example: There is a number in the sequence 5, 55, 555, ... which is divisible by 2017.
10/2: Chapter 3. Elementary counting problems. Permutations. Sets and multisets. Multiset permutations. Counting strings over an alphabet, perhaps with repetition not allowed. An n-element set has 2^n subsets.
10/4: Chapter 3. Functions: injections, surjections, bijections. Bijection Principle: If X and Y are sets and f: X to Y is a bijection, then |X| = |Y|. Example: There are 3^n pairs (A,B) of subsets of [n] such that A is a subset of B. Counting k-element subsets of an n-element set. Binomial coefficients.
10/6: Chapter 3. More on binomial coefficients. Counting valid exam placements (40 day term, 5 exams, no two exams < 3 days apart) using the Bijection Principle. The number of k-element multisets drawn from an n-element set is {n+k-1 choose k} = {n+k-1 choose n-1}. "Stars and bars" argument illustrating this fact.
10/9: Chapter 4. The Binomial Theorem. Failure of the Binomial Theorem in non-commuting variables. The alternating sum of binomial coefficients vanishes. Pascal's Recursion. The Hockey Stick Property of Pascal's Triangle. (sum over k) k * {n choose k} = n * 2^(n-1). Proof by formulas vs. combinatorial proof.
10/11: Chapter 4. The Chu-Vandermonde convolution. Unimodality of binomial coefficients. Multinomial coefficients and the Multinomial Theorem. Definition of {n choose k} when n is not an integer; application to the Taylor series of (1 + x)^n around x = 0. Chapter 5. Compositions.
10/13: Chapter 5. The number of compositions of n. The number of compositions of n with k parts. Weak compositions. The number of weak compositions of n with k parts. Set partitions. Bell numbers. Stirling numbers of the second kind. Recursion for Stirling numbers of the second kind.
10/16: Chapter 5. Recursion for the Bell numbers. The number of surjections from [k] to [n] is k!*S(n,k). Integer partitions. The partition numbers p(n) and p_k(n). Ferrers diagrams. Conjugation of integer partitions.
10/18: Chapter 5. p_k(n) is the number of partitions of n with largest part k. Self-conjugate partitions. The number of self-conjugate partitions of n equals the number of partitions of n with distinct odd parts.
10/20: Midterm 1.
10/23: Chapter 6. One-line, functional, and cycle notation for permutations. Permutation multiplication in functional and cycle notation. Anonymous course feedback.
10/25: Chapter 6. The cycle type (a_1, ... , a_n) of a permutation in S_n. The number of permutations of cycle type (a_1, ... , a_n). The Stirling numbers of the first kind s(n,k) and their signless versions c(n,k). Example: n = 4. Recursion for c(n,k).
10/27: Chapter 6. (sum over k >= 0) c(n,k) x^k = x (x+1) ... (x+n-1). Relationship between Stirling numbers of the first and second kinds via infinite matrices. Chapter 7. Statement of the Principle of Inclusion-Exclusion.
10/30: Chapter 7. Applications of Inclusion-Exclusion. Counting derangements in S_n (Blind Coatcheck Problem). Formula for S(n,k). Closed vs. not-closed formulas. Version of PIE for functions 2^[n] --> R.
11/1: Chapter 8. Counting domino tilings. Fibonacci numbers. Generating functions T(x) of the Fibonacci numbers. Explicit formula from generating function (and partial fractions) involving the Golden Ratio.
11/3: Chapter 8. The ordinary generating function of a real sequence. Examples: a_n = 3^n, a_n = n^2. Finding explicit formulas for recursively defined sequences with generating functions. The ring of formal power series (with real coefficients): addition and multiplication of generating functions.
11/6: Chapter 8. Combinatorial interpretation for multiplying two ordinary generating functions A(x), B(x). Combinatorial interpretation of 1/(1 - A(x)) when A(0) = 0.
11/8: Chapter 8. Partition identities. Euler's Formula. Proof that the number of partitions of n with distinct parts equals the number of partitions of n with only odd parts using generating functions.
11/13: Chapter 8. Exponential generating functions. Getting exponential generating functions from recursions. Combinatorial interpretation of the product C(x) = A(x)B(x) of two exponential generating functions.
11/15: Chapter 8. Interpretation of exp(A(x)), where A(x) is an exponential generating function. Chapter 16. Definition of a poset. Boolean poset, divisibility poset, chain poset, antichain poset.
11/17: Midterm 2.
11/20: Chapter 16. Chains and antichains in poset. Chain covers of posets. Dilworth's Theorem (and proof). Examples.
11/22: Gobble.
11/24: Gobble.
11/27: Chapter 16. Intervals in posets. The incidence algebra I(P) of a finite poset P. Multiplication in I(P). Representation of I(P) in terms of upper triangular matrices. The delta and zeta functions in I(P). Chains and multichains. The zeta function and multichain counting.
11/29: Chapter 16. The zeta/delta functions and chain counting. The Moebius function in I(P). The Moebius function is the inverse of the zeta function in I(P). The Moebius function of the chain, the Boolean poset, and the divisibility poset.
12/1: Chapter 16. The Moebius function of a product of posets. The Moebius inversion formula. Examples: chains (partial sums) and the Boolean poset (inclusion-exclusion). The definition of a lattice. Join and meet. Examples and non-examples.
12/4: Chapter 16. The Boolean poset as a lattice. The divisibility poset as a lattice. The lattice of set partitions. Statement and proof of Weisner's Theorem.
12/6: Chapter 16. Application of Weisner's Theorem to the Moebius values of partition lattices. Catalan numbers. Dyck paths, triangle poset antichains, 321-avoiding permutations, polygon triangulations, noncrossing set partitions, handshake patterns: Catalania.


Lecture Notes:

Lecture 1.
Lecture 2.
Lecture 3.
Lecture 4.
Lecture 5.
Lectures 6/7.
Lecture 8.
Lectures 9-11.
Lecture 12.
Lectures 13-15.
Lectures 16-18.
Lectures 19-20.
Lectures 21-22.
Lectures 23-24.


Homework Assignments:

Homework 1, due 10/4/2017.
Homework 2, due 10/11/2017. (Problem 7 postponed to next week)
Homework 3, due 10/18/2017.
Homework 4, due 11/1/2017.
Homework 5, due 11/8/2017. (Problem 7 postponed to next week)
Homework 7, due 11/29/2017. (Warning!! A previous version of this assignment said the due date is 12/6 -- it really is 11/29.)

Midterms:

Midterm 1. (Out of 100)
Score Distribution: 100, 100, 100, 99, 99, 97, 97, 96, 95, 95, 94, 93, 92, 90, 90, 90, 87, 85, 85, 85, 85, 82, 81, 80, 79, 79, 78, 78, 78, 78, 76, 76, 75, 74, 73, 73, 73, 72, 71, 71, 70, 70, 69, 69, 69, 69, 68, 68, 68, 67, 67, 67, 65, 65, 65, 65, 65, 65, 64, 63, 63, 63, 62, 62, 61, 61, 60, 60, 60, 60, 60, 60, 59, 58, 58, 58, 58, 58, 57, 56, 55, 54, 54, 53, 53, 53, 52, 51, 51, 51, 50, 50, 50, 50, 50, 50, 49, 48, 48, 47, 47, 46, 45, 45, 45, 45, 45, 44, 44, 43, 43, 43, 42, 42, 41, 40, 39, 38, 38, 38, 38, 35, 34, 32, 31, 31, 29, 28, 28, 27, 27, 25, 22, 21, 20, 10.

Midterm 2. (Out of 105)
Score Distribution: 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 103, 103, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 99, 98, 98, 95, 95, 95, 95, 95, 95, 95, 95, 95, 94, 94, 94, 93, 93, 90, 90, 90, 90, 90, 90, 89, 89, 89, 89, 88, 88, 88, 88, 88, 87, 87, 85, 85, 85, 85, 85, 84, 84, 83, 80, 80, 80, 80, 80, 79, 79, 78, 78, 78, 78, 76, 76, 75, 75, 75, 75, 75, 75, 75, 74, 73, 73, 73, 73, 73, 72, 71, 70, 70, 69, 69, 68, 67, 67, 66, 66, 65, 65, 65, 63, 58, 57, 57, 56, 55, 55, 51, 49, 48, 46, 46, 46, 45, 45, 44, 42, 38, 25, 25, 22, 22, 20.