# Proving a Recursive Relation

I’m studying for an exam, and have this problem as one of my review questions: I have $p(n)$, which represents the amount of partitions from a set $A$ that has $n$ elements.

I know that if $R$ is an equivalence relation for a set $S$, then the equivalence classes of $R$ make a partition $S$. Likewise, if I have a partition $\{A_i | i \in I\}$ from set $S$, then there is an equivalence relation $R$ that contains sets $A_i, i \in I$.

Example: $p(2)=2$, and if $A=\{a_1, a_2\}$, then the only partitions that can exist are: $\{a_1, a_2\}$, and $\{a_1\}\cup\{a_2\}$.

I need to show that $p(n)=\sum\limits_{j=0}^{n-1} C(n-1,j)p(n-j-1)$, for $n\ge1$, and $p(0)=1$.

I suppose that if I have $A=\{a_1,\dots, a_n\}$, then I can fix an element $a_i \in A$. And have set $A=B_i \cup \dots \cup B_k$, where they are mutually disjoint subsets. I can cases that depend on the number of elements $B_i$ has if $B_i =\{a_i\}$. But where can I go from there?

-
Not set theory. I removed the tag. –  Andres Caicedo Jun 18 '11 at 15:29
Theses numbers are called Bell numbers en.wikipedia.org/wiki/Bell_number Some proof of the fact you mention should be here planetmath.org/encyclopedia/BellNumber.html –  Martin Sleziak Jun 18 '11 at 15:30
Thanks for the link, I've been able to do a bit more now. –  David Jun 18 '11 at 15:34
I have nothing to contribute to the solution of this question, but wish to leave a warning about the notation being used. The notation $p(n)$ is already used in Number Theory for the number of partitions of an integer $n$, and it's not the same as the $p(n)$ here. E.g., in Number Theory, $p(3)=3$ because there are the 3 partitions $3$, $2+1$, and $1+1+1$, whereas in this problem $p(3)=5$. –  Gerry Myerson Jun 19 '11 at 0:56

Hint: focus on the group that $a_1$ is in. It can be of any size from $1$ to $n$. How many ways are there to choose the rest of the elements of its group? Then how many ways are there to split up what is left?