Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

If a set has $n$ elements then what are maximum number of equivalence classes and equivalence relations possible on it?

share|cite|improve this question

The maximum number of equivalence classes is $n$ -the identity relation $\{ (x,x) \ | \ x \in X \}$ is an equivalence relation. The number of equivalence relations is the Bell number. The series is in A000110 of OEIS.

share|cite|improve this answer
the empty relation is not an equivalence relation (except on the empty set!). I think you meant to say "identity relation". Anyway, I'm sure we are both talking about the relation whose ordered pairs are $(x,x)$ for all $x \in X$. – Pete L. Clark Feb 10 '11 at 16:53
@Pete: fixed. Thanks. Also added the OEIS reference – Ross Millikan Feb 10 '11 at 16:56
it looks like there was some kind of strange edit conflict which caused part of your edit to be undone. Since we agree on the content, I went ahead and fixed it. – Pete L. Clark Feb 10 '11 at 17:21
@Pete: Thanks much. – Ross Millikan Feb 10 '11 at 17:22

The Stirling numbers of the second kind $S(n,k)$ are by definition the number of ways you can partition some set of $n$ elements into $k$ non-empty and disjoint subsets. But since an equivalence relation may partition your set into any amount of subsets, you need to sum over all possibilities:

$$\sum_{k=1}^n S(n,k)$$

gives you the anwser.

You can read about them here.

share|cite|improve this answer

Your Answer


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