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?