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 ?
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