**Lectures:** M/W/F 9:00-9:50 A.M., MS 5138. **TA class:**
Thu 9:00-9:50 A.M., MS 5138

**Instructor:**

Benny Sudakov, MS 7911,
bsudakov@math.ucla.edu

Office hours: Wednesday 4-5 P.M. at MS 7911.

**Teaching Assistant:**

Shagnik Das, MS 6160, shagnik@ucla.edu

Office hours: Monday 4-5 P.M., Tuesday 4-5 P.M. at MS 6160

**Course description:**

Material to be covered: Permutations and combinations, generating functions, recurrences, principle of inclusion and exclusion, graph theory.

**
Grading:**

Homeworks - 20%, Midterm 20%, Final exam - 60%

**Text book:**

*Applied Combinatorics*, by
Tucker, 5th edition.

The midterm for class MATH 180 will be on **Friday, February 10**
Please show up at class a bit earlier so that we can start working at 9.00 A.M. There is class after us so I will not be able to grant
any time extensions.
The topics to know for Midterm are: all sections we covered includig Section 6.4 (everything including all sections of generating functions)

Homework is a very important part of the class. You can not learn math without doing homework. Most of the questions of exams will be quite similar to the questions which have appeared on the homework. I will post all the homeworks on this website: http://www.math.ucla.edu/~bsudakov/180.html

* Section 5.1, Problems: 3, 4, 6, 9, 13, 21, 23, 30, 32, 39;
*

*
Section 5.2, Problems: 7, 10, 11, 17, 22, 30, 60a, 60b, 67a
*

*
Section 5.3, Problems: 8b, 11, 13, 18, 22, 24, 32
*

*
Section 5.4, Problems: 6, 7, 10, 18, 22, 24, 36, 48
*

*
Section 5.5, Problems: 9a, 14a, 14b, 14c
*

*
Section 8.1, Problems: 10, 11, 12, 19, 28, 29, 36
*

*
Section 8.2, Problems: 2, 4, 10, 13, 17, 18, 22
*

*
Section 6.1, Problems: 2, 3a, 3b, 7, 14, 20, 22, 23. (Hint on 22: try changing variables e_i to f_i=e_i-e_{i-1}, with f_1=e_1.)
*

*
Section 6.2, Problems: 7, 8, 11a, 11b, 15a, 15d, 18, 22
*

*
Section 6.3, Problems: 2, 7b, 12
*

*
Section 6.4, Problems: 3, 6, 7, 9, 14, 20
*

*
Section 7.1, Problems: 3, 6, 17, 18, 27
*

*
Section 7.3, Problems: 3, 6, 7
*

*
Section 7.4, Problem: 9
*

*
Section 7.5, Problems: 1, 2, 5, 8
*

*
Section 1.1, Problems:4, 7, 10, 16
*

*
Section 1.2, Problems: 5b, 6a, 14a, 14b
*

*
Section 1.3, Problems: 2, 7, 9, 14, 15
*

*
Section 1.4, Problems: 5, 8, 12a,b, 16, 20, 23
*

*
Section 2.1, Problems: 1, 2, 4, 8, 12b, 18
*

*
Section 2.2, Problems: 2a,b, 9a,b, 16, 19a,b, 21, 23
*

*
Section 2.3, Problems: 1a,c,f, 9, 10, 13, 14
*

*
Section 2.4, Problems: 2, 4, 11, 14, 17
*

*
Section 5.1-5.3: Two basic counting principles,
Simple arrangements and selections, Arrangements and selections with repetitions
*

*
Sections 5.4-5.5: Distributions, Binomial Identities
*

*
Sections 8.1, 8.2, 6.1: Venn diagrams, Inclusion-Exclusion formula, Introduction into Generating functions
*

*
Sections 6.2-6.4: Generating functions and their coefficients, Partitions, Exponential generating Functions
*

*
Sections 7.1, 7.3: Recurrence and solution of linear reccurence relation, Midterm
*

*
Section 7.4-7.5, 1.1: Solution of inhomogeneous recurrences,
solution of recurrences using generating functions, graph models
*

*
Section 1.2-1.3: Isomorphisms, Edge counting, Bipartite graphs
*

*
Planar graphs, Euler cycles and Hamilton cycles in graphs
*

*
Graph colorings, Graph colorings theorems, Chromatic polynomial
*