I am struggling with a combinatorics problem, which I understand but can't formulate a solution for.

Problem statement:

You are given a set of $n$ elements all of which have equal value. For example : $A = \{5,5,5,5,5\}$ where $n=5$.

You have to count the number of ways to select subsets from the original set such that the subsets can be partitioned with the difference of 0. ie. the sum of the left hand side should equal sum of the right hand side. For example: $\{5,5\}$ or $\{5,5,5,5\}$ these two can both be sub divided into sets that have equal partitions ($\{5,5\}, \{5,5\}$).

But the catch is that I have to calculate all the ways of obtaining the sum : example a valid set is $\{a_1, a_2\}$ ($a_1$ and $a_2$ are just indexes of the original set) which might look like $\{5,5\}$, but there are also many other valid sets that look the same ie. I include $\{a_2,a_3\}$ or $\{a_1,a_3\}$ they all look the same ie. $\{5,5\}$. So how do I count that ?

What I have tried:

I know the subsets that will be in the solution will only contain even number of elements, and I know that any one side of a solution subset cannot be $\ge n/2$.

So for every even number from 2 to $n/2$ you calculate the number of ways that much of elements can be selected. For example: for the subset of 4 elements we select the number of ways 2 elements can be selected = $5\choose 2$ * 2 (multiplied by 2 for the second half)

I don't know if the above is correct but it is infeasible to do when $n$ is large : is there a one -line expression for this. This my reasoning correct ?

  • $\begingroup$ It would be much easier to follow what you are doing if you make $A=\{1,2,3,\ldots,n\}$ and ask about subsets that have the same number of members. Then instead of $a_1$ we can talk about $1$. Now if your original subset is $\{1,2,3,4\}$ you want to divide that into two sets with two elements each. Do we just count $\{1,2,3,4\}$ because it can be split, or do we count the three ways to divide it, or do we count the six ordered ways to divide it, so $\{1,2\},\{3,4\}$ is different from $\{3,4\},\{1,2\}$ $\endgroup$ – Ross Millikan Apr 1 '18 at 19:24

As you say you need each subset to have an even number of elements, so $n$ must be divisible by $4$. Assuming $4$ divides $n$ you are just looking for half the number of even size subsets of $n$ items. The half comes because splitting $\{a_1,a_2\}$ and $\{a_3,a_4\}$ is the same as splitting $\{a_3,a_4\}$ and $\{a_1,a_2\}$. You might also want to subtract $1$ if you don't all the split of the empty set and the whole set. Can the empty set be partitioned this way? I think so, but some would disagree. In that case you are looking for $$\frac 12\sum_{i=0}^{n/2}{n \choose 2i}=2^{n-2}$$ because half the $2^n$ subsets of a set with $n$ members have an even number of members

  • $\begingroup$ N does not need to be divisible by 4. My example shows 5 elements. Also why do you have 2i in your answer? What does that mean? And how does the summation expression equal a power of 2. Could you elaborate? $\endgroup$ – ng.newbie Apr 1 '18 at 18:23
  • $\begingroup$ I thought you were partitioning the original set into two, each of which had to be able to be split, which is where the multiple of $4$ comes from. If you just want to extract one subset that can be split, you just need to extract a subset that has an even number of elements. That is half the total of $2^n$ subsets, so $2^{n-1}$ $\endgroup$ – Ross Millikan Apr 1 '18 at 19:19
  • $\begingroup$ The $2i$ is the number of elements in a subset, which is required to be even. $\endgroup$ – Ross Millikan Apr 1 '18 at 19:21

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.