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