Explore advanced concepts in discrete mathematics and combinatorics through a comprehensive 12-hour course based on Grimaldi's "Discrete and Combinatorial Mathematics." Delve into fundamental principles like the Rules of Sum and Product, permutations, combinations, and the Binomial Theorem. Master mathematical induction, recursive definitions, and the Pigeonhole Principle. Study advanced topics including the Principle of Inclusion and Exclusion, derangements, generating functions, and partitions of integers. Investigate recurrence relations, group theory, and Burnside's Theorem. Examine graph theory concepts such as Euler trails, planar graphs, Hamilton paths, and graph coloring. Explore trees, rooted trees, and algorithms like Dijkstra's Shortest Path and minimal spanning trees. Gain a solid foundation in discrete mathematics and combinatorics applicable to various fields in computer science and mathematics.
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
