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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
Not set theory. I removed the tag. – Andrés E. Caicedo Jun 18 '11 at 15:29
Theses numbers are called Bell numbers Some proof of the fact you mention should be here – 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?

share|cite|improve this answer

Your Answer


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.