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.
Number of positive integer walks from 0 to b.
2
$\begingroup$
combinatorics
reference-request
catalan-numbers
-
3Are 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}$. – 2012-07-02
-
0I am not... should that be easy to locate? – 2012-07-02
-
0Look for "ballot numbers" or "Catalan triangle". You will find the values in [OEIS A009766](http://oeis.org/A009766) and sequences linked there – 2012-07-02