Discrete Mathematics Formulas: A Cheat Sheet with Examples

Last updated 3 November 2026 · Part of the Discretiq guides

This page collects the formulas students need most in a first discrete mathematics course, grouped by topic, each with a small numeric example so you can see it work. Memorising a formula helps less than knowing when it applies, so each group notes the condition to check.

Logic

Law	Formula
De Morgan	¬(P ∧ Q) ≡ ¬P ∨ ¬Q; ¬(P ∨ Q) ≡ ¬P ∧ ¬Q
Implication	P → Q ≡ ¬P ∨ Q ≡ ¬Q → ¬P (contrapositive)
Biconditional	P ↔ Q ≡ (P → Q) ∧ (Q → P)
Rows in a truth table	2ⁿ for n variables

Sets

Idea	Formula	Example
Inclusion–exclusion	\|A ∪ B\| = \|A\| + \|B\| − \|A ∩ B\|	30 + 20 − 8 = 42
Subsets of an n-set	2ⁿ	5 elements: 32 subsets
Cartesian product size	\|A × B\| = \|A\| · \|B\|	3 · 4 = 12
De Morgan for sets	(A ∪ B)ᶜ = Aᶜ ∩ Bᶜ

Counting

Idea	Formula	Example
Permutations	P(n, r) = n!/(n − r)!	P(10, 3) = 720
Combinations	C(n, r) = n!/(r!(n − r)!)	C(10, 3) = 120
With repetition, order matters	nʳ	3² = 9
With repetition, order ignored	C(n + r − 1, r)	C(4, 2) = 6
Symmetry	C(n, r) = C(n, n − r)
Row sum of Pascal's triangle	Σ C(n, k) = 2ⁿ	n = 5: 32

Sums and sequences

Idea	Formula	Example
Sum of 1 to n	n(n + 1)/2	n = 100: 5,050
Geometric sum	Σ rⁱ (i = 0..n) = (rⁿ⁺¹ − 1)/(r − 1)	r = 2, n = 9: 1,023
Sum of first n odd numbers	n²

Number theory

Idea	Formula	Example
GCD and LCM	gcd(a, b) · lcm(a, b) = \|ab\|	gcd(252, 105) = 21, lcm = 1,260
Euclid	gcd(a, b) = gcd(b, a mod b)
Totient of a prime power	φ(pᵏ) = pᵏ − pᵏ⁻¹	φ(49) = 42
Fermat's little theorem	aᵖ⁻¹ ≡ 1 (mod p), p prime, p ∤ a	3⁶ ≡ 1 (mod 7)

Graphs and trees

Idea	Formula	Example
Handshaking lemma	Σ deg(v) = 2\|E\|
Edges in complete graph Kₙ	n(n − 1)/2	K₆: 15
Edges in a tree	\|V\| − 1
Euler's formula (connected planar graph)	V − E + F = 2

Relations and functions

Idea	Formula	Example
Relations on an n-set	2^(n²)	n = 3: 2⁹ = 512
Functions from m to n elements	nᵐ	4 → 3: 81
One-to-one functions from m to n elements	P(n, m)	3 → 5: 60

Using the formulas safely

Check the conditions first: Fermat's theorem needs a prime modulus, Euler's formula needs a connected planar graph.
Substitute a tiny case to test your formula before trusting it with big numbers.
Use a calculator to check the final value, but write the working yourself.

Frequently asked questions

Which formulas matter most for exams?

Counting formulas, logical equivalences, the gcd and Euclid facts, the handshaking lemma and sum formulas appear most often in introductory courses.

Are these formulas the same in every textbook?

The mathematics is, but notation varies, for example nCr versus C(n, r).

Try it yourself

Work the examples above by hand first, then confirm your answers.

Follow the learning path through every topic in order

References and further reading

Rosen, K. H. Discrete Mathematics and Its Applications. McGraw-Hill (standard undergraduate text).
Graham, R., Knuth, D., Patashnik, O. Concrete Mathematics. Addison-Wesley.