Discrete Structures in Mathematics: a Problem-Solving Approach (Free PDF Textbook)

(with lots of practical applications, help, and hints to solve the hard problems)

by Prof. Gregory V. Bard

Chapter 0: Advice to the Student
- Module 0.1: The Preface (How to Use This Book) (click here)
- Module 0.2: The Seven Pitfalls of Students in Discrete Mathematics (click here)
Chapter 1: Set Theory
- Module 1.1: Introduction to Set Theory (click here)
- Module 1.2: Basic Venn Diagram Problems (click here)
- Module 1.3: Intermediate Venn Diagram Problems (click here)
- Module 1.4: Advanced Venn Diagram Problems (click here)
Chapter 2: The Basics of Number Theory
- Module 2.1: Changing Between Number Bases [Planned]
- Module 2.2: Intermediate Set Theory and Irrationality (click here)
- Module 2.3: Set Theory meets Number Theory (click here)
Chapter 3: The Basics of Probability
- Module 3.1: A Formal Introduction to Probability Theory (click here)
- APPLET: Throwing 1000 darts at the unit circle, to estimate pi (a Monte-Carlo Simulation) (powered by SageMathCell)
- Module 3.2: Exploring Probability Through Problem Solving (click here)
- Module 3.3: You Can't Just Add Probabilities (click here)
- Module 3.4: Expected Value and Insurance (click here)
- Module 3.5: The Square Root of NPQ Rule (click here)
Chapter 4: Combinatorics
- Module 4.1: The Multiplication and Exponent Principles (click here)
- Module 4.2: The Permutations and Factorial Principles (click here)
- Module 4.3: The Combinations and Handshake Principles (click here)
- Module 4.4: The Missing Principle of Combinatorics (click here) (micromodule)
- Module 4.5: Which Combinatorial Formula Should I Use? (click here)
- Module 4.6: Pascal's Triangle and the Binomial Theorem (click here)
- Handy Reference Sheet for Pascal's Triangle and the Binomial Theorem (click here)
- Module 4.7: Some Advanced Combinatorial Principles [Underway]
Chapter 5: Advanced Topics in Probability
- Module 5.1: Probability Tree Diagrams (click here)
- Module 5.2: Independence and Repetition (click here)
- Module 5.3: Bernoulli's Binomial Distribution Formula and Reliability Engineering (click here)
- APPLET: The Binomial Distribution Formula helper (powered by SageMathCell)
- Module 5.4: Conditional Probability Notation and Bayes' Rule [Underway]
- Module 5.5: Probability, Dice Games, and Odds [Underway]
- Module 5.6: A Combinatorial View of Poker (5-Card Stud) [Planned]
Chapter 6: Intermediate Logic
- Module 6.1: Disproof of Hypotheses by Counter-Example [Underway]
- Module 6.2: The Logic Game: Ten Levels of Problems Toward Mathematical Logic, and Set Theory (without answers) (with answers)
- Module 6.3: Contrapositives and Converses (click here)
- Module 6.4: More about Implications [Planned]
- Module 6.5: Working with Quantifiers [Planned]
- Module 6.6: Negating Long First-Order Logical Sentences [Planned]
Chapter 7: Proof-Writing Techniques [Planned]
Chapter 8: Mathematical Induction and Recursive Sequences [Underway]
Chapter 9: The Theory of Digraphs and Graphs [Planned]
Chapter 10: Modular Arithmetic and Cryptography
- Module 10.1: Exploring Steganography with the Baconian Cipher (click here)
- Several Cayley Tables, useful for what follows (click here)
- Module 10.2: The Basics of Modular Arithmetic (click here)
- Module 10.3: All about Modular Inverses (click here)
- Module 10.4: Some Historical Ciphers [Under Major Renovation!]
- Module 10.5: Euler's Totient Function and Modular Exponentiation (without answers) (with answers)
- APPLET: The Modular Exponentiation helper (powered by SageMathCell)
- APPLET: Exploring Euler's Totient Theorem (powered by SageMathCell)
- Module 10.6: Introducing the RSA Cryptosystem (without answers) (with answers)
- APPLET: Key Generator for the RSA Cryptosystem (powered by SageMathCell)
- Module 10.7: Exploring the RSA Cryptosystem (without answers) (with answers)
- For Science Olympiad students, I'm including some older materials.
  - Old Module 10.2: A Worksheet about the Basics of Modular Arithmetic (without answers) (with answers)
  - Old Module 10.4: Some Historical Ciphers (without answers) (with answers)
  - Old Module 10.4-and-a-half: Exploring the Vigenère Cipher (without answers) (with answers)
Appendix A: Good Old-Fashioned Mathematics
- Module A.1: Converting Between Different Number Bases [Planned]
- Module A.2: Completing the Square (and Applications) [Underway]
- Module A.3: Cardano's Method for Solving Cubic Equations [Underway]
- Module A.4: The Pigeon-Hole Principle [Planned]
- Module A.5: Injective, Surjective, and Bijective Functions (click here)
- Module A.6: Equivalence Relations (Reflexive, Symmetric, Transitive) (click here)
- Module A.7: Fermat's Last Theorem and Famous Unsolved Problems [Under Major Repairs]
- Module A.8: About Poisson's Theorem on Rare Events [Underway]
Appendix B: A Lab Packet about Dijkstra's Algorithm (without answers) (with answers)

Special thanks to my proofreaders:

I am very indebted to my chief proofreader, Joseph Bertino, who has now moved onto much bigger and better things, but who served me well for nine years; my senior proofreaders, Russel Chamberlain, Isaac Quella, and Tanner Verber, who also served me well for years, but who have now moved on to bigger projects; and my current proofreaders, Ryan Hornberger and Trevor Kretschmann, upon whom I am entirely dependent. I must also mention my gratitude for students from MATH-270: Discrete Mathematics, many of whom have reported a typo or two. Thanks very much!

Other Discrete Mathematics Resources:

To see more great free stuff about discrete mathematics (by other authors), please visit the Discrete Math Resources and Help page. There are lots of useful resources there for both students and course instructors.

To Contact me, or to Notify me of Typos or Other Errors:

If you notice any typos, grammar errors, or mathematical issues, then please write to me (Prof. Gregory V. Bard) at the following email address. I will be very happy to hear from you. I would also happily accept any recommendations about online resources, tutorials, free textbooks, practice exercises, course syllabi, or anything that will help discrete math students solve problems. (The email address below is an image, to protect me from spam bots.) Please place "Discrete Math Hub" in the subject line. Feel free to also visit my professional webpage or my personal webpage.

$An image to display my email address, which is the reverse of ude.tuotswu@gdrab (Read it backwards.)$

Last Updated on December 11th, 2020.