Math 188 - Algebraic Combinatorics (Fall 2022)

Lecture times and location: TuTh 11AM - 12:20PM, APM B412
Textbook: Bruce Sagan, Combinatorics: The Art of Counting, errata
Instructor: Steven Sam email
Instructor office hours:
- APM 7220, Tu 2-3PM
- Zoom, W 5-6PM, F 4-5PM
TA: Tianyi Yu email
Discussion time and location: Th 10-10:50AM, APM B402A
TA office hours:
- HSS 4073, Th 1-2PM
- Zoom, Sat 2-3PM
Syllabus: link
Discord server: see Canvas for invite link

I last taught this course in Spring 2021, and you can find all of the materials (except homework solutions) here: link
I will probably follow the content pretty closely, though there will be some cuts since this time we will lose 2 lectures for midterms.

Homework

Homework is due via Gradescope by 11:59PM on Saturdays.
Homework may be submitted up to 24 hours late, but receive a -25% penalty.
The lowest homework score is automatically dropped.

Homework 1 (due 10/8)
Homework 2 (due 10/15)
Homework 3 (due 10/29)
Homework 4 (due 11/5)
Homework 5 (due 11/19)
Homework 6 (due 11/30)
Homework 7 (not due, but provides practice for final exam)

Exam materials

Notes for course

Mostly everything we cover is in Sagan's book, but we'll go in a very different order.
The lectures will follow my own notes below fairly closely, but it is recommended to read Sagan's book for more examples and alternative explanations.

Notes (last updated 11/15/22)

Schedule


Sep 22	Linear recurrence relations (1.1) Proofs (1.2) Sagan: 3.6
Sep 27	Generalizations (1.3)
Sep 29	Formal power series, definitions (2.1) Sagan: 3.3

Oct 4	Binomial theorem (2.2)
Oct 6	Choice problems (2.3) Rational generating functions (2.4) Sagan: 3.1, 3.7
Oct 8	HW 1 due

Oct 11	Catalan numbers (2.5) 12-fold way, introduction (3.1) Compositions (3.2) Sagan: 1.8, 1.11 (Catalan numbers, but different approach), 3.4
Oct 13	Compositions (3.2) Words (3.3) Set partitions (3.4) Sagan: 1.2, 1.3, 1.4, 1.7
Oct 15	HW 2 due

Oct 18	Midterm 1
Oct 20	Set partitions (3.4) Integer partitions (3.5) Sagan: 1.6, 3.5

Oct 25	Integer partitions (3.5) 12-fold way, summary (3.6) Cycles in permutations (3.7) Sagan: 1.5, 1.6, 1.8
Oct 27	Cycles in permutations (3.7) Counting subspaces (3.8) Sagan: 1.5, 3.2
Oct 29	HW 3 due

Nov 1	Walks in graphs (4.1) Sagan: 1.9 Sagan doesn't quite cover this; extra reading can be found in Stanley, Enumerative Combinatorics 1, 2e, Section 4.7
Nov 3	Transfer matrix method (4.2) Products of exponential generating functions (5.1) Sagan: 4.3, 4.4 For transfer matrix method, see Stanley, Enumerative Combinatorics 1, 2e, Section 4.7
Nov 5	HW 4 due

Nov 8	Midterm 2
Nov 10	Products of exponential generating functions (5.1) Compositions of exponential generating functions (5.2) Sagan: 4.4, 4.5

Nov 15	Cayley's formula and Lagrange inversion (5.3) Möbius inversion (6.1) Sagan: 1.10 (different approach to Cayley's formula) Extra reading can be found in Stanley, Enumerative Combinatorics 2, Sections 5.3, 5.4
Nov 17	Möbius inversion (6.1) Boolean poset and inclusion-exclusion (6.2) Sagan: 2.1, 5.1, 5.4, 5.5
Nov 19	HW 5 due

Nov 22	Divisor poset and classical Möbius inversion (6.3) Group action basics (7.1) Sagan: 5.5, 6.1
Nov 24	Holiday - no class

Nov 29	Burnside's lemma (7.2) Redfield-Pólya theory (7.3) Sagan: 6.2, 6.3, 6.4
Nov 30	HW 6 due note unusual day of week
Dec 1	Proving congruences (7.4) Discussion of some further topics of study in algebraic combinatorics Sagan: 6.5

Dec 7	Final exam: 11:30AM-2:29PM in APM B412.