MIT   fall 2007

18.314     combinatorial analysis

Updated Problem Set 6 is available here.

class meets:   Tuesday and Thursday, 2:30 - 4 pm, room 2-136

instructor:   Alexander Postnikov

office hour: Tuesday 4 - 5 pm

description:
Combinatorial problems and methods for their solution. Enumeration, generating functions, recurrence relations, construction of bijections. Introduction to graph theory. Prior experience with abstraction and proofs is helpful.

topics:
pigeon-hole principle, mathematical induction, permutations, binomial theorem, compositions, partitions, Stirling numbers, inclusion-exclusion principle, recurrence relations, generating functions, Catalan numbers, graphs, trees, Eulerian walks, Hamiltionian cycles, matrix-tree theorem, electrical networks, graph colorings, chromatic polynomials, (and if time allows) Polya counting, Ramsey theory, pattern avoidance, probabilistic method, partial orders, combinatorial algorithms ...

course level:   undergraduate

recommended textbook:
-  A Walk through Combinatorics, 1st edition or 2nd edition, by Miklos Bona, World Scientific.
The students will not be required to buy this textbook.

grading:   Problem sets due every two weeks 50% + 3 inclass quizes 50%. There will be no final exam.

problem sets:

practice quizes:

syllabus: (tentative)

  1. R 09/06/2007. Pigeonhole principle. Chapter 1.

  2. T 09/11/2007. Mathematical induction. Chapter 2.

  3. R 09/13/2007. Permutations. Rook placements. Binomial coefficients. Lattice paths. Chapter 3.

  4. T 09/18/2007. Binomial theorem. Chapter 4.

  5. R 09/20/2007. Compositions. Integer partitions. Sections 5.1 and 5.3. Problem Set 1 is due.

  6. T 09/25/2007. Set partitions. Section 5.2.

  7. R 09/27/2007. Cycle structure of permutations. Chapter 6.

  8. T 10/02/2007. Quiz 1.

  9. R 10/04/2007. Inclusion-exclusion principle. Chapter 7. Problem Set 2 is due.

    T 10/09/2007. no classes (Columbus day)

  10. R 10/11/2007. Inclusion-exclusion (cont'd).

  11. T 10/16/2007. Generating functions and recurrence relations. Chapter 8.

  12. R 10/18/2007. Generating functions (cont'd). Ordinary generating functions. Problem Set 3 is due.

  13. T 10/23/2007. Generating functions (cont'd). Exponential generating functions.

  14. R 10/25/2007. Catalan numbers.

  15. T 10/30/2007. Catalan miscellany.

  16. R 11/01/2007. Quiz 2. Problem Set 4 is due.

  17. T 11/06/2007. Graphs. Eulerian walks. Hamiltionian cycles. Chapter 9.

  18. R 11/08/2007. Trees. Counting trees. Chapter 10.

  19. T 11/13/2007. Minimum-weight trees. Greedy algorithm. Section 10.2.

  20. R 11/15/2007. Matrix-tree theorem. Section 10.3.

  21. T 11/20/2007. Electrical networks. Problem Set 5 is due.

    R 11/22/2007. no classes (Thanksgiving)

  22. T 11/27/2007. Eulerian digraphs.

  23. R 11/29/2007. Graph colorings. Chromatic polynomials. Matchings. Chapter 11.

  24. T 12/04/2007. Quiz 3.

  25. R 12/06/2007. Polya counting. Ramsey theory.

  26. T 12/11/2007. Pattern avoidance. Probabilistic method. Problem Set 6 is due.

additional information: