Fall 2004

Lectures: |
TR 1:40-3:00pm in Wellman 211 |

Office hours: Tuesday after class, Friday 2-3pm | |

Instructor: |
Anne Schilling, Kerr Hall 578, phone: 754-9371, anne@math.ucdavis.edu |

Text: |
Richard P. Stanley, "Enumerative Combinatorics, Volume I" Cambridge Studies in Advanced Mathematics 49, Cambridge University Press 1997. |

Prerequisites: |
MAT 145, 150 or equivalent; or permission by instructor |

Grading: |
Homework 50%; Final 50%
Homework assignment (due on November 4) Final exam: Wednesday December 15, 10:30-12:30 Problems will be assigned regularly in class. Students are expected to work on these problems, though they are not collected for grading. Instead, some of the assigned problems will be on the final exam (the exam will also contain new problems). Whereas students are encouraged to work together on the assigned problems, it is expected that each student works independently on the graded homework assignment. |

Web: |
http://www.math.ucdavis.edu/~anne/FQ2004/245.html |

I. Introduction to counting (permutation statistics, twelvefold way)

II. Inclusion-Exclusion

III. Order (posets, lattices, Moebius inversion)

IV. Generating functions

The sequel to this course MAT 246 will cover symmetric functions and polytopes.

- Sept. 30: Motivation; example of a non-combinatorial and combinatorial proof (ch 1.1)
- Oct. 5: Sets and multisets; basic counting (ch 1.2)
- Oct. 7: Permutations; cycle type; Stirling numbers of first kind (ch 1.3)
- Oct. 12: Inversions; descents; major index; q-binomial coefficient (ch 1.3)
- Oct. 14: q-binomial coefficient (continued); partitions; Euler's pentagonal number theorem
- Oct. 19: Twelvefold way (ch. 1.4)
- Oct. 21: Generating functions for partitions with restricted parts
- Oct. 26: Inclusion-Exclusion, derangements (ch 2.1, 2.2)
- Oct. 28: Examples for inclusion-exclusion: descents, Euler's Phi function; permutations with restricted positions (ch 2.2, 2.3)
- Nov. 2: Sign-reversing involutions (ch 2.6)
- Nov. 4: Partially ordered sets (ch 3.1)
- Nov. 9: Lattices (ch 3.3)
- Nov. 12: discussion of homework; lattices continued
- Nov. 16: Incidence algebra (ch. 3.6)
- Nov. 23: Moebius inversion (ch. 3.7, 3.8)
- Nov. 30: Euler characteristic (ch. 3.8), Catalan numbers
- Dec. 2: Rational generating functions (ch. 4.1), P-partitions (ch. 4.5)
- Dec. 7: P-partitions, generating functions (ch. 4.5)
- Dec. 9: Reciprocity, relation between major index and inversions