Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I need a hint for computing the number of ways in which all the equivalent classes on a set of $n$ elements can be realized. For example, if the set has 2 elements ${a,b}$, then there are 2 possible partitions: either a and b are related or not.

share|cite|improve this question
Do you mean the number of equivalence relations? (The maximum number of equivalent classes is $n$, which appears if you take equality as your equivalence relation.) – azimut Mar 6 '13 at 17:17
You are right. I mean if you have 3 equivalent classes, in how many ways can they be realized. I edited the question. – saadtaame Mar 6 '13 at 17:21
up vote 7 down vote accepted

An equivalence relation uniquely corresponds to a partition of the base set. For a fixed size $n$ of the base set, the number of such partitions is known as the Bell number $B_n$, see Wikipedia and the Online encyclopedia of integer sequences.

The first Bell numbers are $$1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, \ldots$$ The numbers are growing rapidly. Also, note that no simple closed formula for $B_n$ is known.

share|cite|improve this answer
I edited the question. I got it wrong at first. Thank you. – saadtaame Mar 6 '13 at 17:23
@saadtaame: ok. So I guess my post exactly answers your question. I'll edit to give some more details. – azimut Mar 6 '13 at 17:25
Isn't no. of partitions of a 2-element set = 3? {{a}}, {{b}}, {{a, b}}. How does the Bell number show 2 instead? – Masked Man Dec 25 '13 at 10:22
@Happy: Neither $\{\{a\}\}$ nor $\{\{b\}\}$ is a partition of $\{a,b\}$. The two partitions of $\{a,b\}$ are given by $\{\{a\},\{b\}\}$ and $\{\{a,b\}\}$. – azimut Dec 25 '13 at 13:23
Oh, right, I get it now. Thanks for that clarification. – Masked Man Dec 25 '13 at 15:21

The number of ways of splitting a set of $n$ elements into $k$ classes is counted by the Stirling numbers of the second kind, the total number of equivalence relations is the $n$-th Bell number.

share|cite|improve this answer

Every equivalence relation in a set induce a partition of that set into non-empty blocs and vice versa every set partition defines a equivalence relation on that set. Number of set partitions i.e number of equivalence relations on a n-set is called Bell number $B_n$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.