# tHow many ways we can partition a set S into two subsets under the following restrictions?

How many ways we can partition a set S into two subsets such that:

The set $S$ can have $n$ elements in the range $1$ to $1000$ (inclusive). Let the two subsets be $A$ and $B$. For all $x$ in range $1$ to $1000$ we count the number of elements in each subset which are equal to $x$. Let the set $A$ has $a$ elements equal to $x$, and and the set $B$ has $b$ elements of equal to $x$. We compute the sum of all such $a$'s and $b$'s. Now how to determine how many subsets the sum of all $a$'s is more than the sum of all such $b$'s (without actually iterating through all subsets)

Example:

Let $S = \{1, 1, 3, 2\}$ in this cases the answer is $5$. And the subset choice of $A$ are: $\{1,1,3\},\{1,1,2\},\{1,3,2\},\{1,3,2\},\{1,1,3,2\}$

Please note: Either partition can be empty for this problem.

• Don't those sums just give you the number of elements of $A$ and of $B$? So aren't you just getting all the partitions where $A$ has more elements than $B$? – Gerry Myerson Feb 7 '13 at 11:30
• Normally a set cannot have two elements equal, so $\{1,1,3,2\}$ would not be a set. A multiset can have equal elements. If $S$ has to be a set, Gerry Myerson is right that the sums are just the number of elements in $A$ and $B$. Are you trying to compute the number of pairs $A,B$ where the size of $A$ is greater than the size of $B$? Do $A$ and $B$ have to exhaust $S$? – Ross Millikan Feb 7 '13 at 15:45
• @RossMillikan I'd say that $\{1,1,3,2\}$ is a set, it's just equal to $\{1,3,2\}$ (as well as to $\{1,2,3\}$, etc.) In the usual development of axiomatic set theory it's important that the pairing operation can be used to get singletons $\{x,x\}$. – Trevor Wilson Feb 7 '13 at 20:13

What you tak about are actually not sets, but rather something like this: For each number $k$, you specify a maximal number $s(k)\in\mathbb N_0$ of occurences. There are only finitely many $k$ with $s(k)\ne 0$. We want to find all possible choices for functions $a$ such that $0\le a(k)\le s(k)$ for all $k$ and $\sum_k a(k)>\frac12\sum_k s(k)$.
If we drop the condition $\sum_k a(k)>\frac12\sum_k s(k)$ for a moment, there are $\prod_k(s(k)+1)$ possible functions $a$. Let $\sigma = \sum_k s(k)$. For every $a$ with $\sum_k a(k)<\frac12 \sigma$, its complement has sum $>\frac12\sigma$. Therefore, if $\sigma$ is odd, then the desired number is simply $$\tag1 \frac12\prod_k(s(k)+1).$$ However, if $\sigma$ is even, we need to explicitly count the number of functions $a$ such that $\sum_k a(k)=\frac12 \sigma$ and then subtract half this number from $(1)$. The counting in this case, I guess, is best done using the techniques of dynamic programming ...