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: MW 4:00-5:00pm or by appointment. My office is 3228 Mathematical Sciences Building.
Text and References: I will follow the classic book ``Enumerative Combinatorics'' Volume I, by Richard P. Stanley. I will supplement it with my own notes and exercises.
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. Unknown to some people, there is a nice set of tools and
structures that help on carrying an exact count or how to make educated
estimations. Here is an outline of the course:
1) (2 weeks) Basic Combinatorial Enumeration (Permutations, Sets, MultiSets, Graphs, Partitions), bijections, and the Twelvefold way. (Chapter 1)
2) (4 weeks) Posets, Moebius Inversion, Involutions and the Inclusion-Exclusion Principle. (Chapters 2,3)
3) (4 weeks) Generating functions, Rational generating functions. (chapter 4).
Grading policy and Rules:
From Stanley's book Chapter 1: 1, 2.c, 9, 12, 14d, 14e
Problem 1: What is the number of $k$-subsets chosen from $1$ to $n$ containing no two consecutive integers?
Problem 2: What is the number of monotone increasing functions mapping the set $\{1,\dots,n\}$ into itself?
Problem 3: Prove that the Catalan numbers give the cardinality of the set of Standard tableaux in a 2 X n rectangular 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: find the right object to make the bijection).
Problem 4: 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.
Problem 5: All points of the plane that have integer coordinates are colored red, blue, or green. Prove that there will be a rectangle whose vertices are all of the same color. (Hint: use the pigeonhole principle!)
Problem 6: The number of partitions of $n$ into (any number) of distinct terms is equal to the number of partitions of $n$ into odd terms.
Problem 7: What is the number of conjugacy classes in the symmetric group $S_n$?
Problem 8: 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)?
Problem 9: Suppose you choose a permutation in S_n uniformly at random. What is the expected number of cycles?
Problem 10: Stanley chapter 1 30 a,b.
Problem 11: 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.
Problem 12: What is the number of permutations in $S_n$ so that there is no triple $i < j < k$ with $\pi(j) < \pi(i) < \pi(k)$?
Problem 13: Find in the literature or create yourself a combinatorial proof of the theorem: the number of labeled spanning trees on the complete graph on $n$ nodes is $n^{n-2}$. Essentially, don't use generating functions!
Problem 14: Five people wearing red hats start spreading a rumor. In the first hour, each of them tells the rumor to one person who did not wear a red hat before. These new converts will put on red hats and enlist to spread the rumor further. The same trend continues, following the rule that each person will tell the rumor to one other person in his first hour after enlisting, and to nine other people in each subsequent hour. Nobody will ever take their red hat off. How many people will wear red hats after $n$ hours?
Problem 15: Using generating functions find an explicit formula for a_n if it satisfies the recurrence $a_n=na_{n-1} +(-1)^n$ and a_0=1.
Problems from Stanley's book Chapter 1: 23, 30,43, 44
Problem 16: Verify that the ring of formal power series is an integral domain. What is its quotient field?
HOMEWORK PROBLEMS FOR SECOND HALF
Exercises for the second part of the course
Stanley Chapter 2: #1,6,7
Stanley Chapter 3: 5, 11, 44, 45, 53.a, 56 a,b.
Problem 17: 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}.
Problem 18: 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.
Problem 19: Let P(Q) be the face lattice of a convex polytope with the smallest element $o$ deleted. Let O(P(Q)) be its order complex, if we think of the simplices of O(P(Q)) as simplices made of points of Q can you find any relation between Q and O(P(Q))?
Problem 20: 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 (HINT: See page 15 of http://www.math.ucdavis.edu/~deloera/BOOK/october2006version.pdf)
Problem 21: 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. (HINT: First of all by corollary 3.9.5 of Stanley's book one can assume all elements are joints of atoms and meet of coatoms. Using this show that if $L$ is a lattice such that M(0,y) is non-zero for all y in L, then there exist a permutation p:L ---> L satisfying x meet p(x) = 0 for all x in L. Using this permutation {y in L : x <= y} and p({y in L : x <= y}) intersect and any t in their intersection satisfies t meet p(t) >= x. To prove the lemma see page 7 of http://quoll.uwaterloo.ca/pstuff/moebius.pdf)
Stanley's Book Chapter 4: 5, 10, 15, 27, 28.a, 29, 30, 32,33
Problem 22: Let $P_3(r)$ be the number of $3 \times 3$ semi-magic squares that are symmetric to their main diagonal and have line sum $r$. Is $P_3(r)$ a polynomial?
Problem 23: Show a bijection from the set of $n \times n$ Latin squares onto that of $n \times n \times n$ semi-magic cubes with magic line sums all equal to one. (HINT: What is the vertical slice of the semi-magic cube?)
Problem 24: Let $P$ be an integer polytope such that dim P=d and let $f$ be its Ehrhart polynomial. Prove that the highest term of $f$ is equal to the volume of $P$. (HINT: when counting lattice points we can also think we are approximating the volume the polytope by unit squares, use a limit as the grid decreases in width)
Problem 25: Let $P$ be a tetrahedron with vertices $(0,0,0)$ $(1,0,0)$, $(0,1,0)$ and $(1,1,n)$, where $n>0$ is an integer parameter. prove that the Ehrhart polynomial of $P$ is $$ p(k)=(n/6)k^3 + k^2 + (12-n)k/6 +1$$ (HINT: Set up calculation as cone and then you can apply the rational function method we saw in class).