Meetings: MWF 3:10-4:00 PM, Bainer 1134
Instructor: Prof. Jesús A. De Loera.
email: deloera@math.ucdavis.edu
URL: http://www.math.ucdavis.edu/~deloera/TEACHING/ENUMCOMBINAT/enumcombinat.html
Check this web page often!
Phone: (530)-754 70 29
Office hours: MWF 3:00am-4:00pm
or by appointment. My office is 580 Kerr Hall.
Text and References: I will follow the classic book ``Enumerative Combinatorics'' Volume I, by Richard P. Stanley. I will supplement with my own notes and exercises. Other useful reference is ``A course in Combinatorics'' by Van Lint and Wilson.
Description: The objective of this
course is to teach you HOW TO COUNT (and you thought you knew since Kindergarden, eh?). The goal of enumerative combinatorics is to count the number of elements of a finite set. My goal is to teach a set of tools that help on carrying an exact count or how to make educated estimations. Here is an outline of the course
1) (3 weeks) Basic Combinatorial Enumeration (Permutations, Sets,
MultiSets, Graphs, Partitions), Basics of generating functions, bijections
and the Twelvefold way. (Chapter 1)
2) (4 weeks) Posets, Moebius Inversion, Involutions and the Inclusion-Exclusion Principle. (Chapters 2,3)
3) (3 weeks) Rational generating functions.
Grading policy and Rules:
-----------------FIRST WEEK------------------
April 1: From Stanley's book Chapter 1: 1, 2.c
Problem: What is the number of ways of going up n stairs, if we may take
one or two steps at a time?
April 3: Chapter 1 Stanley: 3,7.
Problem: Using the idea of contracting edges of a triangulation
derive a different recurrence for the number T_n of triangulations of
a convex n-gon. Can you use this to derive a formula for T_n?
April 5: Chapter 1 Stanley 9,12.
Problem: Prove that the following families of objects have
the same cardinality: (A) Parenthesizations of n non-commuting variables
(B) Standard tableaux in a 2 X n rectangular Ferrers diagram.
A Standard tableaux for a 2 X n rectangular array of boxes is a way
to arrange the numbers {1,2,...,2n} in the boxes in such a way they
increase across rows and down columns. (Hint: you don't have to
give a direct bijection).
--------------------SECOND WEEK---------------------
April 8: Problem: (1) Prove that the maps we set up in class for the CATALAN family are indeed bijections. (2) A Full binary tree is one where every node has either 2 or 0 children. Set up a bijection between binary trees with n nodes and full binary trees with 2n+1 nodes.
April 10: Stanley's book Chapter 1: 14d, 14e.
April 12: How one can check whether a set of permutations p_1,p_2,..p_k generates the whole group S_n? Is there a general effective method like when in the case when the p_i's are transpositions? Check the literature for this problem.
-----------------THIRD WEEK---------------------------
April 15: If a permutation a_1a_2...a_n has an inversion table (b_1,b_2,...,b_n) what is the permutation that corresponds to the inversion table (n-1-b_1,n-2-b_2,...,0-b_n)?
April 17:
PROBLEM 1: Suppose you choose a permutation in S_n uniformly
at random. What is the expected number of cycles?
PROBLEM 2: Choose a permutation p at random. denote by invt(p) the
inversion table of p. Show that the entries of the vector invt(p) are
random independent variables.
April 19: Stanley Chapter 1, #30 a,b.
PROBLEM: Figure out how many standard Young tableaux are there which
can be formed with {1,2,...15}. (Hint: There are many ways to skin a cat)
PROBLEM: Using the RSK correspondence write the pair of standard Young
tableaux corresponding to the permutation 4,3,6,8,9,2,6,5,7,1
-------------FOURTH WEEK-----------------------------
April 22: In the following problems [n choose k] denote the corresponding q-binomial coefficient:
PROBLEM: Without doing calculations prove the recursion relation
about the q-binomial coefficients we saw in class.
PROBLEM: Figure out for which exponents e_i we have the identity:
[ n+m choose k] = \sum_{i=0}^k q^{e_i} [n choose i][m choose k-i]
April 24: Stanley Chapter 1: # 16,17
PROBLEM: Show that the number of permutations of S_n with
an even number of cycles equals the number of permutations of S_n with
an odd number of cycles (n>1).
April 26: TAKE HOME MIDTERM
----------------FIFTH WEEK-------------------------------
May 1: Stanley Chapter 2: #1,6,7
May 3: Stanley Chapter 3: #5
PROBLEM: Let A_1,A_2,...,A_k be distinct subsets of
{1,2,...,n} with the property that A_i and A_j have a non-empty
intersection for all pairs i,j. Show that k <= 2^{n-1}.
-----------------SIXTH WEEK-------------------------------
May 6: Stanley Chapter 3: # 11
PROBLEM: Consider the lattice of subspaces of the vector space (F_q)^n, where F_q is a finite field. Prove that the size of the largest antichain is at most [n \choose floor(n/2)], where [n choose k] denotes a q-binomial coefficient.
May 8: PROBLEM: Let P(Q) be the face lattice of a convex polytope.
Let O(P(Q)) be its order complex, if we think of the simplices of
O(P(Q)) as simplices made of vertices of Q can you find any relation between
Q and O(P(Q))?
PROBLEM: Given a poset P with
elements x_1,...,x_n$ one can define an {\em order polytope} Q(P)
in R^n by:
Q(P)=\{X \in R^n | 0 <= X_i <=1 , X_i >X_j \quad if \quad x_i>x_j \quad in \quad P\}.
Prove that the vertices of Q(P) are in bijection to the order ideals of P.
What are the linear extensions of P in terms of Q(P)? Look at examples.
May 10: Stanley Chapter 3: #44,45.
PROBLEM: Let L be any lattice with n elements. Suppose there is an x, different
from 0 the smallest element, such that |{y in L : x <= y}|> n/2. Show that then
the Mobius function M(0,y)=0 for some y in L.
---------- SEVENTH WEEK ----------------------------------
May 13: Stanley Chapter 3: 53.a, 56 a,b.
May 15: Stanley Chapter 3: 61, 62.
May 17: Stanley Chapter 1: 44
-------------- EIGHTH WEEK --------------------------------
May 20: PROBLEM: If a compound structure S(N) is obtained by splitting a set into parts each part getting structure N, show that the exponential generating function of S(N), S(N)(x) equals exp(N(x)), where N(x) is the exponential generating function of the structure $N$.
May 22: PROBLEM: Verify that the ring of formal power series
is an integral domain. What is its quotient field?
PROBLEM: Prove that D(\sum f_n(z))=\sum D(f_n(z))
for a sequence of formal power series.
May 24: Stanley Chapter 4: #5.
PROBLEM: Without getting your hands dirty with calculus prove that
(A) exp(x)*exp(-x)=1 and (B) log(exp(z))=z inside
the ring of formal power series.
----------- NINETH WEEK ------------------------
May 27: MEMORIAL DAY.
May 29: Stanley Chapter 4: 10
May 31: Stanley Chapter 4: 15
--------- TENTH WEEK -----------------------------
June 3: Stanley Chapter 4: 27,28.a
June 5: Stanley Chapter 4: 29
June 6: Stanley Chapter 4: 30
June 7: Stanley Chapter 4: 32,33
----------------------------------------
LAST MIDTERM DUE Tuesday June 11 by 5:00pm.