Instructor: Brendon Rhoades
Instructor's Email: bprhoades (at) math.ucsd.edu
Instructor's Office: 7250 APM
Instructor's Office Hours: By appointment
Lecture Time: 12:00-12:50pm MWF
Lecture Room: 2402 APM


Grading:

Homework: 100%

Textbook: We will loosely follow Enumerative Combinatorics, Volume 1, by Richard Stanley. This is freely available online here.

Lectures:

9/28: Administrivia. Counting domino tilings of a (2 x n) strip. Binomial coefficient sum formula. Recursion. Generating function. Golden ratio formula.
10/1: Sets, subsets, binomial coefficients (generating functions), multisets, stars/bars, permutations, strong and weak Bruhat order, multiset permutations, compositions.
10/3: Permutation statistics. cyc and Stirling numbers of the first kind. Absolute length. ogf for Stirling numbers of the first kind. Equidistribution of cyc and LRmax. Cycle index. Touchard's Theorem. Expected number of k-cycles in a permutation in S_n.
10/5: Inversions in ordered set partitions. Algebraic interpretation of inv(w) (Cayley graph). Geometric interpretation of inv(w) (Braid arrangement chambers). Mahonian distribution. maj(w). Carlitz bijection.
10/8: Des(w) and des(w). Eulerian polynomials. w-compatible function enumeration. Applications: Mahonian distribution for maj, egf for the Eulerian polynomials. Exceedences and weak exceedences. exc is Eulerian.
10/10: Set partitions. Bell numbers and Stirling numbers of the second kind. Relationship between Stirling numbers of the first and second kinds (+ function enumeration). Exponential generating function for Bell and Stirling numbers. Ordered set partitions. Connection to flats and faces in the braid arrangement. Generating function for ordered Bell numbers. Using complex analysis to estimate the ordered Bell numbers.
10/12: Integer partitions and Young diagrams. Partition numbers. Basic partition generating functions. Some applications of partitions in algebra. Odd = distinct.
10/15: Partitions inside a box. The q-binomial coefficient; basic properties. Application to Grassmannians.
10/17: inv and maj on multiset permutations. q-multinomial coefficient. inv and the q-multinomial. Application to parabolic cosets. Application to partial flag enumeration.
10/19: Principle of Inclusion-Exclusion. Derangement problem. Counting multiset permutations {1,1,2,2,...,n,n} with no copies of ii. Formula for the Stirling numbers of the second kind S(n,k).
10/22: Counting ordered covers with PIE. Dual form of PIE. Counting permutations according to their descent sets.
10/24: Planar networks and their path matrices. Lindstrom-Gessel-Viennot. Proof of LGV via a sign reversing involution. Any n x n matrix over a field is the path matrix of a (weighted) planar network. Application: Cauchy-Binet identity.
10/26: Totally nonnegative matrices. Examples from planar networks. Totally nonnegative polynomials. Counting partitions contained in a fixed partition.
10/29: Partial orders. Examples of posets. Incidence algebra I(P). Chains and multichains. Zeta function.
10/31: Moebius function. Moebius inversion. Calculating the Moebius function for Boolean poset, subspace poset.
11/2: Moebius function for set partition poset. Simplicial complexes.
11/5: f-vectors and Euler characteristic. The order complex of a poset. Connection to Moebius function.
11/7: Meet and join. Lattices. (Non-)examples. Weisner's Theorem. Using Weisner's Theorem to calculate Moebius values. Moebius inversion on the partition lattice.
11/9: Hyperplanes. Hyperplane arrangments. Examples. Regions and relatively bounded regions. Region counting for generic arrangements. Parking functions.
11/14: Stanley labeling for Shi regions. The Linial arrangement and alternating trees. The intersection lattice of an arrangement; basic properties. Characteristic polynomial. Zaslavsky's Theorem; topological proof.
11/16: The characteristic polynomials of the Boolean and Braid arrangements. The Finite Fields Method; Moebius inversion proof. Characteristic polynomial of the type B Braid arrangement. Characteristic polynomial of the Shi arrangement.
11/19: Antichains in posets. Dilworth's Theorem. Rank number and level sets. Rank symmetry and rank unimodality. Spernerity. Order matchings. Symmetric chain decompositions. Sperner's Theorem. Up and down maps.
11/26: More on up and down maps. Actions of subgroups G of S_n on Boolean algebras. Orbit enumeration; examples of orbits. Proof of symmetry and unimodality for orbit counts.
11/28: Proof of unimodality of (1 + q)(1 + q^2)...(1 + q^n). The Lie algebra sl_2. E,F,H, and bracket. sl_2-modules.
11/30: Examples of sl_2-modules. Axioms for SL_2- vs sl_2-modules. Homomorphisms/isomorphisms. Direct sums. Irreducibility. Complete reducibility. Sketch of proof: Weyl's Unitary Trick. Classification of irreducible sl_2-modules. Formal characters.



Lecture Notes:

Lectures 1-2.
Lectures 3-5.
Lectures 6-8.
Lectures 9-11.
Lectures 12-16.
Lectures 17-26.

Homework Assignments:

Permutation statistics.
Combinatorial distributions.
PIE and Posets.