Discrete Mathematics — Complete Formula Sheet
GATE CS Quick Reference — Sets, Relations, Functions, Graph Theory, Combinatorics, Number Theory, Recurrence Relations & Probability
Last Updated: April 2026
📌 How to Use This Sheet
- This is a comprehensive quick-reference for all Discrete Mathematics formulas tested in GATE CS.
- Formulas are grouped by topic — jump directly to the section you need using the table of contents.
- For full derivations, worked examples, and explanations, follow the links at each section to the detailed topic pages.
- Bookmark this page and review it during your GATE CS revision — it covers all 7 major DM topics in one place.
1. Sets & Power Sets
| Formula | Expression |
|---|---|
| Power set size | |P(A)| = 2n where n = |A| |
| Cartesian product size | |A × B| = |A| × |B| |
| Inclusion-Exclusion (2) | |A∪B| = |A|+|B|−|A∩B| |
| Inclusion-Exclusion (3) | |A∪B∪C| = |A|+|B|+|C|−|A∩B|−|B∩C|−|A∩C|+|A∩B∩C| |
| De Morgan (sets) | (A∪B)’ = A’∩B’ | (A∩B)’ = A’∪B’ |
| Symmetric difference | |A⊕B| = |A|+|B|−2|A∩B| |
| Subsets of size r | C(n,r) subsets of an n-element set |
| Number of divisors of n = p₁a₁…pₖaₖ | τ(n) = (a₁+1)(a₂+1)…(aₖ+1) |
2. Relations — Counting & Properties
| Type | Count (set with n elements) |
|---|---|
| All relations on A | 2n² |
| Reflexive relations | 2n²−n |
| Irreflexive relations | 2n²−n |
| Symmetric relations | 2n(n+1)/2 |
| Antisymmetric relations | 2n × 3n(n−1)/2 |
| Reflexive + Symmetric | 2n(n−1)/2 |
| Equivalence relations (= Bell number) | B(n): 1,2,5,15,52,203… for n=1,2,3,4,5,6 |
Equivalence relation = Reflexive + Symmetric + Transitive
Partial order (POSET) = Reflexive + Antisymmetric + Transitive
Total order = Partial order where every pair is comparable
3. Functions — Counting
For functions f: A → B where |A|=m, |B|=n:
| Type | Count | Condition |
|---|---|---|
| Total functions | nm | — |
| Injective (one-to-one) | P(n,m) = n!/(n−m)! | Requires n ≥ m |
| Surjective (onto) | ∑k=0n(−1)kC(n,k)(n−k)m | Requires m ≥ n |
| Bijective | n! | Requires m = n |
Inverse exists iff function is bijective.
(g ∘ f)(x) = g(f(x)) — apply f first, then g.
Order of element a in (ℤₙ,+) = n / gcd(a,n)
4. Graph Theory
| Formula | Expression |
|---|---|
| Handshaking Lemma | ∑deg(v) = 2|E|; odd-degree vertices count = even |
| Directed: in-deg = out-deg | ∑in-deg(v) = ∑out-deg(v) = |E| |
| Complete graph Kn edges | n(n−1)/2 |
| Complete bipartite Km,n edges | m × n |
| Euler Circuit condition | Connected + ALL degrees even |
| Euler Path condition | Connected + EXACTLY 2 odd-degree vertices |
| Tree: edges | n − 1 edges for n vertices |
| Labeled trees on n vertices | nn−2 (Cayley’s formula) |
| Forest: k components, n vertices | n − k edges |
| Euler’s planar formula | V − E + F = 2 (connected planar graph) |
| Planar bound | E ≤ 3V−6 (general); E ≤ 2V−4 (bipartite/triangle-free) |
| Binary tree (perfect, height h) | 2h+1−1 nodes; 2h leaves |
| Complete binary tree height | ⌊log₂n⌋ for n nodes |
| Chromatic number — bipartite | χ = 2 (non-empty) |
| Chromatic number — complete Kn | χ = n |
| Chromatic number — odd cycle | χ = 3 |
| Four Color Theorem | χ ≤ 4 for any planar graph |
5. Combinatorics
| Formula | Expression |
|---|---|
| Permutation P(n,r) | n! / (n−r)! |
| Combination C(n,r) | n! / (r!(n−r)!); symmetry: C(n,r)=C(n,n−r) |
| Pascal’s identity | C(n,r) = C(n−1,r−1) + C(n−1,r) |
| Binomial theorem | (x+y)n = ∑C(n,k)xkyn−k |
| Sum of binomial coefficients | ∑C(n,k) = 2n |
| Circular permutations | (n−1)! |
| Necklace permutations | (n−1)!/2 |
| Pigeonhole (basic) | n+1 objects, n boxes → ≥1 box has ≥2 objects |
| Pigeonhole (generalized) | kn+1 objects, n boxes → ≥1 box has ≥k+1 objects |
| Derangements D(n) | n![1−1+1/2!−1/3!+…+(−1)n/n!] ≈ n!/e |
| D(n) recurrence | D(n) = (n−1)[D(n−1)+D(n−2)]; D(1)=0, D(2)=1 |
| D values | D(3)=2, D(4)=9, D(5)=44, D(6)=265 |
| Stars & Bars (≥0) | x₁+…+xₖ=n, xᵢ≥0: C(n+k−1, k−1) |
| Stars & Bars (≥1) | x₁+…+xₖ=n, xᵢ≥1: C(n−1, k−1) |
| Surjections f:A→B (|A|=m, |B|=n) | ∑k=0n(−1)kC(n,k)(n−k)m |
6. Number Theory & Algebraic Structures
| Formula | Expression |
|---|---|
| GCD × LCM | gcd(a,b) × lcm(a,b) = |a × b| |
| Euclidean algorithm | gcd(a,b) = gcd(b, a mod b) |
| Euler’s totient φ(pᵏ) | pᵏ − pᵏ⁻¹ |
| Euler’s totient φ(n) | n × ∏p|n(1 − 1/p) |
| Fermat’s Little Theorem | ap−1 ≡ 1 (mod p) [p prime, gcd(a,p)=1] |
| Euler’s Theorem | aφ(n) ≡ 1 (mod n) [gcd(a,n)=1] |
| Modular inverse (prime mod) | a⁻¹ ≡ ap−2 (mod p) |
| CRT: unique solution mod | M = m₁×m₂×…×mₖ (pairwise coprime) |
| Lagrange’s theorem | |H| divides |G| for subgroup H of finite group G |
| Generators of ℤₙ | φ(n) generators (elements coprime to n) |
| Order of a in (ℤₙ,+) | n / gcd(a,n) |
| GF(q) exists iff | q = pⁿ for prime p, positive integer n |
7. Recurrence Relations
| Formula / Rule | Expression |
|---|---|
| Fibonacci F(n) | F(n−1)+F(n−2); closed: (φⁿ−ψⁿ)/√5; φ=(1+√5)/2 |
| Tower of Hanoi | T(n)=2T(n−1)+1; T(n)=2ⁿ−1 |
| Master Theorem T(n)=aT(n/b)+f(n) | p=logba |
| Master Case 1 (f slow) | f=O(np−ε) → T=Θ(np) |
| Master Case 2 (f equal) | f=Θ(nplogkn) → T=Θ(nplogk+1n) |
| Master Case 3 (f fast) | f=Ω(np+ε) + regularity → T=Θ(f(n)) |
| Binary search T(n)=T(n/2)+1 | Θ(log n) |
| Merge sort T(n)=2T(n/2)+n | Θ(n log n) |
| Homogeneous recurrence | Characteristic eqn → roots → general solution |
| Repeated root r (mult m) | Contributes (A₀+A₁n+…+Aₘ₋₁nᵐ⁻¹)rⁿ |
| Non-homogeneous (particular) | Try C×sⁿ; if s is char. root of mult m → C×nᵐ×sⁿ |
8. Probability & Distributions
| Formula | Expression |
|---|---|
| Conditional probability | P(A|B) = P(A∩B)/P(B) |
| Multiplication rule | P(A∩B) = P(A|B)P(B) = P(B|A)P(A) |
| Total probability | P(A) = ΣP(A|Bᵢ)P(Bᵢ) |
| Bayes’ theorem | P(Bᵢ|A) = P(A|Bᵢ)P(Bᵢ) / ΣP(A|Bⱼ)P(Bⱼ) |
| Independence | P(A∩B) = P(A)P(B) |
| Expectation (discrete) | E[X] = ΣxP(X=x) |
| Variance | Var(X) = E[X²]−(E[X])² |
| Linearity of expectation | E[aX+b] = aE[X]+b; E[X+Y]=E[X]+E[Y] |
| Variance of sum (independent) | Var(X+Y) = Var(X)+Var(Y) |
| Distribution | E[X] | Var(X) | PMF/PDF |
|---|---|---|---|
| Bernoulli(p) | p | p(1−p) | P(1)=p, P(0)=1−p |
| Binomial(n,p) | np | np(1−p) | C(n,k)pk(1−p)n−k |
| Geometric(p) | 1/p | (1−p)/p² | (1−p)k−1p, k≥1 |
| Poisson(λ) | λ | λ | e−λλk/k! |
| Uniform(a,b) | (a+b)/2 | (b−a)²/12 | 1/(b−a) |
| Normal(μ,σ²) | μ | σ² | (1/σ√2π)e−(x−μ)²/2σ² |
| Exponential(λ) | 1/λ | 1/λ² | λe−λx, x≥0 |