0
$\begingroup$

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 !

$\endgroup$
  • $\begingroup$ The problem looks really strange. Is that in the OP a complete version of the problem? $\endgroup$ – Lwins Oct 29 '17 at 17:57
  • $\begingroup$ @Lwins yes, it's exactly set as it's presented. $\endgroup$ – Rebellos Oct 29 '17 at 17:58
  • $\begingroup$ Find the actual partitions? Because that's a pretty long list, especially as $n$ grows. $\endgroup$ – Randall Oct 29 '17 at 17:59
  • $\begingroup$ 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 $\endgroup$ – Bass Oct 29 '17 at 18:03
  • $\begingroup$ @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$. $\endgroup$ – Rebellos Oct 29 '17 at 18:07
2
$\begingroup$

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}$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Rebellos Oct 29 '17 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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