"How many equivalence relations are there on a set of n elements?" This question looks like it wants you to somehow list relations and weed out the non-equivalence ones. That is the brute-force trap. The clean recognition is this: every equivalence relation on A is the same data as a partition of A. So counting equivalence relations reduces to counting partitions — and the count of partitions of an n-element set is a named sequence, the Bell numbers B(n).
The recognition rule
When you see "number of equivalence relations on \{a_1, a_2, \ldots, a_n\}," translate instantly:
Once the question becomes "number of partitions of a set of n elements," the answer is the Bell number B(n). For small n you can compute B(n) by hand; for JEE you rarely need values beyond n = 4 or n = 5.
Why the bijection holds: an equivalence relation groups every element into an equivalence class; the classes are non-empty, disjoint, and together cover all of A — that is exactly the definition of a partition. Going the other way, any partition defines a relation ("related iff in the same block") that you can verify is reflexive, symmetric, and transitive. One bidirectional translation; no counting to do beyond the partitions.
The first few Bell numbers
These are the ones that show up in problems.
| n | B(n) | Partitions of \{1, 2, \ldots, n\} |
|---|---|---|
| 0 | 1 | \varnothing (the empty partition) |
| 1 | 1 | \{\{1\}\} |
| 2 | 2 | \{\{1\},\{2\}\}, \{\{1,2\}\} |
| 3 | 5 | listed below |
| 4 | 15 | too many to list — you count them |
| 5 | 52 | rarely asked in closed form |
For n = 3 on A = \{1, 2, 3\}, the five partitions are:
- \{\{1\}, \{2\}, \{3\}\} — the identity relation (only (a, a) pairs).
- \{\{1, 2\}, \{3\}\} — class \{1, 2\} with singleton \{3\}.
- \{\{1, 3\}, \{2\}\}
- \{\{2, 3\}, \{1\}\}
- \{\{1, 2, 3\}\} — the universal relation (every pair related).
So there are exactly 5 equivalence relations on \{1, 2, 3\}. Not 2^{9} = 512 (the total number of relations). Not 2^{3} = 8. Exactly 5.
The visual: partitions as colouring
Think of a partition as a colouring of the n elements where two elements share a colour iff they are in the same block. The number of colours used is the number of classes, and it can be anywhere from 1 to n.
Breaking B(n) down by number of classes
Sometimes a question asks "how many equivalence relations with exactly k classes are there?" The answer is the Stirling number of the second kind S(n, k). The Bell number B(n) is simply the sum:
For n = 3: S(3, 1) = 1 (one class with all three), S(3, 2) = 3 (three ways to pair two), S(3, 3) = 1 (all singletons). Total 1 + 3 + 1 = 5 = B(3). The table of small Stirling numbers:
| n \backslash k | 1 | 2 | 3 | 4 | 5 | B(n) |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | ||||
| 2 | 1 | 1 | 2 | |||
| 3 | 1 | 3 | 1 | 5 | ||
| 4 | 1 | 7 | 6 | 1 | 15 | |
| 5 | 1 | 15 | 25 | 10 | 1 | 52 |
Common JEE variations use this split:
- "Number of equivalence relations with exactly 2 classes" on \{1,2,3\} → S(3, 2) = 3.
- "Number of equivalence relations on \{1,2,3,4\} containing the pair (1,2)" → count partitions where 1 and 2 share a block; this is a separate count, not a Bell number, but you now know to reach for partitions, not pairs.
The brute-force comparison
A student who does not see the partition bijection might try: "Pick a subset of A \times A, check if it is reflexive, symmetric, transitive." Let us cost this for n = 3:
- Total subsets of A \times A: 2^9 = 512.
- Of these, how many satisfy all three properties? We know the answer is 5. So you would check 512 subsets to find 5 — a 1\% hit rate.
- For n = 4: 2^{16} = 65{,}536 subsets, and only 15 are equivalences. Hit rate 0.023\%.
Listing partitions directly goes from 5 answers to 5 list entries. No wasted work. The partition recognition is not a shortcut; it is the natural formulation of the question.
The recognition checklist
When you see a counting question involving equivalence relations:
- Ask: is this really a partition-counting question in disguise?
- Translate: equivalence relations \leftrightarrow partitions.
- Identify which count: all partitions (B(n)), partitions with k blocks (S(n, k)), or partitions satisfying a constraint (enumerate directly for small n).
- Verify with tiny n: for n = 2 or n = 3, list them to catch any miscounting.
JEE 2020-style: equivalence relations on a 4-element set
Problem: Let A = \{1, 2, 3, 4\}. How many equivalence relations on A contain the pair (1, 2) but not the pair (3, 4)?
Translate. Equivalence relations ↔ partitions of A. The pair (1, 2) \in R means 1 and 2 are in the same block. "(3, 4) \notin R" means 3 and 4 are not in the same block.
Count partitions with the constraint. Fix the block containing \{1, 2\}. The question is where to place 3 and 4 such that they are in different blocks.
Cases by block containing \{1, 2\}:
- Block is \{1, 2\} only. Then 3 and 4 each go into blocks not equal to \{1,2\} and not equal to each other. Options: \{3\}, \{4\} — both singletons; or \{3\}, \{4\} as separate blocks. That is 1 way.
- Block is \{1, 2, 3\}. Then 4 goes into its own block \{4\}. That is 1 way. (Automatically 3 and 4 are in different blocks.)
- Block is \{1, 2, 4\}. Symmetric: 3 is alone. 1 way.
- Block is \{1, 2, 3, 4\}. Then 3 and 4 are in the same block — forbidden. 0 ways.
Total: 1 + 1 + 1 = 3 equivalence relations.
Without the partition translation, this problem is almost unsolvable — you would be listing subsets of a 16-element grid with three property checks apiece.
Train the reflex: "equivalence relations" means "partitions". Every time. No exceptions on a finite set.
Related: Relations · Equivalence Relations · What Counts as an Equivalence Class — How to List All of Them · Equivalence-Class Partition: Coloured Blocks