Skip to content

Lesson 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.