Math 180: General Course Outline
Catalog Description
    180. Combinatorics. (4) Lecture, three hours; discussion, one hour. Requisites: courses 32B, 33B. Permutations and combinations, counting principles, recurrence relations and generating functions, combinatorial designs, graphs and trees, with applications including games of complete information. Combinatorial existence theorems, Ramsey theorem. P/NP or letter grading.
Textbook
    Alan Tucker , Applied Combinatorics, 5th Ed., Wiley
Reviews & Exams
    The following schedule, with textbook sections and topics, is based on 25 lectures. The remaining classroom meetings are for leeway, reviews, and midterm exams. These are scheduled by the individual instructor. Often there are reviews and midterm exams about the beginning of the fourth and eighth weeks of instruction, plus reviews for the final exam.
Schedule of Lectures

Lecture

Section
Topics
1
5.1
Basic counting
2
5.2
Arrangements vs selections
3
5.3
Arrangements and selections with repetition
4
5.4
Distributions
5
5.5
Binomial identities
6
6.1
Generating function models
7
6.2
Coefficients of generating functions
8
6.3
Partitions
9
6.4
Exponential generating functions
10
7.1
Recurrence relation models
11
7.3
Linear recurrences
12
7.3,4
In homogeneous recurrences
13
7.5
Recurrences and generating functions
14
8.1
Venn diagrams
15
8.2
Inclusion/exclusion
16
1.1
Graphs
17
1.2
Isomorphism
18
1.3
Edge counting
19
1.4
Planar graphs
20
2.1,2
Euler cycles
21
2.2,3
Hamilton cycles
22
2.3,4
Graphs Coloring
23
2.4
Planar graphs
24
4.3
Network flows
25
4.4
Matching

Comments

Outline update: I. Neeman and B. Rothschild, 12/03, revised for new edition 9/04

For more information, please contact Student Services, ugrad@math.ucla.edu.
 


UCLA Department of Mathematics                          Search     Home