Math 118. Combinatorics

Winter 2011

·         Instructor:         Sergi Elizalde

·         Lectures:           MWF 11:15 - 12:20 in Kemeny 004

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

·         Office Hours:     M 10:00-11:00, F 1:40-3:30

·         Office:               Kemeny 332

·         Email:               

·         Phone:               646-8191

Announcements

See below for the tentative schedule of student presentations.

The final exam will be handed out on Wednesday, Mar 9, and due on Monday, Mar 14.

 

Homework

·         Problem Set 1. Due on Wednesday, 1/19/11.

·         Problem Set 2. Due on Friday, 2/4/11.

·         Problem Set 3. Due on Friday, 2/18/11.

·         Problem Set 4. Due on Friday, 3/4/11.

Recommended texts

Even though there is no official textbook, much of the material will be taken from the second edition of Richard Stanley’s Enumerative Combinatorics, Volume 1. An online version of this new (not yet published) edition can be downloaded here.

Other topics will be taken from:

 

Tentative syllabus

 

Generating functions [FS Ch I-II; EC 1.1 and Ch 4-6; Wilf’s Generatingfunctionology, available here.]

·         How to count; formal power series [EC 1.1, Chapter 4 of these notes]

·         The symbolic method for unlabeled structures; ordinary generating functions; triangulations, lattice paths, compositions, plane trees [FS Ch I, Chapter 5 of these notes]

·         The symbolic method for labeled structures; exponential generating functions; the Lagrange inversion formula; labeled trees, set partitions, permutations, involutions, derangements, Stirling numbers [FS Ch II, EC Ch 5, Chapter 6 of these notes]

·         Examples of bivariate generating functions; statistics on Dyck paths [Notes]

·         Rational generating functions [EC 4.1]

·         Polynomials and quasi-polynomials [EC 4.3-4.4]

·         Algebraic generating functions [EC 6.1-6.2]

·         D-finite generating functions [EC 6.4]

Permutations [EC Ch 1, Bo Ch 1-3]

·         Cycles, left-to-right maxima, inversions [EC 1.3]

·         Descents, Eulerian numbers, major index, excedances [EC 1.4]

·         Geometric representations of permutations, increasing trees [EC 1.5]

·         Alternating permutations, Euler numbers [EC 1.6]

·         Permutations of multisets, q-binomial coefficients [EC 1.7]

Partitions and tableaux [EC 1.8, BS 2-6, EC Ch 7]

-          Generating functions for partitions [EC 1.8, BS 2]

-          Euler’s pentagonal theorem [EC 1.8]

-          Standard Young tableaux, the Hook-length formula [BS 4]

-          The RSK algorithm [EC 7.11, 7.13, Bo 7.1]

-          Increasing and decreasing subsequences [BS 6]

Introduction to pattern avoidance [Bo Ch 4]

-          Enumerative results, Wilf-equivalence classes, patterns of length 3 and 4 [Bo 4.1-4.4]

-          Asymptotic behavior, the Stanley-Wilf conjecture [Bo 4.5]

Student presentations

·         Fri, 2/25 – Scott, Möbius function and set partititons

·         Mon, 2/28 – Jonathan, Viennot’s geometric version of RSK

·         Mon, 2/28 – Dan, Connections with topology

·         Wed, 3/2 – Zach, Connections of Young tableaux and RSK with representation theory

·         Wed, 3/2 – Kassie, Min-max trees and the cd-index

·         Fri, 3/4 – Megan, Proof of the hook-length formula

·         Fri, 3/4 – Sarah, A combinatorial proof of the Lagrange Inversion Formula

·         Mon, 3/7 – Carter, Proof of Stanley-Wilf conjecture

·         Mon, 3/7 – Nathan, The transfer-matrix method

Homework, exams, and grading

The course grade will be based on the homework (30%), a presentation in class (20%), and a take-home final exam (50%).

Collaboration is encouraged on the homework, 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.

Possible student presentations

Here is a list of suggested topics for student presentations. Please let me know once you have chosen one. If you have some other topic in mind that you would like to talk about, feel free to discuss it with me. Each student should plan a 30-min presentation, more or less.

-          Proof of the hook-length formula [Novelli, Pak, Stoyanovskii, A direct bijective proof of the hook-length formula, Disc. Math. Comp Sci. 1 (1997), 53-67] OR [Greene, Nijenhuis, Wilf, A probabilistic proof of a formula for the number of Young tableaux of a given shape, Adv. in Math. 31 (1979) 104–109]  →   taken by Megan

-          Connections with representation theory [BS 5]  →   taken by Zach

-          Reduced decompositions [BS 7]

-          Möbius function and set partititons [BS 10]  →   taken by Scott

-          Hyperplane arrangements [BS 11]

-          Face numbers of polytopes [BS 12]

-          Connections with topology [BS 13]  →   taken by Danny

-          Proof of Stanley-Wilf conjecture [Bo 4.5] [Marcus, Tardos, Excluded permutation matrices and the Stanley-Wilf conjecture, J. Combin. Theory Ser. A 107 (2004), 153–160]   →  taken by Carter

-          Viennot’s geometric version of RSK [Section 3.6 of Sagan, The Symmetric Group, Springer]   →   taken by Jonathan

-          Combinatorial proof(s) of the Lagrange Inversion Formula [EC Theorem 5.4.2 (second and/or third proof). The proofs make some references to previous results in the chapter]  →   taken by Sarah

-          Bijective proof of the symmetry of the joint distribution of the inversion number and the major index on permutations [Foata, Schutzenberger, Major index and inversion number of permutations, Math. Nach. 83 (1978), 143-159] [EC1 pg. 41-42 gives an indirect proof]

-          Min-max trees and the cd-index [EC 1.6.3]  →   taken by Kassie

-          The transfer-matrix method [EC 4.7]  →   taken by Nathan

 

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.