Fall 2011
· 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
· Email:
Course description
This course is an introduction to algebraic and enumerative combinatorics. You will discover the beautiful interplay between algebra and combinatorics, learning 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. Here is the preliminary schedule of
presentations.
The final exam will be handed out on
Nov 21 and it 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 these three sources (the first two can be freely downloaded, and they cover most of what we will do):
- [dM] Anna de Mier, Lecture notes for "Enumerative Combinatorics". [Download]
- [St] Richard P. Stanley, Topics in algebraic combinatorics, course notes. [Download]
- [Aig] Martin Aigner, A Course in Enumeration, Graduate Texts in Mathematics 238, Springer, 2007.
Other interesting related books are:
- [EC1] [EC2]
Richard P. Stanley, Enumerative Combinatorics, Vols. I and II, Cambridge
University Press, 1997/1999. An online version of the new edition of Vol. I can
be downloaded here.
- [Mat] Jiri Matousek, Thirty-three
Miniatures, Mathematical and
algorithmic applications of linear algebra, AMS, Student Mathematical
Library 53.
- [Wf] Herb Wilf, Generatingfunctionology, Academic Press, 1990. Also
available online at http://www.math.upenn.edu/~wilf/DownldGF.html
- [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. The preliminary version of this
forthcoming book is available online at http://algo.inria.fr/flajolet/Publications/books.html
- [BS] A. Björner, R. Stanley, A Combinatorial Miscellany [Download].
Topics
Here is a tentative list of the topics that will be covered, together with the corresponding references. The main references for each topic are in boldface.
v Basic combinatorics.
·
Catalan numbers. 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.
v 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. Unlabeled 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.
v Topics in algebraic combinatorics.
·
Partially ordered sets. Chains and antichains.
Sperner’s theorem.
[St] Section 4.
·
Group actions on boolean
algebras.
[St] Section 5.
·
Young diagrams and q-binomial
coefficients.
[St] Section 6. [Aig]
Section 1.6.
·
Enumeration under group action. Counting orbits using
the Burnside Lemma. 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.
Homework, exams, and grading
The course grade will be based on
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. You have to mention on your
problem set the names of the students that you worked with, and also which
books or articles you used.
The final will be a take-home exam. You must work on the problems on your own. No
collaboration permitted in the exam.
The final project will consist of preparing a topic and presenting it in class. Students can work in pairs. Here are possible topics for the project.
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 me 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.