This problem maps directly to the Parentheses problem:

How many different ways is it possible to arrange n pairs of parentheses such that:

• There are an equal number of open and closed parentheses in the string.
• Counting from the left, the number of closed parentheses do not exceed the number of open parentheses at any point.

Each "+" maps to "(", and each "-" maps to ")".

The answer to the parentheses problem is $C_n = \dfrac{1}{n + 1} \dbinom{2n}{n}$ . See Catalan numbers .

We have 20 pairs of pluses and minuses, so $C_{20} = \dfrac{1}{21} \dbinom{40}{20} = 6564120420$ .

The first three digits are hence $\boxed{656}$ .

We can use dynamic programming to solve the problem.

Let $dp(p,m)$ be the number of sequences such that the resulting sequence of integers as described in the question contains no negative numbers. Since the right-most sign must be a '+' or '-', we have $dp(p,m)=dp(p-1,m)+dp(p,m-1)$ in general.

To find the base cases, we observe that the last integer in the sequence of integers is equal to the number of '+' signs minus the number of '-' signs and since this integer cannot be negative, we must have $p \ge m$ so when $p<m$ , $dp(p,m)=0$ . Furthermore, when $m=0$ , there is only 1 possible sequence which is a sequence of '+' signs so $dp(p,0)=1$ where $p$ is non-negative.

For a sequence to be good, the last integer in the sequence formed must be $0$ so the number of '+' signs equals the number of '-' signs. Hence the number of good sequences of length $40$ is $dp(20,20)=6564120420$

We could solve this problem by using Dynamic Programming Approach

Let $f(len,score)$ be the number of different sequences with length $len$ with $score$ as the last element.

thus by using the recurrence function $f(len,score) = \left\{ \begin{array}{l l} 0 & \quad \text{if \$score\$ < 0}\\ 1 & \quad \text{if \$len\$ = 1 and \$score\$ = 0}\\ f(len-1,score-1) + f(len-1,score+1) & \quad \text{} \end{array} \right.$

from the function above, we could get the answer from $f(40,0)$ , thus we get $6564120420$ . hence the first 3 digit is $\boxed{656}$

we could implement the reccurence function by the Top-Down Memoization Approach, here my C/C++ code

for a good sequence of length 2 n number of '+'s = '-'s= n

number of ways to distribute them C(2 n , n )

from combinatorics we know that for the '+'s to outnumber '-'s at every point only one possibility remains out of n , and because any good sequence starts with '+' and ends with '-' (to avoid negatives that would appear otherwise) it turns out that N(n) = C(2 n , n )/( n +1) (fraction formating \frac{a}{b} not working)

substituting n =20 we get N(20)= 6564120420 = 656

Call a sequence with no negative numbers, a meh sequence.A meh sequence ending in 0 is a good one. Let's count the sequences recursively.

We introduce a function $f(n,k)$ , which counts the number of meh sequences ending in $k$ of length $n$ , where the initial $0$ is not counted in our length, so it coincides with the length of the sign sequence. The problem asks for $f(40,0)$ . Also, let $a_i$ be a number in our number sequence, with $a_0=0$ .

Notice that $a_n = k$ , and because we can only add or subtract $1$ to adjacent members of the sequence, we can only have $a_{n-1} = k-1,k+1$ .

Therefore for every meh sequence of length $n-1$ ending with $k-1$ we can add a $+$ sign in the sign sequence to form a new meh sequence of length $n$ ending with $k$ . Similarly, we can add a $-$ sign with the sequences of length $n-1$ ending with $k+1$ . We counted all the meh sequences of length $n$ because these are the only two cases and they don't overlap.

Obviously, since we can't admit negatives, for the special case $k=0$ , we can only have $a_{n-1} = 1$ .

Also notice that we must start with a $+$ sign otherwise $a_1$ would be negative.

Therefore we have the following recursion $f(1,1)=1$ $f(1,k)=0 \text{ if } k \ne 1$ $f(n,0) = f(n-1,1)$ $f(n,k) = f(n-1,k-1)+f(n-1,k+1) \text{ if } k \ge 1$

We can then just use dynamic programming to compute the answer.

My code in Python 3, I use lru_cache for lazy dynamic programming, but you can just use a regular list or dictionary if you want.

from functools import lru_cache
@lru_cache(maxsize=None)
def f(n,k):
    if (n,k) == (1,1):
        return 1
    if n == 1:
        return 0
    if k==0:
        return f(n-1,1)    

    return f(n-1,k-1)+f(n-1,k+1)    

print(f(40,0))

Once Again,Recursion with Memoization.

F(N,M) is the number of ways of making a good sequence that sums to N using M moves for N>=0.We use N=0 for our case. Code uses the fact that F(N,M)=F(N-1,M-1)+F(N+1,M-1)

Store = {}
def F( N , M ):
    if (N%2)!= (M%2):return 0  #N and M must either both be odd or both be even;
    if ( N , M ) in Store:#If it has already computed,avoid recomputation and obtain from dictionary
        return Store[ ( N , M ) ]
    if N < 0:return 0 #Define a base case
    if M == 0:
        if N == 0:return 1 # Also a base case F(0,0) has to be 1
        return 0
   a = F( N - 1 , M - 1)  # recursive part
   b = F( N + 1 , M - 1) #recursive part
   Store[ ( N , M ) ] = a + b
   return a + b

print str( F( 0 , 40 ) )[0:3]

Via a combinatorial reduction, we can look at this problem as the problem of matching $+$ and $-$ , which is equivalent to the problem of counting binary trees: $+(+-)(+-)- \cong \def\arraystretch{0.2}\begin{array}{ccccc}&&\circ\\& \swarrow&& \searrow\\ \circ &&&& \circ\end{array}$ This language is succinctly described by the regular pattern $\mathcal{T} := \varnothing \mid + \mathcal{T}_1 \mathcal{T} _2 -$ transferring into the reals, this translates into the function $T(z) = 1 + zT(z)^2 \implies T(z) = \frac{1 - \sqrt{1 - 4z}}{2z}$ (we need the minus because otherwise $T$ isn't analytic around $z = 0$ , so we can't use Taylor's theorem) We can extract out the coefficients via the generalized binomial theorem $\begin{aligned}\frac{1 - \sqrt{1 - 4z}}{2z} &= \frac{1}{2} \frac{1 + \sum_k {1/2 \choose k}(-4z)^k}{z} \\ &= \frac{1}{2} \sum_k {1/2 \choose k+1} (-4)^{k+1} z^k \\ &= \sum_k \frac{1}{k+1} {2k\choose k} z^k\end{aligned}$ Therefore, for a class of strings of size $2k$ , we would expect there to be $\frac{1}{k+1}{2k\choose k}$ good sequences. Therefore, the answer is $\frac{1}{21}{40\choose 20} = \boxed{6564120420}$

I have no Idea for programm, but I Know it's "Catalan Number Problem for $n=20$ "

So, the answer are:

$\frac{C(40,20)}{21}=6564120420$

The first three digit $\fbox{656}$

include < stdio.h >

include < conio.h >

long int numstr( long int a, long int b )

{

if (a==1) return b;

if (a==b) return numstr(a-1,b) ;

return ( numstr(a-1,b) + numstr(a, b-1) );

}

int main()

{

long int n;

clrscr();

n=numstr(20,20);

printf("number of string = %ld",n);

getchar();

return 0;

}

We use dynamic programming. We define dp[i][j] as the number of non-negative sequences of length i that sum to j. One can then find the transition: dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]. As our base case, dp[0][0] = 1, and dp[0][x] = 0 if x > 0. Additionally, dp[i][k] = 0 if k < 0. My code can be found here: http://ideone.com/trc1tN

I actually see that the number of good sequences of length $2n$ is the $(n+1)$ th Catalan number. Not a computer science solution. Answer is $6564120420$ .

Not much computer science actually used. The answer is the $40/2=20\mathrm{th}$ Catalan number $C_{20}$ . The Catalan numbers are given by $C_n=\frac{1}{n+1}{{2n}\choose{n}} = \frac{2n!}{(n+1)!n!}$ . This can be calculated with your language of choice in many different ways, but the answer will be $6564120420$ , so the first three digits are $\boxed{656}$ .

If you don't know of the Catalan numbers, look them up! They satisfy a whole slew of recurrence relations and combinatorics problems.