COMP 423: Combinatorial Mathematics
(2nd semester of Calculus)
Combinatorics is a branch of mathematics with broad areas of application. There are important uses of combinatorics in computer science, operations research, probability, and statistics. Theoretical thermodynamics uses combinatorial theory to describe ideas such as entropy. Combinatorial analysis is a cornerstone of the study of error-correcting codes; these codes are used to transmit information from deep space or to protect the quality of music on compact discs. Our course will mainly focus on describing and/or counting complicated sets. Often questions which begin "How many ways can you...?" or "How many steps does it take to...?" are answered using combinatorial analysis. Such questions on the surface may appear rather uninteresting, but one can quickly get to questions that are quite engaging. What gambler wouldn't want to understand the odds at winning a poker hand?
We plan to examine the following topics: permutations and combinations, the inclusion-exclusion principle and other general counting techniques, partitions, generating functions, recurrence relations, Burnside's Theorem, the cycle index, and Polya's formula. Other topics may be included as time permits. Emphasis will be on examples rather than theory.
This course is a combined undergraduate/graduate course. The requirements of the course for the graduate students will be different from the requirements for the undergraduates. The material should be comprehensible for any student who has completed MATH 162.
Text: Applied Combinatorics, 4th edition, by Alan Tucker.