General expression of $f(a, b)$ if $f(a, b)=f(a-1,b) + f(a, b-1) + f(a-1, b-1)$?

Question

$f(a,b) = f(a-1, b) + f(a-1, b-1) + f(a, b-1), ab \neq 0$
$f(a,b) = 1, ab = 0$
So what is $f(a, b)$?

Answer 1

These numbers actually have a name. They're called Delannoy numbers.

The link here is to the On-Line Encyclopedia of Integer Sequences. Generally, when you have a sequence of integers that you want to learn more about the OEIS is a great place to start looking. For instance, both Robin Chapman's and Qiaochu Yuan's formulas are given at the link provided, as well as some other formulas and a large number of references and related problems.

Answer 2

I don't know about a formula for $f(a,b)$, but the generating function is $$\sum_{a,b=0}^\infty f(a,b)x^ay^b=\frac1{1-x-y-xy}.$$

Answer 3

I doubt there's a nice closed form in both entries. For example, the diagonal entries $f(n, n)$ have generating function

$$\sum_{n=0}^{\infty} f(n, n) x^n = \frac{1}{\sqrt{1 - 6x - x^2}}$$

which can be proven using the methods described here, but suggests that $f(n, n)$ doesn't have a product formula (for example like the Catalan numbers do).

For fixed $n$, it turns out that

$$\sum_{m=0}^{\infty} f(m, n) x^m = \frac{(1 + x)^n}{(1 - x)^{n+1}}$$

which translates into the binomial identity

$$f(m, n) = \sum_{k=0}^{n} {n \choose k} {m + n-k \choose n}$$

but this identity isn't terribly useful for large $n$.

Answer 4

Following Robin Chapman's answer, $$\sum_{a,b \geq 0} f(a,b)x^a y^b = \frac{1}{1-x-y-xy} = \sum_{n \geq 0} (x+y+xy)^n = \sum_{n \geq 0} \sum_{i+j+k=n} \frac{n!}{i!j!k!} x^i y^j (xy)^k$$ so $$f(a,b)=\sum_{k=0}^{\min (a,b)} \frac{(a+b-k)!}{(a-k)!(b-k)!k!}$$