Thread: Equivalence Relations

Let B(n) be the n-th Bell number (the number of equivalence relations on an n-element set). Show that the Bell numbers satisfy:
B(0) = 1;
B(n+1) = Sum_{k=0 }^n C(n,k)B(k).
(Hint: count equivalence relations on {0,1,...,n} by first choosing which elements are NOT related to n.) I am not quite sure how to start. i was thinking induction, but got lost? any help would be great

Here is a pdf file that I did sometime ago.

the pdf does not show that B(0)=1, it just says "for convenient notation."

Originally Posted by Chief65

the pdf does not show that B(0)=1, it just says "for convenient notation."

Well of course not! By definition the empty set cannot be partitioned.
But for convenience of notation we use it in the sums.