Discrete Math

Every lesson explains the concept, works through examples, and gives you practice problems with full solutions. Work through them in order, or jump to the topic you need.

32 lessons

  1. Counting Divisors: τ(n), σ(n) and Perfect NumbersCount and add the divisors of n from its prime factorization: τ(n) multiplies (exponent + 1), σ(n) multiplies geometric sums. Find perfect numbers like 6, 28 and 496.CoreUndergraduate
  2. Counting Lattice Paths on a GridCount shortest grid paths with right and up steps: there are C(m + n, m) paths to (m, n). Multiply to count paths through a point; subtract to avoid it.CoreUndergraduate
  3. Propositional Logic and Truth TablesCombine statements with and, or, not and if–then, build truth tables, and spot equivalent forms: the contrapositive, De Morgan's laws and why the converse differs.AdvancedUndergraduate
  4. Predicate Logic: Quantifiers ∀ and ∃ and Their NegationsWrite statements with 'for all' and 'there exists', negate them by flipping the quantifier, and see why the order of nested quantifiers changes the meaning.AdvancedUndergraduate
  5. Sets, Set Operations and Inclusion–ExclusionWork with sets: union, intersection, difference and complement, subsets and power sets, and count overlapping groups with the inclusion–exclusion principle.AdvancedUndergraduate
  6. Proof Techniques: Direct, Contrapositive and ContradictionLearn the three standard ways to prove a statement: a direct proof from definitions, a proof of the contrapositive, and proof by contradiction, with classic examples.AdvancedUndergraduate
  7. Combinatorial Proofs and Binomial Coefficient IdentitiesProve identities like Pascal's rule, the row sum 2ⁿ and Vandermonde's identity by counting one set in two different ways, with no algebra needed.AdvancedUndergraduate
  8. Modular Arithmetic and CongruencesArithmetic with remainders: what a ≡ b (mod n) means, why you can reduce before adding or multiplying, fast powers, last digits, days of the week and modular inverses.AdvancedUndergraduate
  9. Number Bases: Binary, Hexadecimal and Base bRead numbers in base 2, 3, 5 and 16 using place values that are powers of the base, convert from base 10 by repeated division, and turn binary into hex.IntroUndergraduate
  10. Boolean Algebra and Logic GatesCompute with 0 and 1 using AND, OR and NOT, simplify expressions with the Boolean laws, build a formula from a truth table, and design circuits like a half adder.AdvancedUndergraduate
  11. Stars and Bars: Combinations with RepetitionCount ways to share identical objects among groups with stars and bars: C(n + k − 1, k − 1) ways with empty groups allowed, C(n − 1, k − 1) when each gets one.CoreUndergraduate
  12. Inclusion–Exclusion in General: Derangements and Onto FunctionsCount the objects with none of several properties by alternately subtracting and adding overlaps. Count derangements, onto functions and numbers free of given divisors.AdvancedUndergraduate
  13. Strong Induction and the Well-Ordering PrincipleProve statements where each case depends on several earlier ones: assume all cases up to k, prove case k + 1, and supply enough base cases to start the chain.AdvancedUndergraduate
  14. The Euclidean Algorithm and Bézout's IdentityFind the greatest common divisor of two large numbers by repeated division, write it as a combination ax + by with the extended algorithm, and compute modular inverses.AdvancedUndergraduate
  15. Euler's Totient Function φ(n)Count the numbers up to n that share no factor with n. Compute φ(n) from the prime factorization with φ(n) = n(1 − 1/p₁)(1 − 1/p₂)⋯, and use φ(mn) = φ(m)φ(n).CoreUndergraduate
  16. The Chinese Remainder TheoremSolve systems like x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7): with pairwise coprime moduli there is exactly one solution modulo their product.AdvancedUndergraduate
  17. Linear Diophantine Equations: Whole-Number Solutions of ax + by = cDecide whether ax + by = c has integer solutions with the gcd test, find one with the extended Euclidean algorithm, write them all, and count the nonnegative ones.AdvancedUndergraduate
  18. The Pigeonhole PrincipleIf more objects than boxes are placed in boxes, some box holds two. Use the pigeonhole principle and its general form ⌈n/k⌉ to prove that something must happen.AdvancedUndergraduate
  19. Graphs, Degrees and the Handshaking LemmaGraph theory basics: vertices, edges, degree, paths and connectedness. Prove that degrees add to twice the number of edges, and count edges in complete graphs and trees.AdvancedUndergraduate
  20. Euler and Hamilton Paths: The Bridges of KönigsbergWhen can you trace every edge of a graph once? Euler's theorem answers by counting odd-degree vertices. Contrast it with Hamilton paths, which visit every vertex once.AdvancedUndergraduate
  21. Recurrence Relations and How to Solve ThemDefine sequences by recurrence, like Fibonacci and the Tower of Hanoi, and solve linear recurrences with a characteristic equation to get a closed formula.AdvancedUndergraduate
  22. Catalan Numbers: Paths, Parentheses and TriangulationsThe Catalan numbers 1, 1, 2, 5, 14, 42, … count balanced parentheses, lattice paths that stay below the diagonal and polygon triangulations. Use Cₙ = C(2n, n)/(n + 1).CoreUndergraduate
  23. Generating Functions: Counting with Power SeriesEncode a sequence as the coefficients of a power series, multiply series to count combinations, and use generating functions to solve recurrences like Fibonacci.AdvancedUndergraduate
  24. One-to-One, Onto and Bijective FunctionsClassify functions between sets as one-to-one, onto or both, count the functions between finite sets, and see why only bijections have inverses.AdvancedUndergraduate
  25. Countable and Uncountable Sets: Sizes of InfinityCompare infinite sets with bijections: the integers and the rationals can be listed like the natural numbers, but Cantor's diagonal argument shows the reals cannot.AdvancedUndergraduate
  26. Relations, Equivalence Relations and Partial OrdersTest a relation for the reflexive, symmetric, antisymmetric and transitive properties, find equivalence classes, and see how equivalence relations split a set into parts.AdvancedUndergraduate
  27. Trees, Spanning Trees and Kruskal's AlgorithmLearn what makes a graph a tree, why a tree on n vertices has n − 1 edges, and find a minimum spanning tree of a weighted network with Kruskal's algorithm.AdvancedUndergraduate
  28. Planar Graphs and Euler's Formula V − E + F = 2Draw graphs without crossing edges, count faces, and prove Euler's formula V − E + F = 2. Use E ≤ 3V − 6 to show that K₅ and K₃,₃ are not planar.AdvancedUndergraduate
  29. Graph Coloring and the Chromatic NumberColor the vertices of a graph so that neighbors differ, find the chromatic number, test for two-colorability with odd cycles, and schedule exams with no conflicts.AdvancedUndergraduate
  30. Shortest Paths and Dijkstra's AlgorithmFind the shortest route through a weighted network with Dijkstra's algorithm: keep tentative distances, finalize the closest vertex, and update its neighbors.AdvancedUndergraduate
  31. Fermat's Little Theorem and Euler's TheoremReduce huge powers mod n: a^(p−1) ≡ 1 (mod p) for a prime p, and a^φ(n) ≡ 1 (mod n) when gcd(a, n) = 1. Find remainders, last digits and modular inverses.CoreUndergraduate
  32. RSA Encryption: Public Keys from Modular ArithmeticBuild RSA keys from two primes, encrypt with c = mᵉ mod n, decrypt with m = cᵈ mod n, and see why it works (Euler's theorem) and why it is secure (factoring is hard).AdvancedUndergraduate