MAT2313

Combinatorics and Probability - MAT2313

Catalog entry

Prerequisite: Algebra and Number Systems MAT1313, or Discrete Mathematical Structures (CS 2233/2231), or instructor consent. Corequisite: MAT1224. (3-0) 3 Credit Hours.

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. 3 Credit Hours

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. Second 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.