Links:    Home     Homework     Exams     Calendar     Syllabus

Math 184A: Combinatorics
Winter 2019, Lecture B, Prof. Tesler
Calendar

Updated 3/13/19

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.

Week 1
Jan. 7 Class overview

Ch. 1: Pigeonhole Principle (slides) [revised 1/7]

Jan. 9 3, 4.1-4.2, 2: Elementary Counting Problems (slides 1-23) [revised 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
Jan. 11
  • slides continued (23-38)
Week 2
Jan. 14
  • rest of slides

3.3, 4: Binomial coefficient identities (slides 1-12)
  • 3.3-4.1: Binomial coefficient identities, counting two ways, recursions
  • 4.3: Binomial series
Jan. 16
  • slides continued (12-28)
Jan. 18
  • rest of slides

5: Partitions (slides 1-7)
  • 5.1: Integer compositions
Week 3
Jan. 21 Martin Luther King, Jr. Holiday
Jan. 23
  • slides continued (slides 7-35)
  • 5.2: Set partition. Stirling number of the 2nd kind.
  • Bell numbers. Simplex locks. Surjections. More identities with Stirling numbers of the 2nd kind.
Jan. 25
  • rest of slides
  • 5.3: Integer partitions

6.1: Cycles in permutations (slides 1-4) [revised again 1/30]
  • Permutations: 1-line form, 2-line form, cycle form.
  • Multiplying permutations. Inverse of a permutation. Number of permutations by type.
  • Stirling numbers of the first kind.
Week 4
Jan. 28
  • slides continued (5-21)
  • Slides 22-31 are optional. Matrices of Stirling numbers in Linear Algebra. Generating functions for Stirling Numbers (optional, after covering Chapter 8).
Jan. 30
  • added more to an example, review + revised slides 18-19

7: Inclusion-Exclusion (slides 1-13) [revised 1/30]
  • Intro. Inclusion-exclusion formula.
Feb. 1
  • rest of slides
  • Derangements. Counting derangements. Counting surjections. Formula for Stirling number of 2nd kind S(n,k).

8.1: Ordinary Generating Functions (slides 1-5)
  • Ordinary generating functions: introduction
Campuswide deadline to drop without a "W"
Week 5
Feb. 4
  • slides 6-22: introduction, recursions
Feb. 6
  • slides 23-34: multiplying generating functions, Chu-Vandermonde identity
Feb. 8 Midterm
Week 6
Feb. 11
  • slides continued 35-46: structures, generating functions for counting integer partitions.
Feb. 13
  • slides continued 47-62: integer partitions; using generating functions to compute averages.
  • slides 63-64 are optional: generating functions for probability - read this if you took a probability class, such as Math 180A, 183, or 186.

18.1: Counting structures with Symmetry (slides 1-3)
Feb. 15
  • 18.1 slides continued 4-21 (slides 15-18 optional)
Campuswide deadline to drop with a "W"
Week 7
Feb. 18 Presidents' Day Holiday
Feb. 20
  • 18.1 continued: rest of slides

Feb. 22 9 and part of 10: Graph Theory (slides 1-18, 28-29; we'll do the skipped slides later) [revised 2/19]
  • 9 and 10.3: Graph Theory - basic definitions for graphs, vertices, edges, degrees, adjacency matrices, simple graphs, multigraphs, directed graphs, complete graphs, walks
Week 8
Feb. 25
  • slides continued (26-41): Subgraphs, walks/trails/paths/cycles, connected graphs, Hamiltonian paths, Eulerian trails
Feb. 27
  • rest of slides (42-51, 19-25): Hamiltonian paths, Eulerian trails. Adjustments for directed graphs. Unlabeled graphs, isomorphic graphs.

Mar. 1 10.1: Trees (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.
Week 9
Mar. 4
  • 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.
Mar. 6
  • rest of slides
  • 12.2: Classifying regular polyhedra
  • 11.1-11.2, 12.3: Bipartite graphs, graph colorings, chromatic number, Four Color Theorem

Mar. 8 8.1.2.1: Catalan numbers (slides 1-14)
  • 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
Mar. 11
  • rest of slides

Mar. 13 10.3: Counting walks using powers of the adjacency matrix (slides)

Mar. 15 Ranking and unranking (slides)
Week 11
Wed.
Mar. 20 		Final exam, 3-6 p.m.
 
Note: Additional information about some topics is available here:
Edward A. Bender & S. Gill Williamson, Foundations of Combinatorics with Applications, 2006 (free download).