Week 0 
Fri. Sep. 29 
Class overview
Ch. 1: Pigeonhole Principle
(slides)

Week 1 
Oct. 2 
3, 4.14.2, 2: Elementary Counting Problems
(slides 117)

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 

Oct. 6 
3.3, 4: Binomial coefficient identities
(slides 19)

3.34.1: Binomial coefficient identities, counting two ways, recursions

4.3: Binomial series

Week 2 
Oct. 9 

Oct. 11 
5: Partitions
(revised slides 17)
[revised 10/16]

5.1: Integer compositions

Oct. 13 

slides continued (revised slides 733)

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 122)
[revised again 10/26]

Ordinary generating functions: introduction, recursions

Oct. 20 

revised slides 2331, 3336: multiplying generating functions

Week 4 
Oct. 23 

revised slides 32, 3748: generating functions for counting integer partitions.

Oct. 25 

revised slides 4961: integer partitions; using generating functions to compute averages.

revised slides 6263 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 13)
[revised 10/22]

Permutations: 1line form, 2line 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 2127 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: InclusionExclusion
(slides 119)

Intro. Inclusionexclusion formula. Derangements. Counting derangements. Counting surjections. Formula for Stirling number of 2nd kind S(n,k).

Nov. 1 
18.1: Counting structures with Symmetry
(slides 17)

Nov. 3 
Midterm
(seat map)

Week 6 
Nov. 6 

18.1 continued: slides 719, 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 121)
[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 (2239): 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 17)

Week 8 
Nov. 20 
10.3: Counting walks using powers of the adjacency matrix
(slides 111)

Nov. 22 
12, 11.1: Planar graphs, regular polyhedra, and graph colorings
(slides 19)

12.112.2 Planar graphs and
Euler's formula on a plane.

Nov. 24 
Thanksgiving Holiday

Week 9 
Nov. 27 

slides continued (1028):

Euler's formula on a sphere.

Transforming a coffee cup into a donut (video)

Inequailities among V,E,F.

K_{5} and K_{3,3} are nonplanar and characterize nonplanar graphs.

Nov. 29 

rest of slides

12.2: Classifying regular polyhedra

11.111.2, 12.3: Bipartite graphs, graph colorings, chromatic number, Four Color Theorem

Dec. 1 
8.1.2.1: Catalan numbers
(slides 112)

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 

Dec. 6 
Ranking and unranking
(slides 117)

Dec. 8 

Week 11 
Tue. Dec. 12 
Final exam, 36 p.m.
(seat map)
