I stumbled upon this problem when preparing a lecture about random walks. The problem is as follows:
Suppose we have a sequence of $n$ numbers, and each of them can be $1$, $0$ or $-1$. What is the number of possible combinations (without repetitions) that add up to a given number (evidently the sum has to be between $-n$ and $n$)?
The fact that a $-1$ plus a $1$ has the same net effect as a $0$ is making the problem quite cumbersome for me. Is it possible to get an analytical solution?
On
Assume $k≥0$. Indeed, the answers for $\pm k$ are clearly the same.
If the desired sum is $k$, then you must have $a$ $1's$ and $b$ $(-1)'s$ with $a-b=k$. The least $a$ can be is $k$. To get the maximum possible value for $a$, note that $$a_{max}+b≤n\implies 2a_{max}≤n+k\implies a_{max}≤\frac {n+k}2\implies a_{max}=\Big\lfloor \frac {n+k}2\Big\rfloor$$
For a particular $a$ in the range, the answer is $\binom na\times \binom {n-a}{a-k}$ So the answer is $$\sum_{a=k}^{\big\lfloor \frac {n+k}2\big\rfloor}\binom na\times \binom {n-a}{a-k}$$
The number of sequences $(x_1, \ldots, x_n) \in \{1, 0, -1\}^n$ such that $x_1 + \ldots + x_n = k$ is equal to the coefficient of $x^k$ in $(x^1 + x^0 + x^{-1})^n = (x + 1 + 1/x)^n$. This can be written as $$\sum_{m=0}^{\lfloor(n-|k|)/2\rfloor}\frac{n!}{m!(m+|k|)!(n-|k|-2m)!}.$$ The closed form, even in the case $k = 0$, is problematic - see e.g. Theorem 8.8.1 in this book.