I know this might be a newbie question, but it's confusing to me.

What is a partition, does it only apply to integers? And how does the size of it compare to the size of subsets?

Also, suppose we have a set {A,B,C,D} and a set {A,B,C,D,E}? How does the number of partitions in each compare? i.e, how does the size of partitions grow as it's members increases?'

For the set {A,B,C,D} I think the partitions are:

{ABCD} , {ABC, D}, {AB, CD}, 


I appreciate any tips or help.


In combinatorics, the $n$th Bell number, named after Eric Temple Bell, is the number of partitions of a set with $n$ members, or equivalently, the number of equivalence relations on it.

Wikipedia has info on the definition of this function, which can be defined recursively as

$$ B_{n+1}=\sum_{k=0}^{n}{{n \choose k}B_k} $$

with $B_1 = 1$. It turns out that this number grows very fast; see OEIS A000110 for the first few Bell numbers. Specifically, there are 15 and 52 partitions of a 4- and 5-element set, respectively.

Also, interestingly, there is a correspondence between integer partitions and set partitions and also between vector partitions and multiset partitions. You can use this fact to list all set partitions for a set of size $m$ by generating the integer partition of $m$ and having a correspondence between the numbers $1\cdots{}m$ and the members of your set. The multiset case is roughly the same but using the vector partition concept instead, where the vector in question is a vector of multiplicity counts (one for each element in the multiset). Knuth is a good reference on this.


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.