# A basic combinatorics problem: number of solutions of form $\pm 1$ to and additive equationn

In my combinatorics and discrete mathematics class I was asked this question which I cannot seem to be able to solve:

Let us define N variables $\{ s_k \}_{k=1}^{N}$ each having two possible values $\pm 1$ and we are asked to determine the number of possible N distinct solutions to the following equation:

$\sum_{k=1}^{N} s_k = m$ for an integer m (positive, negative or zero unknown value).

I have not studied this explicitly, how would one find the number of distinct $\pm 1$ solutions to an integer equation? I certainly appreciate all kind helpers.

## 1 Answer

HINT: The key is to realize that $\sum_{k=1}^Ns_k$ depends entirely on the number of variables that are $1$. Say that $\ell$ of them are $1$; then

$$\sum_{k=1}^Ns_k=\ell-(N-\ell)=2\ell-N\;.$$

You can easily determine what $\ell$ must be (in terms of $m$) in order for the sum to be $m$. Now ask yourself: in how many different ways can you get exactly that many of the $N$ variables to be $1$ and the rest to be $-1$?

• Thanks Brian. Is this different number the number of distinct subsets to choose $\ell$ out of N ? – Don John Prep Apr 15 '16 at 18:23
• @Abeer: No, it's not different: that's exactly the number that you want. – Brian M. Scott Apr 15 '16 at 18:24
• @Abeer: You're welcome. – Brian M. Scott Apr 15 '16 at 18:27