Benjamin A.T. Discrete Mathematics

The Great Courses, 2009. — 262 p.Discrete mathematics can be described as an advanced look at the mathematics that we learned as children. In elementary school, we learned to count, did basic arithmetic, and amused ourselves with solving puzzles, ranging from connecting the dots, to coloring, to more sophisticated creative pursuits.
So what exactly is discrete mathematics? Perhaps it is easier to first say what it is not. Most of the mathematics that we are taught in high school — from geometry through calculus — is continuous mathematics. Think of the second hand of a wristwatch or the path traveled by a ball as it is thrown in the air. These objects are typically described by real numbers and continuous functions. By contrast, discrete mathematics is concerned with processes that occur in separate chunks, such as how the seconds or minutes change on a digital watch, or the way the path of the ball would look if we took a few snapshots of its journey. The numbers used in discrete mathematics are whole numbers. Discrete mathematics is the foundation of computer science, where statements are true or false, numbers are represented with finite precision, and every piece of data is stored in a specific place.
In this course, we concentrate on 3 major fields of discrete mathematics: combinatorics, number theory, and graph theory. Combinatorics is the mathematics of counting. How many ways can we rearrange the letters of “Mississippi”? How many different lottery tickets can be printed? How many ways can we be dealt a full house in poker? Central to the answers to these questions is Pascal’s triangle, whose numbers contain some amazingly beautiful patterns, which we shall explore.What Is Discrete Mathematics?
Basic Concepts of Combinatorics
The 12-Fold Way of Combinatorics
Pascal’s Triangle and the Binomial Theorem
Advanced Combinatorics — Multichoosing
The Principle of Inclusion-Exclusion
Proofs — Inductive, Geometric, Combinatorial
Linear Recurrences and Fibonacci Numbers
Gateway to Number Theory — Divisibility
The Structure of Numbers
Two Principles — Pigeonholes and Parity
Modular Arithmetic — The Math of Remainders
Enormous Exponents and Card Shuffling
Fermat’s “Little” Theorem and Prime Testing
Open Secrets — Public Key Cryptography
The Birth of Graph Theory
Ways to Walk — Matrices and Markov Chains
Social Networks and Stable Marriages
Tournaments and King Chickens
Weighted Graphs and Minimum Spanning Trees
Planarity — When Can a Graph Be Untangled?
Coloring Graphs and Maps
Shortest Paths and Algorithm Complexity
The Magic of Discrete Mathematics