What is the size of partitions versus subsets?

Question

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

etc??

I appreciate any tips or help.

Answer 1

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.