MA 614, Spring 2011
Tentative Schedule

NOTE: This schedule will likely change throughout the semester and will be updated online as changes occur.

For each day there is an assigned reading; you are expected to complete the reading for each day before class. In this schedule, ``EC 2-5'' refers to pages 2-5 of Stanley's Enumerative Combinatorics Vol 1, 2nd edition.

Jan 12:

Syllabus preview.
Discussion: What is Enumerative Combinatorics?

Jan 14:

Reading: EC 9-11, stop at point 5.
Discussion: The Fibonacci recurrence and integer compositions.

Jan 17:

MLK Holiday

Jan 19:

Reading: EC 21, middle paragraph only. EC 23-24, only first three lines of 24.
Discussion: Permutations and Combinations.

Jan 21:

Reading: EC 24, stop at connection to compositions.
Discussion: Pascal's triangle, the binomial recurrence, and the binomial theorem.

Jan 24:

Reading: EC 24-26, only first half of 26 (stop after the second direct proof).
Discussion: Binomial coefficients and integer compositions; multisets.

Jan 26:

Reading: EC 27-28
Discussion: Multinomial coefficients and lattice paths.

Jan 28:

Reading: http://en.wikipedia.org/wiki/Catalan_number, read the sections titled ``Properties,'' ``Applications in Combinatorics,'' and the second proof in the section ``Proof of the formula.''
Discussion: Catalan numbers.

Jan 31:

Reading: EC 11-14, stop after Example 1.1.7.
Discussion: Ordinary and Exponential Generating Functions.

Feb 2:

Reading: EC 15-16, start at the last paragraph of page 15 and stop before Example 1.1.11.
Discussion: Composition of generating functions, the generalized binomial theorem, and formal derivatives.

Feb 4:

Reading: EC 17-18 and 20, on 17-18 read only Examples 1.1.12 and 1.1.13 and on 20 stop before point 3.
Discussion: Ordinary Generating Functions: Linear recurrences, formal differentiation, and compositions.

Feb 7:

Reading: EC 29 and 32-33 - on page 32, only read Lemma 1.3.6 and its proof.
Discussion: The Symmetric Group $\mathfrak{S}_n$, word/two-line notation and cycle notation, cycle structure, and (signless) Stirling numbers of the first kind.

Feb 9:

Reading: EC 33-35, read only Prop 1.3.7, its first proof and fourth proof, and Example 1.3.9.
Discussion: ``The Local/Global Paradigm'' and (signless) Stirling numbers of the first kind.

Feb 11:

Reading: EC 35-37, read the subsection regarding inversions.
Discussion: Permutation inversions and $q$-analogues.

Feb 14:

Reading: EC 62-64, on page 62 skip the second passage that has to do with descent sets; skip both proofs of Prop 1.7.1 (we will prove a special case in class); read Prop 1.7.2 and its proof.
Discussion: $q$-multinomial polynomials, Gaussian polynomials, and multiset permutation inversions.

Feb 16:

Reading: EC 65 and 67, omit proof of Prop 1.7.3 (we will give a straightforward proof in class).
Discussion: Gaussian polynomials, partitions, and lattice paths.

Feb 18:

Reading: EC 79-83, on page 83 stop after the proof of Entry 3.
Discussion: The twelvefold way, Bell numbers, and Stirling numbers of the second kind.

Feb 21:

Reading: EC 83-84 and 87-88, on page 87, start with the proof of Entry 4.
Discussion: The twelvefold way, continued.

Feb 23:

Reading: EC 68 and 69-70 and 74, on page 68 skip Prop 1.8.1, on page 69 start with Prop 1.8.4, on page 70 skip the second proof of Prop 1.8.5, on page 74 only read equation (1.87) and the comments following it.
Discussion: Partition Identities and the $q$-binomial theorem.

Feb 25:

Reading: None.
Discussion: On permutations with restricted cycle type - Derangements and Involutions in $\mathfrak{S}_n$.

Feb 28:

Reading: None.
Discussion: Exponential Generating Functions

Mar 2:

Catch-up day.
EXAM: Distribute take-home midterm exam. The midterm exam covers material through Partition Identities.

Mar 4:

Reading: None.
Discussion: Examples of Exponential Generating Functions.

Mar 7:

Reading: None.
Discussion: Tree Counting and Cayley's theorem
EXAM: Midterm exam due

Mar 9:

Reading: None.
Discussion: The exponential formula and the Lagrange Inversion Formula.

Mar 11:

Reading: EC 38 (read only first paragraph) and 39 (read only second half of page, beginning after the note) and 40-41 (read on page 40 starting at Prop 1.4.4).
Discussion: Eulerian numbers.

Spring Vacation: March 14-18

Mar 21:

Reading: http://en.wikipedia.org/wiki/Inclusion-exclusion_principle, read through the end of the Example. NOTE: This is equivalent to section 2.1 in EC.
Discussion: The principle of inclusion-exclusion.

Mar 23:

Reading: EC 240-241, and 121 Exercise 1.49, on page 241 stop at the section that is ``a more complicated example'' and on page 121 just read the Exercise as if the problems were theorem statements.
Discussion: Sign-reversing involutions, unimodal sequences, and log-concave sequences.

Mar 25:

Reading: EC 246-248, skip the proof of Theorem 2.7.1, we will prove a special case in class.
Discussion: The Gessel-Viennot theorem.

Mar 28:

Reading: EC 275-277, stop at definition of isomorphic.
Discussion: Posets.

Mar 30:

Reading: EC 277-280.
Discussion: Posets.

Apr 1:

Reading: EC 281-282.
Discussion: New posets from old.

Apr 4:

Reading: EC 283-287.
Discussion: Lattices.

Apr 6:

Reading: EC 288-289, stop after proof of Theorem 3.4.1.
Discussion: Distributive lattices.

Apr 8:

Reading: EC 297-299, stop after discussion of $(\zeta -1)$.
Discussion: The incidence algebra of a poset and the zeta function.

Apr 11:

Reading: EC 301-302 and 299 and 305, on 299 only read the first justification regarding $2-\zeta$ and on 305 only read Prop 3.8.5 and its proof.
Discussion: Möbius functions and the Möbius inversion formula.

Apr 13:

Reading: EC 303-304 and 312, on 304 stop after Example 3.8.3 and on 312 stop just before Theorem 3.9.2.
Discussion: The product theorem and Möbius algebras for lattices.

Apr 15:

Reading: EC 312-314, on 312 start with Cor 3.9.3.
Discussion: Weisner's theorem and the crosscut theorem.

Apr 18:

Reading: EC 315.
Discussion: The Möbius function of a semi-modular lattice.

Apr 20:

Reading: EC 293 and 332-334, on 293 read only the definition of linear extension given in the second to last paragraph, on 332 skip the NOTE regarding simplicial complexes, and on page 334 skip Theorem 3.13.3.
Discussion: Rank selection.

Apr 22:

Reading: EC 335.
Discussion: $R$-labelings.

Apr 25:

Reading: EC 336-337.
Discussion: Examples of $R$-posets.

Apr 27:

Reading: EC 350 and 351-352, on 350 only read the definition of Eulerian at the top and on 351-352 only read from Lemma 3.16.3 through Cor 3.16.6.
Discussion: Eulerian posets and duality.

Apr 29:

Catch-up day.
EXAM: Final exam distributed - due May 4th at noon to my office.