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