This question is based on a dynamic programming problem on TopCoder that I have been trying to understand forever.
The main concept that I can't understand or even begin to formulate is the following-:
Problem Statement:
Given a tuple of $n$ items $A = \{a_1,a_2,...,a_n\}$, where each item is of equal value, i.e. $a_1 = a_2, a_2 = a_3, ...$ and so on.
How many ways are there for two people to pick items from the tuple $A$, such that they always have equal cumulative value on both sides?
Example:
$A = \{5,5,5,5\}$
Solution (not exhaustive)-:
$\{5\},\{5\}$ (first 5 and second 5)
$\{5\},\{5\}$ (first 5 and third 5)
$\{5\},\{5\}$ (first 5 and fourth 5)
$\{5,5\}$ and $\{5,5\}$ (first 5 second 5 and third 5 and fourth 5)
$\{5,5\}$ and $\{5,5\}$ (first 5 third 5 and second 5 and fourth 5)
so on
This is equivalent to having a set of $n$ items and choosing an ordered pair of two disjoint subsets of equal size. For a fixed size $k\le \frac{n}{2} $ the number of ways to choose two disjoint subsets is $$ \binom{n}{k} \binom{n-k}{k}. $$ Summing over all possible $k$ yields. $$ \sum_{k=1}^{\lfloor n/2\rfloor} \binom{n}{k} \binom{n-k}{k}. $$ More on these numbers might be found in the Online Encyclopedia of Integer Sequences (A180282).
If you include the choice of both sets being empty, you have $$ \sum_{k=0}^{\lfloor n/2\rfloor} \binom{n}{k} \binom{n-k}{k}, $$ which is A002426 in the OEIS.