Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
"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
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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