# how many was can a set of size n be partitioned into 2 distinct subsets where the ordering does not matter?

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.

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