Take the 2-minute tour ×
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.

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|improve this question
2  
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. –  staame Mar 6 '13 at 17:21
add comment

3 Answers

up vote 3 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.

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|improve this answer
    
I edited the question. I got it wrong at first. Thank you. –  staame Mar 6 '13 at 17:23
1  
@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? –  Happy Dec 25 '13 at 10:22
1  
@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. –  Happy Dec 25 '13 at 15:21
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.