1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.