475 - Introduction to Combinatorics
Prerequisites:
Math 320 or 340, or consent of instructor.
Frequency:
Fall (I), Spring (II)
Student Body:
Math, statistic and comp science majors
Credits:
3. (N-A) Recent Texts:
Introduction to Combinatorics, 5th ed, Richard A. Brualdi
Course Coordinator:
Arnold Miller 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.