2

I am studying the equal partition problem as part of my algorithms course. What I'm wondering is how many ways can a set of size n be partitioned into 2 distinct subsets where the ordering does not matter?

For example, a set S of size 4 might look like this: {1, 2, 3, 4}, then I count seven distinct ways that the set can be partitioned into two subsets. There are n ways (n = 4) that set S can be partitioned into subsets of size 1, and n-1. For example, you'd have: {1,2,3} {4}, {1,2,4} {3}, {1,3,4} {2}, and {2,3,4} {1}.

Further, there are n-1 ways that set S can be partitioned into sets of size 2 and n-2. For example, you'd have: {1,2} {3,4}, {1,3} {2,4}, and {1,4} {2,3}. This should continue on as long as x <= (n-x) since the ordering inside the subsets does not matter.

So here you'd have a sum of series: n + (n-1) + (n-2) + ... + (n-x), but again this only continues as long as x <= (n-x). If someone more mathematically inclined than myself could assist me in deriving a general sum of series for this I would be very grateful.

Andrés E. Caicedo
  • 79,201
Trixie the Cat
  • 123

1 Answers1

3

There are $2^{n-1}$ ways to partition a set of $n$ elements into two subsets. This includes the case where one of the subsets is empty: you left that out of your example with $n=4$. If you mean to count partitions into two nonempty subsets, that is $2^{n-1}-1$.

The reason is that there are $2^{n}$ subsets of your set of $n$ elements, but since a subset and its complement generate the same partition you have to divide by $2$.

Robert Israel
  • 448,999
  • thank you for your help. can you explain to me why the solution wouldn't look like the solution posted here: https://math.stackexchange.com/questions/556807/what-is-the-sum-of-n-1n-2-n-k is it because the first term is not n? – Trixie the Cat Apr 17 '19 at 21:05
  • @TrixietheCat: You're counting the number of ways for each size wrong. There are many more than 99 ways to divide a set of size 100 into subsets of size 2 and 98, for example. – hmakholm left over Monica Apr 17 '19 at 21:08
  • @Robert Israel, thank you for taking the time to help a struggling student! – Trixie the Cat Apr 17 '19 at 21:16