Number of equivalence relations

Question

How many different equivalence relations can be defined on a set of five elements?

Answer 1

Hint: In how many ways can you partition a five element set?

Answer 2

We have $5$ people, and want to find the number of ways to break them up into groups (equivalence classes). With a number significantly bigger than $5$, it would be useful to develop some theory (and there is such theory). With $5$, we just count in a systematic way.

(i) One big happy family, everybody equivalent to everybody else. Clearly there is $1$ way to do this.

(ii) One loner, and four friends. The loner can be chosen in $\binom{5}{1}$ ways, giving $5$ ways.

(iii) A group of three friends, and a group of two friends. The group of three can be chosen in $\binom{5}{3}$ ways, and then the other group is determined.

(iv) Three, one, one. You can handle this.

(v) Two, two, one. This one is tricky, it is easy to get the wrong count. The loner can be chosen in $5$ ways. For each of these ways, the remaining four can be broken up into two teams of two in $3$ ways, for a total of $15$. To see this, suppose the four people are A, B, C, D. Then A can be teamed with any of the $3$ others.

(vi) Two, one, one, one. You can handle this.

(vii) Everybody by herself. Easy.

Add up.