MATH 180: Combinatorics

Time and Place:

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.

Midterm:

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:

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

  • Homework 1, due January 18

    • 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

  • Homework 2, due January 25

    • 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

  • Homework 3, due February 1

    • 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.)

  • Homework 4, due February 8

    • 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

  • Homework 5, due February 15

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

    Section 7.3, Problems: 3, 6, 7

  • Homework 6, due February 22

    • Section 7.4, Problem: 9

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

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

  • Homework 7, due February 29

    • 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

  • Homework 8, due March 7

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

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

  • Homework 9, due March 14

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

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

    Course Outline (to be updated during the term):

  • January 9-13:

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

  • January 18-20:

    • Sections 5.4-5.5: Distributions, Binomial Identities
     

  • January 23-27:

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

  • January 30-February 3:

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

  • February 6-10:

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

  • February 13-17:

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

  • February 22-24

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

  • February 27-March 2

    • Planar graphs, Euler cycles and Hamilton cycles in graphs
     

  • March 5-9

    • Graph colorings, Graph colorings theorems, Chromatic polynomial