Program Overview

---

Course Overview

The course is an introduction to algebraic and enumerative combinatorics, focusing on the interplay between algebra and combinatorics. It covers how to apply algebraic techniques to solve enumeration problems and how to use combinatorial methods to solve questions arising in other areas of mathematics.

Course Details

• Instructor: Sergi Elizalde
• Lectures: MWF 1:45-2:50 in Kemeny 105
• X-period: Th 1:00-1:50
• Office Hours: W 10:30-11:30, F 12:30-1:40, and by appointment
• Office: 332 Kemeny

Course Description

This course introduces students to the beautiful interplay between algebra and combinatorics. Students will learn how to apply algebraic techniques to solve enumeration problems and how to use combinatorial methods to solve questions arising in other areas of mathematics. No prior knowledge of combinatorics is expected, but some familiarity with linear algebra and group theory is preferable.

Homework

• Problem Set 1, due on 10/7/2011
• Problem Set 2, due on 10/21/2011
• Problem Set 3, due on 11/4/2011
• Problem Set 4, due on 11/21/2011 Student project presentations are scheduled for Nov 21, 28, and 30. Each student should speak for about 20 minutes.

Final Exam

The final exam will be handed out on Nov 21 and will be due on Nov 30, the last day of classes.

Recommended Texts

There is no textbook required for this course. Most of the material in the course will be taken from the following sources:

• Anna de Mier, Lecture notes for "Enumerative Combinatorics"
• Richard P. Stanley, Topics in algebraic combinatorics, course notes
• Martin Aigner, A Course in Enumeration, Graduate Texts in Mathematics 238, Springer, 2007 Other interesting related books are:
  • Richard P. Stanley, Enumerative Combinatorics, Vols. I and II, Cambridge University Press, 1997/1999
  • Jiri Matousek, Thirty-three Miniatures, Mathematical and algorithmic applications of linear algebra, AMS, Student Mathematical Library 53
  • Herb Wilf,
  • J.H. van Lint, R.M. Wilson, A course in Combinatorics, Cambridge University Press, Cambridge, 1992
  • Miklos Bóna, A walk through combinatorics, World Scientific, 2002
  • P. Flajolet, R. Sedgewick, Analytic Combinatorics
  • A. Björner, R. Stanley, A Combinatorial Miscellany

Topics

Here is a tentative list of the topics that will be covered, together with the corresponding references:

• Basic combinatorics
  • Catalan numbers. Sets and multisets. Compositions
  • Integer and set partitions. Stirling numbers. Permutations
  • Inclusion-Exclusion
• Generating functions
  • Recurrences. Formal power series
  • The symbolic method. Unlabeled structures. Ordinary generating functions
  • Labeled structures. Exponential generating functions
• Topics in algebraic combinatorics
  • Partially ordered sets. Chains and antichains. Sperner’s theorem
  • Group actions on boolean algebras
  • Young diagrams and -binomial coefficients
  • Enumeration under group action. Counting orbits using the Burnside Lemma. Pólya's theorem
  • Young tableaux. The RSK algorithm

Homework, Exams, and Grading

The course grade will be based on:

• Homework (50%)
• A final exam (25%)
• A final project (25%) The homework will consist of a problem set roughly every two weeks. Collaboration is permitted, but you are not allowed to copy someone else's work. The solutions must be written individually.

Students with Disabilities

Students with disabilities enrolled in this course that may need disability-related classroom accommodations are encouraged to make an office appointment to see the instructor before the end of the second week of the term. All discussions will remain confidential, although the Student Accessibility Services office may be consulted to discuss appropriate implementation of any accommodation requested.