Links:    Home     Homework     Calendar     Syllabus

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)
 
Note: Additional information about some topics is available here:
Edward A. Bender & S. Gill Williamson, Foundations of Combinatorics with Applications, 2006 (free download).