Course meets: Tuesday and Thursday, 11-12:30,
Room 2-102.
Lecturer: Professor
Sergey Fomin,
Room 2-363B, 253-1713,
fomin@math.mit.edu
Office hours: Wednesday, 11-12:30 (and by appointment).
Teaching assistant: Benjamin S. Joseph,
ben@math.mit.edu
Grade based on two 1.5-hour exams, 20% each;
30% homework; 30% final exam. Exams are open-book.
Text:
R.Brualdi,
Introductory Combinatorics, 3rd edition,
Prentice Hall, 1999.
Course homepage: http://www-math.mit.edu/~fomin/18314.html
Course description from the MIT Catalog
Combinatorial problems and methods for their solution. Prior
experience with abstraction and proofs helpful.
Enumeration, generating functions, recurrence relations, construction
of bijections. Introduction to graph theory.
Network algorithms, extremal combinatorics.
Course Outline (tentative)
1. The pigeonhole principle (Chapter 2).
2. Permutations and combinations (Chapter 3).
3. Binomial coefficients (Chapter 5).
4. Inclusion-exclusion principle (Chapter 6).
5. Generating combinatorial objects (Chapter 4).
6. Recurrence relations and generating functions (Chapter 7).
7. Special counting sequences (Chapter 8).
8. Introduction to graph theory (Chapters 11 and 13).
9. Digraphs, networks, and matchings (Chapters 9 and 12).
Homework assignments (from Brualdi)
HW1, due 2/11: Sec. 2.4, problems 10, 11, 13, 17, 20, 21, 22, 27.
HW2, due 2/18: Sec. 3.6, problems 2, 7, 10, 17, 21, 30, 31, 33(c), 35.
HW3, due 2/25: Sec. 3.6, problems 22, 26;
Sec. 5.8, problems 12, 18, 20, 32, 37, 40.
HW4, due 3/4: Sec. 6.6, problems 6, 8, 13, 24(a), 24(b), 27, 30.
HW5, due 3/18: Sec. 4.6, problems 23, 25, 29, 33;
Sec. 7.8, problems 30, 32, 39.
HW6, due 4/1: Sec. 7.8, problems 11, 14, 22, 26, 34;
Sec. 8.5, problems 7, 8.
HW7, due 4/8: Sec. 8.5, problems 2, 5, 12(d), 16, 20, 22(a), 28.
HW8, due 5/6: Sec. 11.8, problems 2, 9, 12, 20, 34, 35, 82;
Sec. 13.6, problems 17, 25.
First midterm exam: March 4
Second midterm exam: April 13
Final exam: May 18, 9-12, Room 4-149.