Math, statistic and comp science majors
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.
- 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.