Math 5705 (Enumerative combinatorics): (Fall 2007)

Instructor: Alexander Yong ayong@math.umn.edu

Lectures: Mondays and Wednesdays 3:35PM-5:00PM. VinH 311

Outline: We will cover chapters 5-9 of the book, as well as some special topics. This will include basic aspects of enumerative combinatorics: counting techniques, generating series, algorithmic aspects, common constructions. I'll discuss how to relate these ideas to ideas in computer science, probability and statistics, e.g., to study problems motivated by gambling games: poker, solitaire, T.V. game shows).

Grading: Weekly assignments (25%), three in class exams (75%) -- no final. The grading of homework will be based on the availability of a qualified grader. If no such grader is found, I will announce an alternative policy. I reserve 10% of the portion of the "weekly assignments" to be based on the effort shown on solving "starred problems" as well as participation in class (e.g., presentation of solutions). Students should expect to show reasonable achievement on these problems and those harder problems on exams in order to achieve an A.

Textbook: Applied Combinatorics, 5th edition by Tucker.

Notes: Material principally concerning graph theory is covered in Math 5707. I assume you have had an introduction to power series (including Taylor's theorem). So for example, you know the power series for exp(x) and for sums of finite and infinite geometric series. Typically, we will not concern ourselves with convergence issues, put rather will algebraic manipulations.

Test 1: Wednesday October 3 2007; Test 2: Wednesday November 7, 2007; Test 3: Wednesday December 12, 2007.


Lecture 1: Email me some information about yourself (mathematical background and interests). Complete the following survey . It will help me better prepare the course material to suit your needs. I'll outline some of the ways in which enumerative problems arise, and some basic philosophy of the course. Also, read Polya's method of solving problems, either in his book, or the summary found here at wikipedia as "four principles".

We discussed the addition and multiplication principles, and their variants. Warmed up with some dice, word and card problems, computing the probability of various events occuring. We ended with the gorup problem of how many ways to place two identical rooks on a 8x8 (and then mxn) chess board such that they share a row or column (answer to be presented next class).

Lecture 2: Here is assignment 1. It is due in one week. Today we talked about binomial coefficients and identities, permutations and combination problems. A Texas hold'm problem was presented, and partitions and lattice paths were introduced.

Lecture 3: We started with a discussion of a "starred" programming project that I'll more carefully describe in assignment 2. Basically, how many casino style shuffles are needed to ensure a deck of cards is shuffled randomly? We took up some more binomial identity examples. We then talked more about distributions, and how to break down the problems in terms of the "identical" or "distinct" condition. Finally, I asked a world poker tour question, where "Rocky" went all in with 1,000,000 dollars and "Annie Duke" called; all this before the flop. Your job is to determine if Annie's call gives her good pot odds.

Lecture 4: Here is Assignment 2 , due Wednesday September 27, 2007. Today, I'll introduce (ordinary) generating series.

Lecture 5: Today I'll go deeper into the study of generating series. In particular, I'll look at partition identities. Note: in the problem 8 of Assignment 2, the LHS should read C(2n,2) (thanks to tyler for pointing that out). Also, in Q1, (c) should read "Find a bijection between the number of paths from A=(1,1) to B=(h+t,h-t) which touch or cross the x-axis , and the number of all paths from A'=(1,-1) to B. [Hint: look at the first time a path touches or crosses the x-axis.]" (Thanks Bryan for pointing this out.)

Today we spoke about refinement of the weight function and began our discussion of exponential generating series.

Our first test will cover all of chapter 5, but not anything about generating series.

Lecture 6: Here is Assignment 3 , due October 17, 2007. Today, we'll continue our discussion of exponential generating series.

Lecture 7: We had test 1.

Lecture 8: We completed our discussion of the ``star product'' on labelled combinatorial sets, and formally derived the corresponding product lemma. We took up Test 1.

Lecture 9: Here is Assignment 4 which is not due until October 30, 2007. (I put it up now so you can start thinking about these problems while we discuss exponential generating series.) Today I spoke about the compositional lemma. Here's the idea again. You have some combinatorial structures B(t) where t is the generic subobject, and you have another combinatorial structure A(s) with generic subobject s. You want to build another combinatorial structure A@B(t) with generic subobject t by placing elements of B(t) into the generic subobjects s of an element of A(s), and relabelling in all possible ways. The point is that many combinatorial objects can be realized this way. Our main example is when A=U=unordered sets, and B=C=cycle permutations . Then A@B _is_ in bijection with the set of all permutations P. Hence [P]=[A]@[B] where [P], [A], [B] are the corresponding exponential generating series, weighted by the number of generic subobjects.

Lecture 10: We'll finish off our discussion of generating series today with more discussion of using the composition lemma. I'll talk about Lagrange's inversion formula (but not prove it). An application is the enumeration of rooted labelled trees. I'll talk about the Prufer bijection. A (*) problem is to prove the Prufer map is a bijection (hand in with Assignment 4).

Lecture 11: We began chapter 7 on recurrences. Our discussion led to a (*) problem: show by an explicit bijection that the number of binary trees on n leaves equals the number of Dyck paths with n up and down steps.

Lecture 12: We discussed the Schensted correspondence and as a group showed its well defined and a bijection. I also want you to prove that the longest increasing subsequence of a permutation is the length of the first row of the shape associated to it under Schensted. We'll continue to discuss this next time as we build towards a group project.

Lecture 13: Setup the group project about Schensted, Longest increasing subsequences and Plancherel measure. No class next Wednesday. However, we will meet as a class at Expresso expose on Sunday Nov 11 at 2pm to discuss progress.

Lecture 14: We proved the hook length formula, using a probabilistic argument. Here is Assignment 5 .

Lecture 15: We reviewed for the second midterm.

Lecture 16: We took the second midterm. Here is the exam and solutions. The average grade on MT2 was 72%.

Lecture 16.5: We got together on Sunday November 11, 2007 to discuss aspects of the "Longest increasing subsequences" assignment.

Lecture 17: Discussed inclusion-exclusion.

Lecture 18: Discussed rook placements and polynomials. Here is assignment 6, due December 3: Section 8.1 Q14, 27; section 8.2 Q10, 19, 29, 41; section 8.3 Q10, 13.

Lecture 19: Discussed Burnside's lemma. Our discussion varies slightly differently from the book in that I formulated things in terms of abstract groups and abstract group actions on sets.

Lecture 20: Discussed the longest increasing subsequences group assignment. We also decided that Test 3 will be a take home exam, that will be handed out on Monday December 10 at 8AM and due December 12 at 5pm. Continued discussion of Polya's theorem

Lecture 21: Completed out discussion of Polya's enumeration theorem. Students presented solutions to Assignment 4. Here is Assignment 7 (optional) on Chapter 9: Read Chapter 9, do Section 9.2 Q6,12 Section 9.3 Q11, 14; Sectopn 9.4 Q1, 16, 19. This assignment is due the last day of class.

Lecture 22: Discussed Schensted and the Littlewood-Richardson rule.

Take home test III Is now available.