Math 180, Combinatorics

**Update**: Midterm is on Friday, Nov. 9th!!!!!! Office Hours are changed to: M4-5, W3-5.

Tentative Schedule

Syllabus :[Syllabus_math180] with a full description about this course.

Note: Weekly homework is due on Tuesday, at the beginning of Disccusion section. Homeworks will be posted here:

Homework 1 is due on Tuesday, October 9:

Section 5.1: 2, 5, 6, 9, 13(a), 24, 34, 39, 46.
Section 5.2: 7, 12, 18, 22, 29, 46(a), 70, 82.
Section 5.3: 4, 6, 10, 19, 25, 30, 35.

Homework 2 is due on Tuesday, October 16:

Section 5.4: 8, 14, 26, 40, 55.
Section 5.5: 3(c), 12(b), 14(d), 20(b), 32.
Section 6.1: 7, 10, 15, 20, 22.
Section 6.2: 8, 16, 26, 28, 35(b), 41.

Homework 3 is due on Tuesday, October 23:

Section 6.3: 2, 5, 12, 16, 19(b).
Section 6.4: 6, 12, 14, 16, 17, 20,
Section 7.1: 18, 25, 34(c), 36, 46.

Homework 4 is due on Tuesday, October 30:

Section 7.3: 2, 4, 6, 8, 10.
Section 7.4: 6, 9(b), 10, 17, 18.
Section 7.5: 1(d), 4, 8, 13, 14.
Read text until section 7.5.

Homework 5 is due on Tuesday, Novemeber 6:

Section 8.1: 10, 14, 18, 26, 34, 36
Section 8.2: 8, 12, 18, 22, 25, 28, 40, 44(a),

Homework 6 is due on Tuesday, Novemeber 13:

Section 1.1: 6, 7.
Section 1.2: 2, 6(b,d,f,h), 10, 14(a,b).

Homework 7 is due on Tuesday, Novemeber 20:

Section 1.3: 1(b), 4, 6, 8, 11, 16.
Section 1.4: 4, 6, 8, 12(b,c), 16, 20, 23.

Homework 8 is due on Tuesday, Novemeber 27:

Section 2.1: 2, 8, 12(a), 15, 16.
Section 2.2: 2(b), 4(b), 6, 8(c), 16, 24 (Hint: reduce to Thm 2).
It is not a homework, but try to prove Theorem 3 of section 2.2 by using Euler formula.

Homework 9 is due on Tuesday, December 4:

Section 2.3: 1(c,p), 2(b,d)
Section 2.4: 2, 4, 8, 9(b), 11, 14(c,d).

There is no homework in the last week. The following two are good exercises for matchings in bipartite graphs

Problem 1: Let M be a matching in a bipartite graph G and assume that M contains fewer edges than some other matching M' in G. SHow that G contains an M-augmenting path.
Hint: Use both of M and M' to construct such path.
Problem 2: Let A be a finite set with subsets A_1,A_2...,A_k, and let d_1,d_2,...,d_k be positve integers. Show that there are disjoint subsets B_i of A_i with sizes of d_i for all i=1,2,...,k, if and only if for any subset S of {1,2,...,k}, the size of the union of A_i over all i in S is at least the sum of d_i over all i in S.
Hint: Define a bipartite graph in which A is one side and the other side consists of a suitable number of copies of A_i. Then reduce this to the Hall's Theorem.

Course outline will be updated here during term:

Lec 1 (Sep 28): Two basic counting principles (Section 5.1)

Lec 2 (Oct 1): Simple arreangements and Selections (Section 5.2)

Lec 3 (Oct 3): Arreangements and Selections with repetitions (Section 5.3)

Lec 4 (Oct 5): Distributions (Section 5.4)

Lec 5 (Oct 8): Binomial Identities (Section 5.5)

Lec 6 (Oct 10): Generating function models (Section 6.1)

Lec 7 (Oct 12): Coefficients of generating fucntions (Section 6.2)

Lec 8 (Oct 15): Partitions (Section 6.3)

Lec 9 (Oct 17): Exponential generating functions (Section 6.4)

Lec 10 (Oct 19): Recurrence relations (Section 7.1)

Lec 11 (Oct 22): Solution of linear recurrence relations (Section 7.3)

Lec 12 (Oct 24): Solution of inhomogeneous recurrence ralations (Section 7.4)

Lec 13 (Oct 26): Solutions with generating functions (Section 7.5)

Lec 14 (Oct 29): Venn diagram (Section 8.1)

Lec 15 (Oct 31): Inclusion-Exclusion formula (Section 8.2)

Lec 16 (Nov 2): Section 8.2 continued

Lec 17 (Nov 5): Basic of graph theory (Section 1.1-1.2)

Lec 18 (Nov 7): Quick review on Enumeration

Lec 19 (Nov 9): Midterm

Lec 20 (Nov 14): Edge Counting (Section 1.3)

Lec 21 (Nov 16): Planar graphs (Section 1.4)

Lec 22 (Nov 19): Euler cycle (Section 2.1)

Lec 23 (Nov 21): Hamilton circuit (Section 2.2)

Lec 24 (Nov 26): Graph coloring (Section 2.3-2.4)

Lec 25 (Nov 28): Graph coloring continued

Lec 26 (Nov 30): Matching in bipartite graphs (See notes)

Lec 27 (Dec 3): Konig's Theorem and Hall's Theorem

Lec 28 (Dec 5): Hall's Theorem continued

Lec 29 (Dec 7): Review