Equivalence Relations · step 12 of 13

Bell numbers & counting partitions

Bₙ counts the partitions of an n-element set: 1, 1, 2, 5, 15, 52, 203, 877 for n = 0 through 7. The standard recurrence Bₙ₊₁ = Σₖ C(n,k)Bₖ comes from choosing which k elements accompany a fixed element in its block, and the Bell triangle computes the whole sequence with nothing but additions.

Practise bell numbers & counting partitions 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.

Use the binomial recurrenceBₙ₊₁ = Σ_{k=0}^{n} C(n,k)·Bₖ. Fix element n+1, choose its blockmates from the remaining n, and partition the rest.
Or build the Bell triangleStart a row with the last entry of the previous row; each subsequent entry is the one to its left plus the one above-left. The first entry of each row is a Bell number.
Break down by pattern for small nEnumerate block-size patterns and count each with binomials, dividing by k! for interchangeable equal-sized blocks.
Cross-check with Stirling numbersBₙ = Σₖ S(n,k), so the row of Stirling numbers must sum to your Bell number.

Worked example

Compute B₅ from B₀ … B₄ = 1, 1, 2, 5, 15.

B₅ = Σ_{k=0}^{4} C(4,k)·Bₖ.
= C(4,0)·1 + C(4,1)·1 + C(4,2)·2 + C(4,3)·5 + C(4,4)·15.
= 1 + 4 + 12 + 20 + 15.
Cross-check with Stirling: S(5,k) for k = 1…5 is 1, 15, 25, 10, 1, summing to 52 ✓.

Answer. B₅ = 52 — there are 52 partitions of a 5-element set, hence 52 equivalence relations on it.

Where marks get dropped

These are the specific errors that cost credit on bell numbers & counting partitions questions — QED's rubric penalises each of them separately.

Using C(n,k) with the wrong n in the recurrence. The binomial is over the n other elements, not n + 1.
Forgetting B₀ = 1. The empty set has exactly one partition — the empty collection.
Confusing set partitions with integer partitions. Integer partitions of 5 number 7; set partitions number 52.

Practise this until it is automatic

Unlimited fresh questions

QED generates new bell numbers & counting partitions 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.

Bell numbers & counting partitions — frequently asked questions

Is there a closed formula for Bₙ?

Dobiński’s formula gives Bₙ as an infinite series involving e, but nothing elementary. In practice the recurrence or the Bell triangle is how they are computed.

How fast do Bell numbers grow?

Faster than exponentially but slower than n!. B₁₀ is 115975 while 10! is 3628800, and the gap widens.

What is the Bell triangle?

Rows starting 1; 1 2; 2 3 5; 5 7 10 15; … Each row begins with the last entry of the previous row, and each later entry is the sum of the entry to its left and the entry above it. Row starts give the Bell numbers.

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 bell numbers & counting partitions 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 →