# What is the size of partitions versus subsets?

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.

-
"Partition" can refer to two things: a partition of a natural number and a partition of a set. For the former see en.wikipedia.org/wiki/Partition_(number_theory) and for the latter see en.wikipedia.org/wiki/Partition_of_a_set and en.wikipedia.org/wiki/Bell_numbers . –  Qiaochu Yuan May 9 '12 at 20:04

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