Student Body:

Math, statistic and comp science majors

Background and Goals:

As the title Introduction to Combinatorics suggests, Math 475 is a first course with emphasis on the basics of combinatorial counting techniques, number sequences, and patterns, with some graph theory thrown in. It is not however a course on what is traditionally called discrete mathematics. We will discuss algorithms for some of the combinatorial problems considered.

Alternatives:

N/A

Subsequent Courses:

N/A

Course Content:

- Pigeon-hole principle and applications
- Permutations and combinations
- Generating permutations and combinations
- Properties of binomial coefficients (combination numbers)
- Partial orders, equivalence relations, and Dilworth's theorem
- Inclusion-exclusion principle
- Recurrence relations and generating functions
- Difference sequences, Catalan numbers, Stirling numbers, partition numbers, and other counting sequences
- Marriage Theorem and Stable Marriages
- Graph theory (paths, cycles, trees, graph coloring, etc.)
- Polya counting (counting in the presence of symmetries)

Some topics are omitted according to instructor.

credits:

3. (N-A)

semester:

FallSpring

prereqs:

(MATH 320, 340, 341 or 375) or graduate or professional standing or member of the Pre-Masters Mathematics (Visiting International) Program

UW_course_guide: