This course on Combinatorics aims to teach students the rules of sum and product, permutations, combinations, the binomial theorem, mathematical induction, recursive definitions, the pigeonhole principle, the principle of inclusion and exclusion, derangements, generating functions, partitions of integers, recurrence relations, group theory, Burnside’s theorem, Polya’s method of enumeration, graph theory, Euler trails and circuits, planar graphs, Hamilton paths and cycles, graph coloring, chromatic polynomials, trees, rooted trees, Dijkstra’s shortest path algorithm, and minimal spanning trees using Kruskal and Prim's algorithms. The course utilizes a combination of theoretical explanations, examples, and practice questions to help learners understand and apply these concepts effectively. The course is designed for individuals interested in advancing their knowledge of discrete mathematics and combinatorics.
Overview
Syllabus
Combinatorics 1.1 The Rules of Sum and Product.
Combinatorics 1.2 Permutations.
Combinatorics 1.3 Combinations - The Binomial Theorem.
Combinatorics 1.4 Combinations with Repetition.
Combinatorics 4.1 The Well Ordering Principle - Mathematical Induction.
Combinatorics 4.2 Recursive Definitions.
Combinatorics 5.5 The Pigeonhole Principle.
Combinatorics 8.1.1 The Principle of Inclusion and Exclusion.
Combinatorics 8.1.2 Applications of The Principle of Inclusion and Exclusion.
Combinatorics 8.2 Generalizations of The Principle - “Exactly” or “At Least”.
Combinatorics 8.3 Derangements - Nothing Is In Its Right Place.
Combinatorics 9.1 Generating Functions - Introductory Examples.
Combinatorics 9.2.1 Generating Functions - Fundamental Identity.
Combinatorics 9.2.2 Generating Functions - Finite Geometric Series.
Combinatorics 9.2.3 Generating Functions - Binomial and Extended Binomial Theorem.
Combinatorics 9.2.4 Generating Functions - Full Practice Questions.
Combinatorics 9.3 Partitions of Integers.
Combinatorics 10.1 First Order Linear Homogeneous Recurrence Relations.
Combinatorics 10.2.1 Second Order Linear Homogeneous Recurrence Relations.
Combinatorics 10.2.2 Higher Order Recurrence Relations and Word Problems.
Combinatorics 10.4 Recurrence Relations - The Method of Generating Functions.
Combinatorics 16.1 Group Theory - Definitions, Examples and Elementary Properties.
Combinatorics 16.10 Counting and Equivalence - Burnside’s Theorem.
Combinatorics 16.12 The Pattern Inventory - Polya’s Method of Enumeration.
Combinatorics 11.1 Graph Theory - Definitions and Examples.
Combinatorics 11.2 Subgraphs, Complements and Graph Isomorphisms.
Combinatorics 11.3 Euler Trails and Circuits.
Combinatorics 11.4 Planar Graphs and Euler's Theorem.
Combinatorics 11.5 Hamilton Paths and Cycles.
Combinatorics 11.6 Graph Coloring and Chromatic Polynomials.
Combinatorics 12.1 Trees - Definitions, Properties and Examples.
Combinatorics 12.2 Rooted Trees.
Combinatorics 13.1 Dijkstra’s Shortest Path Algorithm.
Combinatorics 13.2 Minimal Spanning Trees - The Algorithms of Kruskal and Prim.
Taught by
Kimberly Brehm
