Equivalence Relations · step 8 of 13

Counting equivalence relations

Because equivalence relations correspond exactly to partitions, counting them means counting partitions. The total for an n-set is the Bell number Bₙ, and the count with exactly k classes is the Stirling number of the second kind S(n,k). For small n the reliable exam method is to enumerate by block-size pattern, which is systematic enough to guarantee completeness.

Practise counting equivalence relations free → All Equivalence Relations subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

List the block-size patternsFor n = 4: 4; 3+1; 2+2; 2+1+1; 1+1+1+1. Every partition has exactly one pattern.
Count partitions of each patternUse binomial coefficients, dividing by the symmetry when blocks of equal size are interchangeable.
Add up to get BₙBell numbers: B₁ = 1, B₂ = 2, B₃ = 5, B₄ = 15, B₅ = 52.
Use S(n,k) when a class count is fixedS(n,k) = k·S(n−1,k) + S(n−1,k−1), with the whole row summing to Bₙ.

Worked example

How many equivalence relations are there on a 4-element set?

Pattern 4: one block containing everything — 1 partition.
Pattern 3+1: choose the singleton, C(4,1) = 4.
Pattern 2+2: choose the partner of element 1, giving 3 ways (the other pair is forced).
Pattern 2+1+1: choose the pair, C(4,2) = 6. Pattern 1+1+1+1: 1.

Answer. 1 + 4 + 3 + 6 + 1 = 15 equivalence relations, which is the Bell number B₄.

Where marks get dropped

These are the specific errors that cost credit on counting equivalence relations questions — QED's rubric penalises each of them separately.

Double-counting the 2+2 case. Choosing {1,2} and {3,4} is the same partition as choosing {3,4} and {1,2}, so C(4,2) = 6 must be halved to 3.
Counting ordered blocks. Partitions are unordered collections; labelling the blocks over-counts by k!.
Confusing Bₙ with 2ⁿ or n!. For n = 4 those give 16 and 24, neither of which is 15.

Practise this until it is automatic

Unlimited fresh questions

QED generates new counting equivalence relations problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Equivalence Relations mastery is tracked so you know when this is exam-ready.

Counting equivalence relations — frequently asked questions

What is the formula for Bell numbers?

The recurrence Bₙ₊₁ = Σₖ C(n,k)Bₖ, obtained by choosing the block containing a fixed element. There is no simple closed form, but the recurrence computes them quickly.

What does S(n,k) count?

Partitions of an n-set into exactly k non-empty unlabelled blocks. S(4,2) = 7, which matches the 4 partitions of pattern 3+1 plus the 3 of pattern 2+2.

How does this differ from counting surjections?

Surjections onto a k-set are k!·S(n,k), because labelling the blocks matters there. Equivalence relations do not distinguish block labels.

The rest of Equivalence Relations

Equivalence classes, partitions and quotient sets. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make counting equivalence relations exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →