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.

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

share|improve this question

4 Answers 4

up vote 9 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer
    
The last "identity" surely doesn't hold, as the RHS doesn't depend on m. –  Marek Nov 9 '10 at 12:33
    
corrected....... –  Robin Chapman Nov 9 '10 at 14:03

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

share|improve this answer

Your Answer

 
discard

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