Math 8669: Combinatorial Theory (Spring 2018)

Lectures: MWF 11:15-12:05 in Vincent Hall 213.

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


Office Hours: (In Vincent Hall 251) TBA.

Course Description:

This is a continuation of Math 8668, taught by Prof. Pasha Pylyavskyy in Fall 2017. Topics include but are not necessarily limited to:
  • Exponential Generating Functions, Lagrange Inversion, and Species
  • Enumeration of Trees
  • Representation Theory of Finite Groups, especially the Symmetric Group
  • Symmetric Functions and their bases, partitions, and Young Tableaux
  • Coxeter Groups (time permitting)

  • The majority of the course will focus on Chapter 7 of Stanley's Enumerative Combinatorics Volume 2 (and related material), although we will also go through Chapter 5 of Volume 2.

    Prerequisites: Abstract algebra (groups, rings, modules, fields) as from 5285-5286 or 8201 and either Math 8668 or some combinatorics experience.

    Textbook:

    Enumerative Combinatorics Volume 2 by Richard Stanley.

    Recommended Texts:

  • Enumerative Combinatorics Volume 1. An online version is available here.
  • The Symmetric Group by Bruce Sagan
  • Linear Representations of Finite Groups by J. P. Serre (Chapters 1-3, 5)
  • Symmetric Functions and Hall Polynomials by Ian Macdonald
  • Young Tableaux by William Fulton
  • Generatingfunctionology by Herbert Wilf
  • Symmetric Functions, Schubert Polynomials and Degeneracy Loci (Chapter 1) by Laurent Manivel
  • Constructive Combinatorics by Dennis Stanton and Dennis White
  • 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:

  • Homework (100%): There will be 3 homework assignments, one due approximately every month. The first homework assignment is due on Monday February 12th.

    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.

    All homeworks will be 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.
  • Tentative Lecture Schedule (with related reading from Stanley EC2)

  • (W Jan 17) Lecture 1: Introduction to the Course and Review of Generating Functions (EC1, Sec 1.1)
  • (F Jan 19) Lecture 2: The Exponential Formula (5.1) and Review of Cycles (EC1, Sec 1.3)
  • (M Jan 22) Lecture 3: Applications of the Exponential Formula (Sec 5.2)
  • (W Jan 24) Lecture 4: More applications and the Cycle Index Poly (Sec 5.2)
  • (F Jan 26) Lecture 5: Tree Enumeration (Sec 5.3)


  • Homework assignments (tentative)
    Assignment Due date Problems from Stanley EC2,
    unless otherwise specified
    Homework 1 Monday Feb 12 Do at least six of the following thirteen suggested problems:
            EC1 Chapter 1: # 7, 21, 40, 41ab;
            EC2 Chapter 5: # 1ab, 3ab, 5, 7ab, 9ab, 10abcd, 15abcd, 39, 41abc