Basic counting principles: permutations, combinations, probability, occupancy problems, and binomial coefficients. More sophisticated methods include generating functions, recurrence relations, inclusion/exclusion principle, and the pigeonhole principle. Additional topics include asymptotic enumeration, Polya counting theory, combinatorial designs, coding theory, and combinatorial optimization.
Additional Requirements for Graduate Students: Extra problems which are more difficult or more theoretical on
homework.
Athena Title
Combinatorics
Prerequisite
(MATH 3000 or MATH 3300 or MATH 3300E or MATH 3500 or MATH 3500H) and (CSCI 2610 or CSCI 2610E or MATH 3200 or MATH 3200W)
Semester Course Offered
Offered fall
Grading System
A - F (Traditional)
Student Learning Outcomes
Students will be able to state and apply basic counting principles such as the pigeonhole principle and the inclusion/exclusion principle.
Students will be able to solve counting problems involving combinations and permutations, and relate these to Pascal's triangle and multinomial coefficients.
Students will be able to analyze recurrence relations using generating functions.
Students will be able to connect certain sequences of natural numbers, such as the Catalan numbers and Stirling numbers, to appropriate combinatorial problems.
Topical Outline
Typical problems posed in combinatorial fashion: "how many ways can you ... ?"
