MATH 180: Combinatorics

Course description:
Permutations and combinations, generating functions, recurrences, principle of inclusion and exclusion, graph theory, networks and algorithms. Prerequisites: Math 32B, 33B; familiarity with proofs.


Time and Place:
Lectures: MWF 12:00P,   Math Sciences Bldg Room 6229 . Section: Tu 12:00P (MS 6229).

Instructor:
Greta Panova , office: MS 6901, e-mail: panova AT math.ucla.edu
Office hours: Monday 3-4:50, Friday 2-3 in MS 6901. (might change throughout semester, check here before you come)

Teaching Assistant:
Humberto Naves, office: MS 3919, e-mail: hnaves AT math.ucla.edu
Office hours: Tuesdays 3-5pm.

Textbook:
Applied Combinatorics, by Alan Tucker, 5th edition.


Grading policy: Final exam - 60%,Midterm 25%, Homeworks - 15%.

Midterm: Wednesday, October 26 12:00-12:50 in room FRANZ 1260!!!. Please arrive early, we cannot take any extra time since the room is available to us only for one regular class hour.
Topics for the midterm all material covered from sections 5,6 and 7 of Tucker.

Final exam: Tuesday, December 06, 2011 11:30 AM - 2:30 PM

Homework:
Learning mathematics and especially Combinatorics happens primarily by solving problems, thus doing homework problems will be an essential part of the course. Homeworks will be posted here every week and will be due on Wednesday at 12:00P in class. Late homeworks will not be accepted, but the homework with lowest score will not be included in the final homework grade. Collaboration on the homework is encouraged, however you should write your own solutions and the names of your collaborators on top.


Handounts:
All supplementary materials (handouts, links, etc) can be found here.

Schedule of Topics

Day

Lecture #
Section
Topics
Sept 23 1 5.1 Basic counting principles
Sept 26 2 5.2 Arrangements vs Selections
Sept 28 3 5.3 Arrangements and Selections with repetitions
Sept 30 4 5.4 Distributions
Oct 3 5 5.5 Binomial identities
Oct 5 6 6.1 Generating functions
Oct 7 7 6.2 Coefficients of generating functions
Oct 10 8 6.3 Partitions
Oct 12 9 6.4 Exponential generating functions
Oct 14 10 7.1 Recurrence relations
Oct 17 11 7.3 Solutions of linear recurrence relations
Oct 19 12 7.4 Inhomogeneous recurrences
Oct 21 13 7.5 Solving recurrences with generating functions
Oct 24 14 5,6,7 Midterm review
Oct 26 15(Exam) 5,6,7 Midterm in room FRANZ 1260, 12:00-12:50.
Oct 28 16 8.1 Venn diagrams
Oct 31 17 8.2 Inclusion-exclusion principle
Nov 2 18 1.1 Graphs
Nov 4 19 1.2 Graph isomorphism
Nov 7 20 1.3 Edge counting
Nov 9 21 1.4 Planar graphs
Nov 11 No class   Veterans Day
Nov 14 22 2.1 Euler Cycles
Nov 16 23 2.2 Hamilton Circuits
Nov 18 24 2.3 Graph coloring
Nov 21 25 2.4 Coloring theorems
Nov 23 26 2.4 Coloring theorems: the chromatic polynomial
Nov 25 No class   Turkey digestion
Nov 28 27 notes Ramsey theory
Nov 30 28 notes Hall's marriage theorem
Dec 2 29   Final review, Q&A.