how many partitions and equivalence relations of A = {a,b,c} exists for example or A {a,b,c,d,e}?

Question

I have these two questions. Is there a formel or anything like that to find how many partitions and equivalence relations there is for A? I know the answer but i don´t know how to calculate it by my self. I would appreciate if anyone could explain how it works.

Answer 1

You have this recurrence relation

To prove it, for a set of $n+1$ elements, single out one element $a$. Then there are $\binom{n}{n-k}=\binom{n}{k}$ ways to choose $n-k$ other elements among the other $n$ elements to be in the class of $a$, when that class ought to have $n-k$ elements. For each of those there are $B_k$ ways to partition the remaining $k$ elements. Summing for all the cases for the size $n-k=0,1,...,n$ of the class of $a$, you get the value of $B_{n+1}$.