**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.