combinatorics - how many ways can I add/subtract 1 from 4 40 times and reach zero without dropping below

Question

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

Answer 1

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.

Answer 2

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}. $$

Answer 3

The generating function is $$ \sum_{n=0}^\infty b_{s,n}x^n=\frac1x\left(\frac{1-\sqrt{1-4x^2}}{2x}\right)^{\large s+1}\tag1 $$ where $b_{s,n}$ is the number of paths of length $n$ with non-negative partial sums that total to $s$.

Here, $s=4$ and $\left[x^{40}\right]\frac1x\left(\frac{1-\sqrt{1-4x^2}}{2x}\right)^5=24647883000$.

---

In this answer, it is shown that $$ \omega(n)=a_{0,n}=\frac1{n+1}\binom{2n}{n}\tag2 $$ where $a_{s,n}=b_{2s,2n}$.

Note that for $n\ge1$, $$ b_{0,n}=b_{1,n-1}\tag3 $$ since to return to $(0,n)$ the prior state must be $(1,n-1)$. Furthermore, for $n,s\ge1$, $$ b_{s,n}=b_{s-1,n-1}+b_{s+1,n-1}\tag4 $$ since to get to $(s,n)$ the prior state must have been $(s-1,n-1)$ or $(s+1,n-1)$.

Applying $(3)$ and $(4)$ a couple of times, we get $$ a_{0,n+1}=a_{0,n}+a_{1,n}\tag5 $$ and for $s\ge1$, $$ a_{s,n+1}=a_{s-1,n}+2a_{s,n}+a_{s+1,n}\tag6 $$ Applying $(5)$ to $(2)$ gives $$ \begin{align} a_{1,n} &=a_{0,n+1}-a_{0,n}\\[6pt] &=\frac1{n+2}\binom{2n+2}{n+1}-\frac1{n+1}\binom{2n}{n}\\ &=\frac{(2n+2)(2n+1)}{(n+2)(n+1)n}\binom{2n}{n+1}-\frac{n+1}{(n+1)n}\binom{2n}{n+1}\\ &=\frac3{n+2}\binom{2n}{n+1}\tag7 \end{align} $$ Lemma: $$ a_{s,n}=\frac{2s+1}{n+s+1}\binom{2n}{n+s}\tag8 $$ Proof: Induction on $s$.

$(8)$ is satisfied by $(2)$ and $(7)$. Now all we need to do is to show that $(8)$ satisfies $(6)$. $$ \begin{align} &a_{s+1,n}+2a_{s,n}+a_{s-1,n}\\[6pt] &=\frac{2s+3}{n+s+2}\binom{2n}{n+s+1}+\frac{4s+2}{n+s+1}\binom{2n}{n+s}+\frac{2s-1}{n+s}\binom{2n}{n+s-1}\\ &=\frac{2s+3}{n+s+2}\frac{(n-s+1)(n-s)}{(2n+2)(2n+1)}\binom{2n+2}{n+s+1}\\ &+\frac{4s+2}{n+s+1}\frac{(n-s+1)(n+s+1)}{(2n+2)(2n+1)}\binom{2n+2}{n+s+1}\\ &+\frac{2s-1}{n+s}\frac{(n+s+1)(n+s)}{(2n+2)(2n+1)}\binom{2n+2}{n+s+1}\\ &=\frac{2s+1}{n+s+2}\binom{2n+2}{n+s+1}\\[6pt] &=a_{s,n+1}\tag9 \end{align} $$ $\large\square$

Corollary $$ b_{s,n}=\frac{s+1}{\frac{n+s}2+1}\binom{n}{\frac{n+s}2}\,[2\mid n+s]\tag{10} $$ Proof: The Lemma proves the case for even $n$ and $s$. We simply need to apply $(4)$ to the Lemma to prove the case for odd $n$ and $s$: $$ \begin{align} b_{2s+1,2n+1} &=b_{2s,2n}+b_{2s+2,2n}\\[6pt] &=a_{s,n}+a_{s+1,n}\\ &=\frac{2s+1}{n+s+1}\binom{2n}{n+s}+\frac{2s+3}{n+s+2}\binom{2n}{n+s+1}\\ &=\frac{2s+1}{n+s+1}\frac{n+s+1}{2n+1}\binom{2n+1}{n+s+1}+\frac{2s+3}{n+s+2}\frac{n-s}{2n+1}\binom{2n+1}{n+s+1}\\ &=\frac{2s+2}{n+s+2}\binom{2n+1}{n+s+1}\tag{11} \end{align} $$ $\large\square$

In this case, $b_{4,40}=a_{2,20}=\frac{5}{23}\binom{40}{22}=24647883000$.

Answer 4

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