combinatorics - how many ways can I add/subtract 1 from 4 40 times and reach zero without dropping below I start at 4 and can add 1 or subtract 1 forty times and I need to 0 without dropping below 0.
tried to start with a Catalan number and add 4 subs but there are too many ways to get the same answers like this. I really need help
 A: It is equivalent to count reverse sequences which start at $0$ and end at $4$ which are never negative. This is exactly the ties allowed variant of Bertrand's ballot problem, so the answer is
$$
\frac{22-18+1}{22+1}\binom{40}{18}.
$$
A: For minimum effort, I would make a spreadsheet.  Leaving A blank, label columns $0$ through $44$.  Leaving row 1 blank, in column A put $0$ through $40$.  The rows are the number of $1$s added, the columns are the sums so far, and the entries are the number of ways to get that sum with that many $1$s.  In the column with $4$ and row with $0$ put $1$ because there is $1$ way to get a sum of $4$ with no $1$s.  In each cell except the $0$ column put =(up left)+(up right) because you can get there from either of those cells with the right sign on one more $1$.  In the $0$ column you just put =(up right) because you can't come from a sum of $-1$.  Copy right and down.  The top rows will be Pascal's triangle until the zero restriction comes in.  Sum the entries in the row labeled $40$ and you are done.
A: In general, consider $n$ negative steps and $m$ positive steps with $n \ge m$ and starting out at the integer $n - m$, and count the 'good' paths that don't dip into the negative integers. We want to show that the good paths, represented by $[n,m]$, is given by
$$\tag 1 [n,m] = \frac{n-m+1}{n+1} \binom{n+m}{n}$$
It turns out that the base case are precisely the Catalan numbers, since the formula when $n = m$ is the number $C_n$ (see this Catalan theory link).
We are going to prove $\text{(1)}$ using the method of infinite descent.
Assume that $\text{(1)}$ doesn't hold for some integers. Select $m$ to be minimal, and it so it must be greater than $1$. With $m$ chosen, select $n$ to be minimal when working under $m$. Using Catalan theory, we must have $n \gt m$.
We have  $[n,m] = [n-1, m] + [n, m-1]$ and by the minimality conditions,
$$\tag 2  [n-1, m] =  \frac{n-1-m+1}{n} \binom{n-1+m}{n-1}$$
$$\tag 3  [n, m-1] =  \frac{n-m+2}{n+1} \binom{n+m-1}{n}$$
if we can show that adding $\text(2)$ and $\text(3)$ together gives the RHS of $\text(1)$ we will have a contradiction. But the proof is found in the accepted answer at
Proving an algebraic binomial identity related to Bertrand's ballot theorem
