how to comput the number of equivalence relation in a finite set? Example: 
Let $A =\{1,2,3\}$ and $S =\{(1,1)(2,2)(3,3)(1,2)(1,3)(3,1)(1,3)(2,3)(3,2)\}$
$S$ is an equivalence relation on $A$, and it has $9$ order pairs in it. Which is the square of element in $A(3^2=9)$
Let $A=\{1,2,3,4\}$, and $S=\{(1,1)(2,2)(3,3)(1,2)(1,3)(3,1)(1,3)(2,3)(3,2)(1,4)(4,1)(2,4)(4,2)(3,4)(4,3)(4,4)\}$
$S$ is an equivalence relation on $A$, and it has $4^2=16$ order pairs in it.
By this pattern, if $A=\{1,2,3,4,5,6,7,8,9,10\}$ then there should be $10^2$ equivalence relations in $S$.
Question:
If $A$ is a set of natural numbers $\{1,2,3.....,n\}$ then how many equivalence relation $S$ have on $A$?
By the above example I know there are going to be $n^2$ equivalence relations, but I just don’t know how to prove it. I was wondering if anyone can give me a hint.
 A: The number of equivalence relations on a set of $n$ elements is the same as the number of partitions on a set of $n$ elements which is given by Bell numbers $B_n$. You can compute them recursively using the recurrence
$$
B_{n+1}=\sum_{k=0}^n \binom{n}{k}B_k;\quad B_0=B_1=1.
$$
The number of relations on a set $A$ with $n$ elements is $2^{n^2}$ as a relation is a subset of the cartesian product $A\times A$.
A: The hint:
Think about equivalence classes.
A: Your examples illustrate the largest possible equivalence relation on sets with $3$ and $4$ elements. In those equivalence relations everything is related to everything else so every ordered pair is in the relation. When $A$ has $n$ elements there are indeed $n^2$ ordered pairs: $n$ choices for the first element and, independently, $n$ for the second.
The title of your question asks for the number of equivalence relations, not the number of pairs in this particular equivalence relation. I don't think that's what you are asking, but if you are, @MichealRozenberg 's answer tells you how to start thinking about it.
A: Based on your comment, what you are really asking is the side of the Cartesian product $|A \times A|$ given the size of $|A|$.  Note that each element of $A$ can be the first element.  For each one, there are $|A|$ ordered pairs because each one can have any element as the second in the pair.  There are therefore $|A|^2$ elements in $A \times A$
A: Equivalence relations on a set correspond one to one with partitions of the set. 
The number of partitions of a set with $n$ elements is the so-called Bell number.
