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)


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.

  • $\begingroup$ 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$? $\endgroup$ – Gerry Myerson Feb 7 '13 at 11:30
  • $\begingroup$ 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$? $\endgroup$ – Ross Millikan Feb 7 '13 at 15:45
  • $\begingroup$ @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\}$. $\endgroup$ – 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 ...

  • $\begingroup$ Excellent answer. +1 $\endgroup$ – mrs Feb 7 '13 at 17:46

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.