# 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
• 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.

## 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.