How many different ways can the signs be chosen so that $\pm 1\pm 2\pm 3 ... \pm (n-1) \pm n = n+1$?
This is an extension of this question: For what $n$ can $\pm 1\pm 2\pm 3 ... \pm (n-1) \pm n = n+1$?
There I asked "for what values of $n$ can the signs be chosen in the equation $$\pm 1\pm 2\pm 3 ... \pm (n-1) \pm n = n+1$$ so the equation is true?"
The answer was that no solutions exist for $n=4k$ and $n=4k+1$; solutions exist and were exhibited for $n=4k+2$ and $n=4k+3$.
My challenge now is to count the number of solutions.
I do not have a complete answer, but, in the work below, I show that there are at least an exponential number of solutions - at least $O(2^{n/4})$.
What has been done so far:
There are two types of solutions stated.
In the first, the fact that $n+(n+3)=(n+1)+(n+2)$ was used to construct solutions with the sign pattern "+ - - +" (or "- + + -").
In the second, the fact that $1+3+5+...+(2m-1) = m^2$ was used to construct solutions with the sign pattern "- + - +" (or "+ - + -") with minor modifications.
Generating an exponential number of solutions.
Once a single solution has been generated, another can be generated by taking any four equally spaced elements with corresponding signs "+ - - +" or "- + + -" and reversing their signs. To show this, the elements values are $\pm m, \mp (m+d), \mp (m+2d),\pm (m+3d)$. Since the sum of these is $0$, so is the sum of the sign-reversed values $\mp m, \pm (m+d), \pm (m+2d),\mp (m+3d)$.
If we use the "- + + -" solution mentioned above, there are about $n/4$ blocks of four elements with a "- + + -" or "+ - - +" sign pattern. By changing the signs of each of these blocks independently, we get about $2^{n/4}$ different arrangements, all summing as desired.
We can get more patterns by starting at $2, 3, $ or $4$, or by using the "- + - +" pattern.
See A058377 in the Encyclopedia of Integer Sequences http://oeis.org/A058377
EDIT: Let $S_n = \sum_{j=1}^n j X_j$ where $X_1, \ldots, X_n$ are independent random variables with $P(X_j = 1) = P(X_j = -1) = 1/2$. You're interested in $a_n = 2^n P(S_n = n+1)$. Now $S_n$ has mean $0$ and variance $\sigma_n^2 = \sum_{j=1}^n j^2 = n^3/3 + O(n^2)$. The Central Limit Theorem will apply (in one of the versions that doesn't require the summands to be identically distributed), so that $S_n/\sigma_n \to {\cal N}(0,1)$ in distribution. Now I would guess (though I'm not completely sure) that a "local" limit theorem will also apply, so that when $j/\sigma_n \to x$ with the right parity (i.e. $j$ odd if $n \equiv 1$ or $2 \mod 4$, or even if $n \equiv 0$ or $3 \mod 4$), $P(S_n = j) \approx \frac{2}{\sqrt{2\pi} \sigma_n} e^{-x^2/2}$. If so, since $(n+1)^2/(2 \sigma_n^2) \to 0$,
$$ a_n \approx 2^n \frac{2}{\sqrt{2\pi} \sigma_n} \approx 2^n \sqrt{\frac{6}{\pi n^3}}\ \text{for } n \equiv 2, 3 \mod 4$$
Numerically, this seems to work pretty well. For example, for $n = 102$ we have $a_n = 6626103472269834127654807314$ while the approximation is $6.802365900 \times 10^{27}$