## Math 8668: Combinatorial Theory I (Fall 2023)

Lectures: MWF 2:30 - 3:20 pm in Vincent Hall 209.

Instructor: Gregg Musiker (musiker "at" umn.edu)

Office Hours: (In Vincent Hall 109A) Mondays and Wednesdays 3:35 - 4:25 pm; Fridays 1:25 - 2:15 pm; or by appointment.

## Course Description:

This is the first semester of the two-semester Math 8668-69 sequence; Math 8669 will be taught by Daoji Huang in Spring 2024.

We will study basic combinatorial objects (e.g., subsets, multisets, permutations, set/number partitions, compositions, graphs, trees), their enumeration, and other properties, such as graphical or partially ordered set structures. Topics include but are not necessarily limited to:

• Generating functions (ordinary and exponential)

• Basic objects:
• Integer partitions and compositions,
• Subsets and multisets,
• Permutations,
• Set partitions,
• the Catalan families
• Combinatorial statistics and q-analogs:
• q-binomial and q-multinomial coefficients,
• Permutation statistics (Mahonian and Eulerian)
• Basic methods:
• Pólya theory,
• Lagrange inversion,
• Inclusion-exclusion,
• Sign-reversing involutions
• Determinantal formulas:
• Matrix-tree and BEST theorems,
• Lindström-Gessel-Viennot lemma,
• Permanent-determinant (Hafnian-Pfaffian) method,
• MacMahon ``master'' theorem,
• Transfer-matrix method
• Partially ordered sets and lattices:
• Distributive lattices, Birkhoff's Theorem,
• Möbius functions and Möbius inversion,
• Prerequisites: Calculus, linear algebra, undergraduate algebra (groups, rings, fields)

## Textbook:

Enumerative Combinatorics Volume 1 (second edition) by Richard Stanley.

An online copy is available through the University Library.

## Secondary Textbook:

Combinatorics: The Art of Counting by Bruce Sagan.

An online copy is available through the University Library.

## Other Recommended Texts:

• Algebraic and geometric methods in enumerative combinatorics by Federico Ardila
• Generatingfunctionology by Herbert Wilf
• Constructive Combinatorics by Dennis Stanton and Dennis White
• Bijective Combinatorics by Nick Loehr
• ## Computer algebra systems (very helpful, but not essential):

Sage, Maple, Mathematica, available in Math computer labs, and also (for CSE undergrads) for free downloads at CSE Labs. Some systems available on the Web, in particular the Sage Cell Server and Wolfram Alpha, are sufficient.

Participation in class is encouraged. Please feel free to stop me and ask questions during lecture. Otherwise, I might stop and ask you questions instead.