1  Preface

These notes were developed to accompany MTH 337: Applied Combinatorics during the Spring semester of 2024. They are meant to be used interspersed with the material from Keller and Trotter’s book Applied Combinatorics. Both these notes and Keller and Trotter’s book are intended to have a heavy algorithmic and applied focus.

A sample sylabus is (KT is Keller and Trotter’s book)

  1. KT-2: Strings, Sets, and Binomial Coefficients
  2. KT-3: Induction
  3. KT-4.1: Pidgeonhole
    • Can cover the rest of KT-4 if students haven’t seen “big-O” in their other courses yet
  4. KT-5: Graph Theory
  5. KT-7 and Inclusion-Exclusion from these notes for supplementary proofs
  6. Permutations from these notes
  7. KT-12, 13, 14 on graph algorithms (Prim/Kruskal, Dijkstra, Ford-Fulkerson/Edmonds-Karp)
  8. Generating Functions from these notes (instead of KT-8)
  9. Regular Languages from these notes

Here is a rough overview of how these notes tie into the Keller/Trotter book.

flowchart
    KT2-Foundations --> KT7-Inclusion/Exclusion
    KT2-Foundations --> Permutations
    KT2-Foundations --> GeneratingFunctions
    KT7-Inclusion/Exclusion <--> Inclusion/Exclusion
    GeneratingFunctions --> RegularLanguages
    KT5-Graphs --> Permutations
    KT5-Graphs --> RegularLanguages
    LinearAlgebra -.. Transfer Matrix Method ..-> RegularLanguages

Inclusion/Exclusion makes a very brief appearance Note 18.1 but is otherwise separate in these notes.