Math 273: Combinatorics I

(Graduate combinatorics, 1st semester)

Fall 2021


Instructor:

 Sam Hopkins (call me "Sam")
Office: Academic Support Bldg B - 214 (temporary)
E-mail: samuelfhopkins@gmail.com 

Classes:

 Mon-Wed-Fri, 12:10pm-1:00pm

Course format:

 Online (via Zoom: link will be emailed)

Office hours:

 By appointment (email me to set up a time)

Course content:

 This is the 1st semester of graduate combinatorics (click here for the 2nd semester).
We will study basic combinatorial objects (subsets, multisets, permutations, set/number partitions, compositions, graphs, trees, etc.), their enumeration, and additional structures they carry (such as partial orders). Roughly speaking we will cover the following:
  • Generating functions (ordinary and exponential)
  • Basic objects:
    • integer partitions and compositions,
    • subsets and multisets,
    • permutations,
    • set partitions,
    • the Catalan families
  • The 12-fold way
  • Combinatorial statistics and q-analogs:
    • q-binomial and q-multinomial coefficients,
    • permutation statistics (Mahonian and Eulerian)
  • Counting with signs:
    • the principle of inclusion-exclusion,
    • sign-reversing involutions
  • Determinantal/trace formulas:
    • matrix-tree theorem,
    • transfer matrix method
  • Partially ordered sets and lattices:
    • distributive lattices, Birkhoff's Theorem,
    • Möbius functions and Möbius inversion
But if there are any topics you are especially interested in (or not interested in), please let me know! I am happy to tailor this course to the interests of the students.

Prerequisites:

 Calculus, linear algebra, undergraduate algebra (groups, rings, fields)

Main texts:

 R.P. Stanley, Enumerative combinatorics, Vol. I, 2nd ed.
F. Ardila, Algebraic and geometric methods in enumerative combinatorics, Part 1.
Problems will come from Stanley, but the lectures will more closely follow Ardila.

Other nice sources:

 H. Wilf, generatingfunctionology.
B. Sagan, Combinatorics: the Art of Counting.

Class notes:

 Batch 1; Batch 2; Batch 3; Batch 4; Batch 5; Batch 6; Batch 7; Batch 8; Batch 9
(Change "_gray.pdf" to "_bw.pdf" for black & white.)

Grading:

 There will be 3 homework assignments for the semester.
The grading of the assignments will depend on both the quality and quantity of homework turned in. Beyond that, I expect you to show up to class and be engaged. Collaboration on the homework is encouraged, as long as each person understands the solutions, writes them up in their own words, and indicates with whom they collaborated.

Homework assignments:

 Problems will mostly be exercises from Stanley, plus some problems I come up with.
Assignment Due date Problems
HW #1 Friday, 10/1
 Click here
HW #2 Friday, 11/5 Click here
HW #3 Friday, 12/3 Click here