If a set has $n$ elements then what are maximum number of equivalence classes and equivalence relations possible on it?
Number of equivalence relations on a set
1
$\begingroup$
combinatorics
algebra-precalculus
elementary-set-theory
discrete-mathematics
2 Answers
7
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.
-
0it looks like there was some kind of strange edit conflict which caused $p$art of your edit to be undone. Since we agree on the content, I went ahead and fixed it. – 2011-02-10
3
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.