1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ thank you for your help. can you explain to me why the solution wouldn't look like the solution posted here: math.stackexchange.com/questions/556807/… is it because the first term is not n? $\endgroup$ – Trixie the Cat Apr 17 '19 at 21:05
  • $\begingroup$ @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. $\endgroup$ – hmakholm left over Monica Apr 17 '19 at 21:08
  • $\begingroup$ @Robert Israel, thank you for taking the time to help a struggling student! $\endgroup$ – Trixie the Cat Apr 17 '19 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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