Program Overview

Course Overview

The course is an introductory program in algebraic and enumerative combinatorics. It aims to teach students how to apply techniques from algebra to solve enumeration problems and to use combinatorial methods to solve questions arising in other areas of mathematics.

Course Details

• Instructor: Sergi Elizalde
• Lectures: TuTh 10:00-11:50 in 201 Kemeny
• X-period: W 3:00-3:50
• Office Hours: Tu 11:50-12:30, Th 1:30-3:30, and by appointment
• Office: 332 Kemeny

Course Description

This course introduces students to algebraic and enumerative combinatorics. Students will learn how to apply algebraic techniques to solve enumeration problems and use combinatorial methods to address questions in other mathematical areas. Prior knowledge of combinatorics is not expected, but familiarity with linear algebra and finite groups is preferable.

Homework

• Problem Set 1, due on 10/11/07
• Problem Set 2, due on 10/25/07
• Problem Set 3, due on 11/8/07
• Problem Set 4, due on 11/27/07 The final exam will be handed out on Thursday, November 29, and due on Tuesday, December 4.

Recommended Texts

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

• [Aig] Martin Aigner, A Course in Enumeration, Graduate Texts in Mathematics 238, Springer, 2007
• [dM] Anna de Mier, Lecture notes for "Enumerative Combinatorics"
• [St] Richard P. Stanley, Topics in algebraic combinatorics, course notes, preliminary version Other useful books include:
  • [EC1] [EC2] Richard P. Stanley, Enumerative Combinatorics, Vols. I and II, Cambridge University Press, 1997/1999
  • [Wf] Herb Wilf, Academic Press, 1990
  • [vLW] J.H. van Lint, R.M. Wilson, A course in Combinatorics, Cambridge University Press, Cambridge, 1992
  • [Bo] Miklos Bóna, A walk through combinatorics, World Scientific, 2002
  • [FS] P. Flajolet, R. Sedgewick, Analytic Combinatorics
  • [Bg] Kenneth P. Bogart, Enumerative Combinatorics Through Guided Discovery
  • [BS] A. Björner, R. Stanley, A Combinatorial Miscellany

Topics

The course will cover the following topics:

• Fundamental coefficients. Sets and multisets. Compositions
  • [Aig] Sections 1.1, 1.2
  • [dM] Chapter 1
  • [EC1] Section 1.2
• Integer and set partitions. Stirling numbers. Permutations
  • [Aig] Sections 1.3-1.5
  • [dM] Chapter 3
  • [vLW] Chapter 13
  • [EC1] Section 1.3
• Inclusion-Exclusion
  • [Aig] Section 5.1
  • [dM] Chapter 2
  • [EC1] Sections 2.1-2.3
  • [vLW] Chapter 10
• Generating functions. Recurrences. Formal power series
  • [dM] Chapter 4
  • [Aig] Sections 2.1, 2.2, 3.1
  • [Wf] Section 2.1
  • [vLW] Chapter 14
• The symbolic method. Unlabelled structures. Ordinary generating functions
  • [dM] Chapter 5
  • [FS] Chapter 1
  • [Wf] Section 2.2
• Labeled structures. Exponential generating functions
  • [dM] Chapter 6
  • [Aig] Section 3.3
  • [FS] Chapter 2
  • [Wf] Section 2.3
• Partially ordered sets. Chains and antichains. Sperner’s theorem
  • [St] Section 4
• Group actions on boolean algebras
  • [St] Section 5
• Young diagrams and -binomial coefficients
  • [St] Section 6
  • [Aig] Section 1.6
• Enumeration under group action. Pólya's theorem
  • [St] Section 7
  • [Aig] Sections 6.1-6.3
• Young tableaux. The RSK algorithm
  • [St] Section 8
  • [EC2] Section 7.11
  • [BS] Section 4
• Lattices. Möbius Inversion
  • [Aig] Section 5.2
  • [EC1] Sections 3.3-3.8

Homework, Exams, and Grading

The course grade will be based on:

• Homework (40%)
• A final exam (25%)
• Class participation (10%)
• A final project (25%) Homework will consist of a problem set every two weeks. Collaboration is permitted, but students must write their solutions individually and mention the names of students they worked with and any books or articles used. The final exam will be a take-home exam, and no collaboration is permitted. Class participation involves attending lectures and asking and answering questions in class. The final project will consist of preparing a topic and presenting it in class, with students working in groups of 2 or 3.

Students with Disabilities

Students with disabilities enrolled in this course who 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.