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.
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:
Combinatorial statistics and q-analogs:
Basic methods:
Determinantal formulas:
Partially ordered sets and lattices:
Prerequisites:
Calculus, linear algebra, undergraduate algebra (groups, rings, fields)
An online copy is available through the University Library.
An online copy is available through the University Library. 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
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. Homework (100%): There will be 4 homework assignments, due on Wednesdays approximately every three weeks. The first one will be due on October 4th with the remaining homeworks tentatively due on October 25th, November 15th, and December 13th. Grades will be based both on the quality and quantity of homework turned in.
I encourage collaboration on the homework, as long as each person understands the solutions, writes them up in their own words, and indicates on the homework page their collaborators. Homework should be brought to class, my office, or can be emailed to me, or left in my mailbox in the School of Math mailroom in Vincent Hall 107. Homework solutions should be well-explained as credit might not be given for an unsupported answer or a solution that comes directly from Stanley's volume with no other comment. Complaints about the grading should be brought to me.
Homeworks will often include a running list of problems of which I will suggest you do at least a certain number, although there will be occasional required problems if the material is fundamental. I will often update the problem sets with additional exercises as the course proceeds. Remember to check back periodically.
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:
- Integer partitions and compositions,
- Subsets and multisets,
- Permutations,
- Set partitions,
- the Catalan families
- q-binomial and q-multinomial coefficients,
- Permutation statistics (Mahonian and Eulerian)
- Pólya theory,
- Lagrange inversion,
- Inclusion-exclusion,
- Sign-reversing involutions
- Matrix-tree and BEST theorems,
- Lindström-Gessel-Viennot lemma,
- Permanent-determinant (Hafnian-Pfaffian) method,
- MacMahon ``master'' theorem,
- Transfer-matrix method
- Distributive lattices, Birkhoff's Theorem,
- Möbius functions and Möbius inversion,
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:
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.
Grading:
I encourage collaboration on the homework, as long as each person understands the solutions, writes them up in their own words, and indicates on the homework page their collaborators. Homework should be brought to class, my office, or can be emailed to me, or left in my mailbox in the School of Math mailroom in Vincent Hall 107. Homework solutions should be well-explained as credit might not be given for an unsupported answer or a solution that comes directly from Stanley's volume with no other comment. Complaints about the grading should be brought to me.
Homeworks will often include a running list of problems of which I will suggest you do at least a certain number, although there will be occasional required problems if the material is fundamental. I will often update the problem sets with additional exercises as the course proceeds. Remember to check back periodically.