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)\| = 2ⁿ 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)

→ Full Sets, Relations & Functions Guide

2. Relations — Counting & Properties

Type	Count (set with n elements)
All relations on A	2^n²
Reflexive relations	2^n²−n
Irreflexive relations	2^n²−n
Symmetric relations	2^n(n+1)/2
Antisymmetric relations	2ⁿ × 3^n(n−1)/2
Reflexive + Symmetric	2^n(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

→ Full Guide

3. Functions — Counting

For functions f: A → B where |A|=m, |B|=n:

Type	Count	Condition
Total functions	n^m	—
Injective (one-to-one)	P(n,m) = n!/(n−m)!	Requires n ≥ m
Surjective (onto)	∑_k=0ⁿ(−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)

→ Full Guide

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 K_n edges	n(n−1)/2
Complete bipartite K_m,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	nⁿ⁻² (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)	2^h+1−1 nodes; 2^h leaves
Complete binary tree height	⌊log₂n⌋ for n nodes
Chromatic number — bipartite	χ = 2 (non-empty)
Chromatic number — complete K_n	χ = n
Chromatic number — odd cycle	χ = 3
Four Color Theorem	χ ≤ 4 for any planar graph

→ Full Graph Theory Guide

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)ⁿ = ∑C(n,k)x^ky^n−k
Sum of binomial coefficients	∑C(n,k) = 2ⁿ
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!/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=0ⁿ(−1)^kC(n,k)(n−k)^m

→ Full Combinatorics Guide

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	a^p−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⁻¹ ≡ a^p−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

→ Full Number Theory Guide

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=log_ba
Master Case 1 (f slow)	f=O(n^p−ε) → T=Θ(n^p)
Master Case 2 (f equal)	f=Θ(n^plog^kn) → T=Θ(n^plog^k+1n)
Master Case 3 (f fast)	f=Ω(n^p+ε) + 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ⁿ

→ Full Recurrence Relations Guide

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)p^k(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

→ Full Probability Guide

Next Steps — Explore Each Topic in Depth

This formula sheet is your revision companion. For full explanations and worked examples, visit each topic page:

Propositional & Predicate Logic — Logical operators, truth tables, quantifiers, normal forms
Sets, Relations & Functions — Full relation counting, POSET, Hasse diagrams, function composition
Graph Theory — Full coverage of trees, spanning trees, planarity, coloring
Combinatorics — Permutations, combinations, pigeonhole, derangements, Stars & Bars
Number Theory & Algebra — GCD, Fermat, Euler, groups, rings, fields
Recurrence Relations — Characteristic roots, Master theorem, generating functions
Probability — Bayes theorem, expectation, variance, distributions

Discrete Mathematics Formula Sheet — GATE CS Quick Reference