Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
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

3 Answers 3

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

share|improve this answer
    
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

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.