# Bertrand's ballot problem - looking for a closed (or say any) formula for $f(n, m)$

While doing some combinatorial counting I found this
recurrence which I do not know how to solve.

$f(n, 0)=1, n \ge 0$

$f(n, n)=0, n \gt 0$

$f(n,m) = f(n-1, m) + f(n, m-1), for \ n \gt m \gt 0$

I did all sorts of things I could think of.
I think it can be expressed with some binomial coefficients
(of $n$ and $m$ of course).

• I'm guessing that $f(n,m)=0$ for $m>n$. Is it right? – Bill O'Haran May 9 '18 at 12:05
• IMO it is not well-defined: By the first equation $f(0,0)=1$ and by the second $f(0,0)=0$. – gammatester May 9 '18 at 12:46
• Assume that we care only about values n > m. We definitely don't care about f(0,0) – peter.petrov May 9 '18 at 12:51
• Can you edit the question then, as the recurrence is now meaningless – ancientmathematician May 9 '18 at 12:53
• @gammatester First formula takes priority then second then third. – peter.petrov May 9 '18 at 12:55

${n+m \choose m} - 2 \cdot {n+m-1\choose m-1}$