Find the number of functions $h:\{1,2,3,\ldots ,2n\}\to \{-1,1\}$ such that $\sum_{j=1}^{2n}h(j)>0$ .

Question

Fix $n\in \Bbb N$. Find the number of functions $h:\{1,2,3,\ldots ,2n\}\to \{-1,1\}$ such that $$\sum_{j=1}^{2n}h(j)>0$$

My try:

Let $A=\{x:h(x)=1\}$ and $B=\{x:h(x)=-1\}$

In order for $\sum_{j=1}^{2n}h(j)>0$ we should have $|A|>|B|$

where $|A|$ denotes cardinality of set $A$.

Now Cardinality of $B$ can have values from the set $\{0,1,2,3,\ldots ,n-1\}$ When we fix $B$ 's cardinality the cardinality of $A$ gets fixed too.

Thus if $B$ has cardinality $j$ then the $j$ elements can be chosen from $\{1,2,3,\ldots ,2n\}$ in $\binom{2n}{j}$ ways.

Thus the total number of functions become

$$\sum_{j=0}^{n-1}\binom{2n}{j}$$

Is my solution correct?Kindly check

Answer 1

You can also arrive at jmerry's closed form answer directly from your answer. You got: $$\sum_{j=0}^{n-1}\binom{2n}{j}$$

Now, notice that $$\sum_{j=0}^{n-1}\binom{2n}{j} = \sum_{j=0}^{n-1} \binom{2n}{2n-j} = \sum_{j=n+1}^{2n} \binom{2n}{j}.$$

Therefore, the answer can be written \begin{align*} \sum_{j=0}^{n-1}\binom{2n}{j} &= \frac12\;\left({\displaystyle\sum_{j=0}^{n-1}\binom{2n}{j} + \sum_{j=0}^{n-1}\binom{2n}{j}}\right) \\ &= \frac12\;\left({\displaystyle\sum_{j=0}^{n-1}\binom{2n}{j} + \sum_{j=n+1}^{2n} \binom{2n}{j}}\right) \\ &= \frac12\;\left({\displaystyle\left\{\sum_{j=0}^{2n}\binom{2n}{j}\right\} - \binom{2n}{n}}\right) \\ &= \frac12\;\displaystyle\left(2^{2n} - \binom{2n}{n}\right). \end{align*}

Answer 2

It's correct, but we can do better - a closed form in which we're not summing an increasing number of terms.

Exactly half of the functions with nonzero sum have positive sum, by symmetry. There are $2^{2n}$ total functions. There are $\binom{2n}{n}$ functions with sum zero, by your argument. Therefore, our answer is $$\frac12\left(2^{2n}-\binom{2n}{n}\right)$$