Program Overview

Course Overview

The course is an introductory program in algebraic combinatorics, focusing on applying algebraic techniques to solve enumeration problems and utilizing combinatorial methods to address questions in other areas of mathematics.

Course Details

• Instructor: Sergi Elizalde
• Lectures: MWF 8:45 - 9:50 in 013 Bradley
• X-period: Th 9:00 - 9:50
• Office Hours: M 11:15-12:15, Th 2:00-4:00, and by appointment
• Office: 312 Bradley

Course Description

This is an introductory course in algebraic combinatorics. Students will learn how to apply techniques from algebra to solve enumeration problems and 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 finite groups is preferable.

Problem Sets

• Problem Set 1. Due on Friday, 10/14/05.
• Problem Set 2. Due on Friday, 10/28/05.
• Midterm. Due on Wednesday, 11/02/05, at 8:45 am.
• Problem Set 3. Due on Monday, 11/28/05.
• Final Exam. Due on Saturday, 12/03/05, at 11:00 am.

Recommended Texts

There is no textbook required for this course. Some useful books are:

• Richard P. Stanley, Enumerative Combinatorics, Vols. I and II, Cambridge University Press, Cambridge, 1997/1999.
• Herb Wilf, Generatingfunctionology, Academic Press, Boston, MA, 1990.
• 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, River Edge, NJ, 2002.
• P. Flajolet, R. Sedgewick, Analytic Combinatorics.
• Kenneth P. Bogart, Enumerative Combinatorics Through Guided Discovery.

Topics

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

• Catalan numbers. Dyck paths, triangulations. Bijections.
• Sets and multisets. Compositions.
• Integer and set partitions. Stirling numbers.
• Permutation statistics.
• Inclusion-Exclusion.
• Pattern-avoiding permutations.
• Generating functions. Recurrences. Formal power series.
• The symbolic method. Unlabelled structures. Ordinary generating functions.
• Labeled structures. Exponential generating functions.
• Partially ordered sets. The Sperner property.
• Enumeration under group action. Pólya's theorem.
• Young tableaux. The RSK algorithm.

Homework, Exams, and Grading

The course grade will be based on the homework (30%), a midterm (20%) and a final exam (20%), class participation (10%), and the final project (20%).

• The homework will consist of 3 problem sets. Collaboration is permitted, but you are not allowed to copy someone else's work.
• The midterm and final will be take-home exams. You must work on the problems on your own. No collaboration permitted in the exams.
• Class participation involves attending lectures, as well as asking and answering questions in class.
• For the final project, the students should work in groups of 2 or 3. Possible topics for the project will be suggested during the quarter. Each group will give a presentation in class.

Students with Disabilities

Students with learning, physical, or psychiatric 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 Disability Services office may be consulted to discuss appropriate implementation of any accommodation requested.