How many different partitions with exactly n parts can be made of a set with k-elements?

Jared picture Jared · Feb 16, 2012 · Viewed 12.7k times · Source

How many different partitions with exactly two parts can be made of the set {1,2,3,4}? There are 4 elements in this list that need to be partitioned into 2 parts. I wrote these out and got a total of 7 different possibilities:

  1. {{1},{2,3,4}}
  2. {{2},{1,3,4}}
  3. {{3},{1,2,4}}
  4. {{4},{1,2,3}}
  5. {{1,2},{3,4}}
  6. {{1,3},{2,4}}
  7. {{1,4},{2,3}}

Now I must answer the same question for the set {1,2,3,...,100}. There are 100 elements in this list that need to be partitioned into 2 parts. I know the largest size a part of the partition can be is 50 (that's 100/2) and the smallest is 1 (so one part has 1 number and the other part has 99). How can I determine how many different possibilities there are for partitions of two parts without writing out extraneous lists of every possible combination? Can the answer be simplified into a factorial (such as 12!)?
Is there a general formula one can use to find how many different partitions with exactly n parts can be made of a set with k-elements?

Answer

penartur picture penartur · Feb 16, 2012

1) stackoverflow is about programming. Your question belongs to https://math.stackexchange.com/ realm.

2) There are 2n subsets of a set of n elements (because each of n elements may either be or be not contained in the specific subset). This gives us 2n-1 different partitions of a n-element set into the two subsets. One of these partitions is the trivial one (with the one part being an empty subset and other part being the entire original set), and from your example it seems you don't want to count the trivial partition. So the answer is 2n-1-1 (which gives 23-1=7 for n=4).