# Partitions of $\{1,2,\dots , n\}$

I'm studying over my first exercises in Algebra and Applications which consist of sets, groups and symmetries but I've stumbled upon an exercise I do not grasp how to proceed with :

For every value of $n \in \mathbb N$, find all the partitions of the set : $\{1,2,\dots , n\}$

Any thorough help would be greatly appreciated !

• The problem looks really strange. Is that in the OP a complete version of the problem? – Lwins Oct 29 '17 at 17:57
• @Lwins yes, it's exactly set as it's presented. – Rebellos Oct 29 '17 at 17:58
• Find the actual partitions? Because that's a pretty long list, especially as $n$ grows. – Randall Oct 29 '17 at 17:59
• You can work out some examples by hand $(n<5)$ and with some combinatorics try to cook up a recurrence relation between the number of partitions of the sets with $n$ elements and $n+1$ elements. This is what you should get : en.wikipedia.org/wiki/Bell_number – Bass Oct 29 '17 at 18:03
• @randall yes, that's what it asks, exactly translated from Greek to English (it means the same in Greek) : Find all the partitions for the many values of $n \in \mathbb N$. – Rebellos Oct 29 '17 at 18:07

A partition of a set is a grouping of the set's elements into non-empty subsets, in such a way that every element is included in one and only one of the subsets.

The number of ways a set of $n$ elements can be partitioned into nonempty subsets is called the Bell Number, $B_n$.

For example, it's easy to see that for a set of 3 elements, $\{a, b, c\}$, $B_3 = 5$

• $\{ \{a\}, \{b\}, \{c\} \}$
• $\{ \{a, b\}, \{c\} \}$
• $\{ \{a, c\}, \{b\} \}$
• $\{ \{a\}, \{b, c\} \}$
• $\{ \{a, b, c\} \}$

To derive the Bell Number for a set of $n$ elements, first count the number of partitions in the set $\{1, 2, \dots, n+1\}$.

Taking the block containing the element $1$, denote $k$ as the number of elements other than $1$ that belong to this block. We can choose these elements in $\binom{n}{k}$ ways.

Having formed this block, we partition the remaining $n + 1 - (k + 1) = n -k$ elements in $B_{n-k}$ ways.

Summing over $k$ gives $$\sum_{k = 0}^n \binom{n}{k} B_{n-k}$$

By the symmetry of the binomial coefficients, we can denote

$$B_n = \sum_{k = 0}^n \binom{n}{k} B_{k}$$

• Hello and thanks a lot for your answer. I edited a bit to look better, hope you don't mind. I wanted to ask you one thing, can you show me thoroughly how you derived the formulae ? By the way, please take into account I do not know anything about Bell Numbers. – Rebellos Oct 29 '17 at 21:20