MAT2313
Contents
Combinatorics and Probability
3 Credit Hours
Course Catalog
Corequisite: MAT1224.
Content: Basic counting principles. Permutations and combinations. Binomial and multinomial coefficients. Pigeonhole and inclusion-exclusion principles. Graphs, colorings, planarity. Eulerian and Hamiltonian graphs. Recurrence relations. Generating functions. Prerequisites: MAT1224 Calculus II and MAT 1313 Algebra and Number Systems.
Description
Introduction to the theory of probability, through the study of discrete and continuous random variables.
Sample textbooks
Alan Tucker, Applied Combinatorics (6th ed). Wiley (2012).
Topics List
Course outline:
Week 1: Finite sets, strings, enumeration, the addition and product rules.
Week 2: Combinations, permutations.
Week 3: Binomial and multinomial coefficients.
Week 4: The Pigeonhole Principle. The Inclusion-Exclusion Formula, derangements, the Euler ɸ function (totient).
Week 5: Review. First midterm exam.
Week 6: Graphs and multigraphs.
Week 7: Eulerian and Hamiltonian graphs.
Week 8: Trees. Colorings. Planarity.
Week 9: Review. First midterm exam.
Week 10: Generating functions. The Binomial Theorem. Partitions.
Week 11: Recurrence relations. Linear recurrences.
Week 12: Solving recurrences by generating functions.
Week 13: Exponential generating functions. Nonlinear recurrences.
Week 15: Review.
