Skip to content
Tutorials Center
My learning

Topics

Lesson 68 of 68 · Practice and Review

Discrete Mathematics Cheat Sheet

A one-page discrete mathematics cheat sheet: formulas for logic, sets, counting, probability, number theory, graphs and recurrences, with Python one-liners.

This page is the whole course on a few screens: the formulas and facts you reach for most, each paired with the Python expression that computes it. Use it as a reminder, not as a first introduction; every row has a lesson behind it, linked at the end of each section. Two runnable blocks (one for logic, sets and counting, one for number theory, graphs and recurrences) execute the one-liners so you can see that the formulas agree with the code.

Conventions: n and k are non-negative integers, p and q are propositions, A and B are finite sets, G = (V, E) is a simple graph, and from math import comb, perm, factorial, gcd, lcm is assumed.

Six sheets in one

Logic Laws, tables, quantifiers.
Sets Operations and counting rules.
Counting nPr, nCr, stars and bars.
Number theory gcd, modular powers, bases.
1 / 2

Logic

Idea Formula or rule Python
Implication p → q ≡ ¬p ∨ q, false only when p is true and q is false (not p) or q
Biconditional p ↔ q is true when p and q have the same value p == q
Contrapositive p → q ≡ ¬q → ¬p (the converse q → p is not equivalent) implies(not q, not p)
De Morgan ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q not (p and q) == (not p or not q)
Exclusive or p ⊕ q ≡ (p ∨ q) ∧ ¬(p ∧ q) p != q
Distribution p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) brute force over product([True, False], repeat=3)
Absorption p ∨ (p ∧ q) ≡ p, p ∧ (p ∨ q) ≡ p same
Tautology / contradiction true for all rows / false for all rows all(f(*v) for v in rows) / not any(...)
∀ over a finite domain ∀x P(x) all(P(x) for x in D)
∃ over a finite domain ∃x P(x) any(P(x) for x in D)
Negating quantifiers ¬∀x P ≡ ∃x ¬P, ¬∃x P ≡ ∀x ¬P not all(...) == any(not ...)

Reminders: nested quantifiers do not commute (∀x ∃y is weaker than ∃y ∀x), and an implication with a false premise is vacuously true. Lessons: Propositional Logic, Truth Tables, Logical Equivalences and Laws, Predicates and Quantifiers.

Sets, relations and functions

Idea Formula or rule Python
Union, intersection A ∪ B, A ∩ B A | B, A & B
Difference, symmetric difference A − B, A △ B A - B, A ^ B
Subset A ⊆ B A <= B (proper subset: A < B)
Inclusion-exclusion (two sets) |A ∪ B| = |A| + |B| − |A ∩ B| len(A) + len(B) - len(A & B)
Inclusion-exclusion (three sets) add the singles, subtract the pairs, add the triple direct formula
Power set size |P(A)| = 2ⁿ 2 ** len(A)
Cartesian product size |A × B| = |A| · |B| len(list(product(A, B)))
Relation properties reflexive, symmetric, antisymmetric, transitive all((a, a) in R for a in S) and so on
Equivalence relation reflexive + symmetric + transitive, gives a partition group by a key function
Partial order reflexive + antisymmetric + transitive divisibility on 1..n
Injective / surjective / bijective one-to-one / onto / both len(set(f.values())) == len(f)
Injective maps from n to m elements m!/(m − n)! perm(m, n)
Functions from n to m elements mⁿ m ** n
Surjections from n onto m elements Σ (−1)ᵏ C(m, k) (m − k)ⁿ inclusion-exclusion sum

Lessons: Sets and Set Operations, Power Sets and Cartesian Products, Relations, Functions and Cardinality.

Counting and probability

Situation Formula Python
Product rule independent choices multiply a * b
Sum rule disjoint cases add a + b
Permutations of n n! factorial(n)
Ordered choice of k from n, no repeats n!/(n − k)! perm(n, k)
Unordered choice of k from n C(n, k) = n!/(k!(n − k)!) comb(n, k)
Ordered choice with repeats nᵏ n ** k
Multiset of size k from n types C(n + k − 1, k) comb(n + k - 1, k)
Arrangements with repeated items n!/(n₁! n₂! …) factorial(n) // (...)
Pascal's rule C(n, k) = C(n − 1, k − 1) + C(n − 1, k) comb
Row sum Σ C(n, k) = 2ⁿ sum(comb(n, k) for k in range(n + 1))
Binomial theorem (x + y)ⁿ = Σ C(n, k) xⁿ⁻ᵏ yᵏ expand with comb
Derangements Dₙ = n! Σ (−1)ᵏ/k!, k = 0..n sum((-1)**k * factorial(n) // factorial(k) ...)
Catalan numbers Cₙ = C(2n, n)/(n + 1) comb(2*n, n) // (n + 1)
Pigeonhole n + 1 objects in n boxes: some box has two reasoning
Probability P(E) = favorable / total (equally likely) Fraction(favorable, total)
Conditional probability P(A | B) = P(A ∩ B)/P(B) ratio
Bayes' theorem P(A | B) = P(B | A) P(A)/P(B) ratio
Independence P(A ∩ B) = P(A) P(B) product
Expected value E[X] = Σ x · P(X = x); E[X + Y] = E[X] + E[Y] always sum(x * p ...)

Lessons: Counting Principles, Permutations and Combinations, Binomial Theorem and Pascal's Triangle, Advanced Counting, Discrete Probability.

Python Logic, sets and counting one-liners

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Number theory and representations

Idea Formula or rule Python
Division algorithm a = q·d + r with 0 ≤ r < d q, r = divmod(a, d)
Divides d | n when n mod d = 0 n % d == 0
gcd, lcm gcd(a, b) · lcm(a, b) = a · b gcd(a, b), lcm(a, b)
Euclid gcd(a, b) = gcd(b, a mod b) while b: a, b = b, a % b
Bezout gcd(a, b) = ax + by for some integers x, y extended Euclid
Congruence a ≡ b (mod m) when m divides a − b (a - b) % m == 0
Modular power aᵇ mod m by repeated squaring pow(a, b, m)
Modular inverse exists iff gcd(a, m) = 1 pow(a, -1, m)
Linear congruence ax ≡ c (mod m) solvable iff gcd(a, m) divides c check gcd
Fermat aᵖ⁻¹ ≡ 1 (mod p), p prime and p ∤ a pow(a, p - 1, p) == 1
Euler's totient φ(n) = n Π (1 − 1/p) over primes p dividing n count gcd(k, n) == 1
Euler's theorem aᵠ⁽ⁿ⁾ ≡ 1 (mod n) when gcd(a, n) = 1 pow(a, phi, n)
Chinese remainder coprime moduli give a unique solution mod their product sum of rᵢ·Mᵢ·Mᵢ⁻¹
Prime test trial division up to √n all(n % d for d in range(2, isqrt(n) + 1))
Number of divisors if n = Π pᵃ then Π (a + 1) count n % d == 0
Base conversion repeated division by the base int("ff", 16), format(n, "b")
Two's complement (k bits) −x is stored as 2ᵏ − x (-x) & (2**k - 1)

RSA toy example: n = p·q, e coprime to (p − 1)(q − 1), d = e⁻¹ mod (p − 1)(q − 1), encrypt pow(m, e, n), decrypt pow(c, d, n). This is for learning only; never roll your own cryptography. Lessons: Divisibility and Primes, GCD, LCM and the Euclidean Algorithm, Modular Arithmetic, Number Bases and Representations, Number Theory in Cryptography.

Graphs

Idea Fact Python
Handshake lemma Σ deg(v) = 2|E| (so the number of odd-degree vertices is even) sum(deg.values()) == 2 * len(edges)
Complete graph Kₙ has n(n − 1)/2 edges comb(n, 2)
Adjacency list dict of vertex to neighbors adj[v].append(u)
Adjacency matrix Aᵏ[i][j] counts walks of length k matrix product
Connected components BFS or DFS from each unvisited vertex stack or deque
Tree connected and acyclic, n − 1 edges len(edges) == n - 1 and connected
Labeled trees Cayley: nⁿ⁻² n ** (n - 2)
Euler circuit connected and all degrees even degree check
Euler path connected with 0 or 2 odd vertices degree check
Bipartite no odd cycle (2-colorable) BFS coloring
Chromatic number 2 for bipartite graphs with an edge, 3 for odd cycles, n for Kₙ try k colors
Planar graph (simple, at least 3 vertices) |E| ≤ 3|V| − 6; V − E + F = 2 when connected inequality
MST Kruskal (sort edges plus union-find) or Prim (heap) heapq
Shortest path Dijkstra for non-negative weights heapq
Matching maximum via augmenting paths; Hall: |N(S)| ≥ |S| for all S DFS augment
Topological order exists iff the directed graph has no cycle Kahn's algorithm

Lessons: Graphs: Terms and Representations, Paths, Cycles and Connectivity, Euler and Hamilton Paths, Trees and Spanning Trees, Graph Coloring and Planarity, Shortest Paths, Matching and Flows.

Sequences and recurrences

Idea Formula
Arithmetic sequence aₙ = a₀ + nd; sum of the first n terms = n(a₁ + aₙ)/2
Geometric sequence aₙ = a₀ rⁿ; sum of a₀ + … + a₀rⁿ⁻¹ = a₀ (rⁿ − 1)/(r − 1)
Useful sums Σ i = n(n + 1)/2, Σ i² = n(n + 1)(2n + 1)/6, Σ 2ⁱ (i < n) = 2ⁿ − 1
Fibonacci Fₙ = Fₙ₋₁ + Fₙ₋₂; Binet: Fₙ = (φⁿ − ψⁿ)/√5
Linear recurrence aₙ = c₁aₙ₋₁ + c₂aₙ₋₂: solve r² = c₁r + c₂; distinct roots r₁, r₂ give aₙ = A r₁ⁿ + B r₂ⁿ; a double root r gives (A + Bn) rⁿ
Tower of Hanoi H(n) = 2H(n − 1) + 1 = 2ⁿ − 1
Master theorem T(n) = aT(n/b) + Θ(nᵈ): Θ(nᵈ) if a < bᵈ, Θ(nᵈ log n) if a = bᵈ, Θ(n^(log_b a)) if a > bᵈ
Induction prove the base case, then P(k) → P(k + 1)
Strong induction assume P(j) for all j ≤ k, prove P(k + 1)

Lessons: Sequences and Summations, Recurrence Relations, Solving Recurrences, Mathematical Induction.

Python Number theory, graphs and recurrences one-liners

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Quick tips

  • When a formula and a brute-force count disagree on a small case, trust the brute force and look for a missed or double-counted case.
  • Use exact arithmetic (Fraction, integers, pow(a, b, m)) for discrete problems; floating point rounds.
  • Name the model before the formula: ordered or unordered, repeats or not, directed or undirected, simple graph or multigraph.
  • Check boundaries: n = 0, n = 1, empty sets, a single vertex, a base case of induction.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. How many multisets of size 3 can be chosen from 5 types of item?

    Stars and bars gives C(n + k - 1, k) = C(7, 3) = 35. Ordered choices with repeats would be 5^3 = 125, and unordered without repeats C(5, 3) = 10.
  2. 2. Which Python expression computes the modular inverse of 3 modulo 7?

    pow(a, -1, m) returns the inverse when gcd(a, m) = 1 and raises ValueError otherwise. 3 ** -1 is the float 0.333...
  3. 3. A recurrence T(n) = 2T(n/2) + n has a = 2, b = 2, d = 1. What does the Master theorem give?

    Here a = b^d (2 = 2^1), the balanced case, so the answer is Theta(n^d log n) = Theta(n log n).
  4. 4. What does the handshake lemma say?

    Every edge contributes 1 to the degree of each of its two endpoints, so the degree sum is 2|E|, always even.

Summary

  • Logic: implication is ¬p ∨ q, the contrapositive is equivalent, De Morgan swaps and/or, and quantifiers over finite domains are all and any.
  • Sets and counting: inclusion-exclusion, 2ⁿ subsets, perm, comb, stars and bars, derangements and Catalan numbers cover most counting questions.
  • Number theory: gcd, pow(a, b, m) and pow(a, -1, m) solve the everyday problems; Fermat, Euler and the Chinese remainder theorem explain why.
  • Graphs: degree sum 2|E|, trees have n − 1 edges, Euler circuits need even degrees, bipartite means no odd cycle.
  • Recurrences: unroll or use the characteristic equation for closed forms, and the Master theorem for divide-and-conquer.

You have reached the end of the course. Revisit Common Mistakes and Pitfalls or the exercise sets such as Exercises: Counting and Number Theory whenever you want to practice again.