# Number of positive integer walks from 0 to b.

It is well known that the number of walks of length $m=2k+1$ starting at $0$ and ending at $0$ of step size $\pm 1$ and always nonnegative is the number of Dyck paths from $(0,0)$ to $(k,k)$ i.e. the $k^{th}$ Catalan number $C_k$. The following seems like it should be well known but I have been having trouble locating it: how many walks of length $m=2k+b$ are there starting at $0$ and ending at $b$ of step size $\pm1$ and always nonnegative? Bonus points for a reference.

-
Are you familiar with the proof that the number of nonnegative paths from $(0,0)$ to $(2k,0)$ is $C_k$ that uses reflection through $y=-1$ ? This argument can be easily adjusted to show that the number of nonnegative paths from $(0,0)$ to $(2k+b,b)$ is $\binom{2k+b}{k}-\binom{2k+b}{k-1}$. – tipshoni Jul 2 '12 at 20:46
I am not... should that be easy to locate? – Sora Jul 2 '12 at 21:28
Look for "ballot numbers" or "Catalan triangle". You will find the values in OEIS A009766 and sequences linked there – Henry Jul 2 '12 at 22:18

Here's another proof.

First we consider the following conclusion, which is really George N. Raney's result in Functional composition patterns and power series reversion:

If $\langle x_1,x_2,\ldots,x_m\rangle$ is any sequence of integers with $x_j\le1$ for all $j$, and with $x_1+x_2+\cdots+x_m=l>0$, then exactly $l$ of the cyclic shifts $$\langle x_1,x_2,\ldots,x_m\rangle,\langle x_2,\ldots,x_m,x_1\rangle,\ldots,\langle x_m,x_1,\ldots,x_{m-1}\rangle$$ have all positive partial sums.

It can be proved by a simple geometric argument (I don't know how to describe it in English, but you can see an algebraic proof in Concrete Mathematics by Graham, Knuth and Patashnik, EXERCISE 7.13).

Now it's easier to solve your original problem. First we add $+1$ to the beginning of each sequence, to make the partial sums positive (and each one with the partial sums positive can be deleted the first term to get a sequence with nonnegative partial sums, so it's bijection). There're $\binom{2k+b+1}{k+b+1}$ sequences with $k$ occurences of $-1$ and $k+b+1$ occurences of $+1$, and Raney's lemma tells us that exactly $(b+1)/(2k+b+1)$ sequences (Why? See next paragraph) have all partial sums positive. So the answer is $$\frac{b+1}{2k+b+1}\binom{2k+b+1}{k+b+1}=\frac{b+1}{k+b+1}\binom{2k+b}{k+b}=\frac{b+1}{k+b+1}\binom{2k+b}k$$.

Explanation for $(b+1)/(2k+b+1)$: Construct $N\times(2k+b+1)$ array, where $N=\binom{2k+b+1}{k+b+1}$. Each line is just $2k+b+1$ cyclic shifts of the first term, and the first column is $N$ sequences with $k$ occurences of $-1$ and $k+b+1$ occurences of $+1$. Each row contains exactly one solution, so there're exactly $N$ occurences of solutions. Each solution appears exactly once in each column, so it appears exactly $2k+b+1$ times in the whole array.

-

Here's the completely elementary, though somewhat tricky, argument using reflection:

Let's try to count the number of paths starting at $(0,0)$, ending in $(2k+b,b)$ that are not nonnegative:

By reflecting through the line $y=-1$ the part of the path from $(0,0)$ until the first time it goes below the x-axis, we get a bijection between the non-nonegative paths from $(0,0)$ to $(2k+b,b)$ and all paths from $(0,-2)$ to $(2k+b,b)$, whose number is clearly $\binom{2k+b}{k-1}$.

So We get that the number of non-nonnegative paths from $(0,0)$ to $(2k+b,b)$ is $\binom{2k+b}{k-1}$, and since the number of all paths from $(0,0)$ to $(2k+b,b)$ is $\binom{2k+b}{k}$, we conclude that the desired number of nonnegative paths from $(0,0)$ to $(2k+b,b)$ is $\binom{2k+b}{k}-\binom{2k+b}{k-1}$ (which is indeed $\frac{b+1}{k+b+1}\binom{2k+b}{k}$)

-

In the latter part of this article, I use generating functions to show that the number of walks of length $2k+b$ starting at $0$ and ending at $b$ where no partial sum is negative is $$\frac{b+1}{k+b+1}\binom{2k+b}{k}$$

-
Note that $$\frac{b+1}{k+b+1}\binom{2k+b}{k} = \binom{2k+b}{k}-\binom{2k+b}{k-1}$$ which is the formula cited by tipshoni. – robjohn Jul 2 '12 at 23:40
Do you know Raney's lemma? – Frank Science Jul 3 '12 at 6:07
@FrankScience: I do now :-) – robjohn Jul 3 '12 at 12:02