Math 108. Topics in Combinatorics

• Instructor:         Sergi Elizalde

• Lectures:           MWF 11:15 - 12:20 in 244 Kemeny

• X-period:           Tu 12:00 - 12:50

• Office Hours:    MW 9:50-10:50, M 2:00-3:00, and by appointment

• Office:               332 Kemeny

• Email:               

• Phone:               646-8191

Homework

• Problem Set 1
• Problem Set 2
• Problem Set 3
• Final

Recommended texts

Some of the topics I will cover can be found in this two-volume book, which is a useful book to have if you are interested in combinatorics:

• Richard P. Stanley, Enumerative Combinatorics, Vols. I and II, Cambridge University Press, Cambridge, 1997/1999.

Other topics will be taken from:

• A. Björner, R. Stanley, A Combinatorial Miscellany [pdf].
• G. M. Ziegler, Lectures on Polytopes, Graduate Texts in Mathematics 152, Springer-Verlag, New York 1995.
• 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
• H. Wilf, Generatingfunctionology, Academic Press, Boston, MA, 1990. Also available online at http://www.math.upenn.edu/~wilf/DownldGF.html

Tentative list of topics

• Partitions.
  - Generating functions. Euler and Sylvester identities.
  - Euler's pentagonal theorem, Jacobi's identity.
  - Rogers-Ramanujan identities.
• P-partitions, partially ordered sets.
• Plane partitions, MacMahon's Theorem.
• Standard Young tableaux, hook-length formula.
• RSK algorithm, connections to representation theory.
• Increasing and decreasing subsequences, reduced decompositions.
• Tilings. Connections to plane partitions.
• The involution principle.
• Determinants, Gessel-Viennot formula.
• Ordinary and exponential generating functions. The symbolic method.
• Parking functions, inversions in trees.
• Catalan numbers, Dyck paths, triangulations, bijections. Generalized triangulations.
• Polytopes.
  - Face numbers.
  - Dehn-Somerville equations.
  - Cyclic polytopes, associahedron, permutahedron.
• Pattern-avoiding permutations.
  - Enumerative results, asymptotic behavior.
  - Statistics on restricted permutations.
  - Generalized patterns.

Homework, exams, and grading

The course grade will be based on the homework (30%) and a final exam (70%).

The homework will consist of a few problem sets. 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 if you used some books or articles that are not on the above list.

The final will be a take-home exam. You must work on the problems on your own. No collaboration permitted in the exam.

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 me 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.

Last modified on November 7 2006.