Combinatorics and Probability - MAT2313
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. 3 Credit Hours
Sample textbooks: Alan Tucker, Applied Combinatorics (6th ed). Wiley (2012).
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.