Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer 1

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?

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.