How many subsets $I$ of $S:=\{1,\cdots,n\}$ exist such that


$\sum\_{i \in I} x\_i \neq \sum\_{j \in S-I} x\_j$


for all $0 < x\_1 < \cdots < x\_n$?


Let $b\_n$ be this number. Then we are interested in the number $a\_n := 2^n - b\_n$.


Is there any reference which considers this situation, where maybe I can read things up in this situation?


Any help is appreciated.


For $n = 3$ consider:


0 () ['x2', 'x3', 'x1']


1 ('x1',) ['x2', 'x3']


2 ('x2',) ['x3', 'x1']


3 ('x3',) ['x2', 'x1']


4 ('x1', 'x2') ['x3']


5 ('x1', 'x3') ['x2']


6 ('x2', 'x3') ['x1']


7 ('x1', 'x2', 'x3') []


Then only 3 and 4 are valid, (for instance 5 is not valid since $x\_1+x\_3>x\_2$) so we get $a\_3$ = 2.



How many subsets I of $\{1,\cdots,n\}$ exist?
I claim that $b\_n=2\binom{n}{[n/2]}$ for $n\geqslant 1$. If $\sum\_{i\in I} x\_i\ne \sum\_{i\notin I} x\_i$, then either the sign is always '$>$' or always '$<$' (since the set of strictly increasing sequences is convex and therefore connected.) So, we need to prove that there are exactly $\binom{n}{[n/2]}$ subsets $I$ for which $\sum\_{i\in I} x\_i>\sum\_{i\notin I} x\_i$ whenever $0<x\_1<\dots<x\_n$. For any set $I$ construct a lattice path as follows: it start from the origin, and on $i$-th step goes from $(a,b)$ to $(a+1,b)$ if $n+1-i\in I$ and goes to $(a,b+1)$ otherwise. Note that condition $\sum\_{i\in I} x\_i>\sum\_{i\notin I} x\_i$ holds if and only if our path lies in the region $\{(a,b):a\geqslant b\}$, i.e., if it does not intersect the line $\ell:\{b=a+1\}$. In other words, out of $k$ greatest values of an index $i$ at least half should belong to $I$. For calculating the number $N$ of such paths do the standard trick. $N$ equals the number of all paths of length $n$ to the possible endpoints $(n,0),(n-1,1),\dots,(\lceil n/2\rceil,\lfloor n/2\rfloor)$ minus the number of paths from the origin to these endpoints, which intersect $\ell$. For any considered endpoint $P(a,b)$, the number of paths from the origin to $(a,b)$ which intersect $\ell$ equals the number of paths from the origin to the point $P^\*$ symmetric to $P$ in $\ell$ (bijection is the symmetrizing the part of the path after the last point of $\ell$ on it). So, we sum up the number of paths to $(k,n-k)$ with $n\geqslant k\geqslant n/2$ and subtract the number of paths to points $(n-k-1,k+1)$, $n\geqslant k\geqslant n/2$. Since the number of paths to $(n-k-1,k+1)$ equals the number of paths to $(k+1,n-k-1)$, we see that everything except paths to $(\lceil n/2\rceil,\lfloor n/2\rfloor)$ cancel, that proves our claim.


