## Math 184A: Combinatorics Fall 2017, Lecture B, Prof. Tesler Calendar

### Updated 12/8/17

Note: This calendar is approximate and is subject to revision.
Chapter numbers are for the class textbook by Bòna.
Slides are posted in advance for most lectures, but are subject to revision.
Some lectures may be on the chalkboard.

 Week 0 Fri. Sep. 29 Class overview Ch. 1: Pigeonhole Principle (slides) Week 1 Oct. 2 3, 4.1-4.2, 2: Elementary Counting Problems (slides 1-17) 3: Multiplication rule, Addition rule, Cartesian products, Sequences, Bijections, Permutations, Binomial coefficients, Multiset permutations, Multinomial coefficients 2: Weak Induction (2.1), Strong Induction (2.2) 4: Binomial Theorem (4.1), Multinomial Theorem (4.2); the rest of Chapter 4 is in the next set of slides Intro to strong and weak compositions for the number of multisets and number of terms in the Multinomial Theorem Oct. 4 slides 18-31 Oct. 6 rest of slides (32-end) 3.3, 4: Binomial coefficient identities (slides 1-9) 3.3-4.1: Binomial coefficient identities, counting two ways, recursions 4.3: Binomial series Week 2 Oct. 9 slides 10-25 Oct. 11 rest of slides (26-end) 5: Partitions (revised slides 1-7) [revised 10/16] 5.1: Integer compositions Oct. 13 slides continued (revised slides 7-33) 5.2: Set partition. Stirling number of the 2nd kind. Bell numbers. Simplex locks. Surjections. More identities with Stirling numbers of the 2nd kind. Week 3 Oct. 16 rest of slides 5.3: Integer partitions Oct. 18 8.1: Ordinary Generating Functions (revised slides 1-22) [revised again 10/26] Ordinary generating functions: introduction, recursions Oct. 20 revised slides 23-31, 33-36: multiplying generating functions Week 4 Oct. 23 revised slides 32, 37-48: generating functions for counting integer partitions. Oct. 25 revised slides 49-61: integer partitions; using generating functions to compute averages. revised slides 62-63 are optional: generating functions for probability - read this if you took a probability class, such as Math 180A, 183, or 186. 6.1: Cycles in permutations (slides 1-3) [revised 10/22] Permutations: 1-line form, 2-line form, cycle form. Oct. 27 slides continued: Multiplying permutations. Inverse of a permutation. Number of permutations by type. Stirling numbers of the first kind. Slides 21-27 are optional, if you want to learn more about Stirling numbers of the first kind in generating functions and in linear algebra. Week 5 Oct. 30 7: Inclusion-Exclusion (slides 1-19) Intro. Inclusion-exclusion formula. Derangements. Counting derangements. Counting surjections. Formula for Stirling number of 2nd kind S(n,k). Nov. 1 rest of slides 18.1: Counting structures with Symmetry (slides 1-7) Nov. 3 Midterm    (seat map) Week 6 Nov. 6 18.1 continued: slides 7-19, 23 Nov. 8 18.1 continued: rest of slides + some on chalkboard Nov. 10 Veterans Day Holiday Week 7 Nov. 13 9 and part of 10: Graph Theory (slides 1-21) [revised 11/8] 9 and 10.3: Graph Theory - basic definitions for graphs, vertices, edges, degrees, adjacency matrices, simple graphs, multigraphs, directed graphs, isomorphic graphs, complete graphs, unlabeled graphs, isomorphic graphs Nov. 15 slides continued (22-39): unlabeled graphs, isomorphic graphs, subgraphs, walks/trails/paths/cycles, connected graphs, Hamiltonian paths, Eulerian trails Nov. 17 rest of slides: Hamiltonian paths, Eulerian trails. Adjustments for directed graphs. 10.1: Trees (slides 1-7) Week 8 Nov. 20 rest of slides 10.3: Counting walks using powers of the adjacency matrix (slides 1-11) Nov. 22 rest of slides 12, 11.1: Planar graphs, regular polyhedra, and graph colorings (slides 1-9) 12.1-12.2 Planar graphs and Euler's formula on a plane. Nov. 24 Thanksgiving Holiday Week 9 Nov. 27 slides continued (10-28): Euler's formula on a sphere. Transforming a coffee cup into a donut (video) Inequailities among V,E,F. K5 and K3,3 are nonplanar and characterize nonplanar graphs. Nov. 29 rest of slides 12.2: Classifying regular polyhedra 11.1-11.2, 12.3: Bipartite graphs, graph colorings, chromatic number, Four Color Theorem Dec. 1 8.1.2.1: Catalan numbers (slides 1-12) Catalan numbers, with applications to parentheses, trees, triangulations of polygons The slides cover Catalan numbers in a lot more depth than the textbook does. In case you are interested, Prof. Richard Stanley at MIT has compiled a list and a book of hundreds of other things counted by Catalan numbers Week 10 Dec. 4 rest of slides Dec. 6 Ranking and unranking (slides 1-17) Dec. 8 slides continued Week 11 Tue. Dec. 12 Final exam, 3-6 p.m.    (seat map)