Closed-form solution of the recurrence relation $f(m,n)=f(m-1,n)+f(m,n-1)+f(m-1,n-1)$

106 Views Asked by At

I'm working with the recurrence relation $f(m,n)=f(m-1,n)+f(m,n-1)+f(m-1,n-1)$, with the boundary condition $f(m,0)=f(0,n)=1$.

After some work, it is not hard to show the generating function is $F(x,y):=\sum_{n,m=0}^{\infty}f(m,n)x^my^n=\frac{1}{1-x-y-xy}$.

Computing $f(m,n)$ seems rather cumbersome because a trinomial expansion is involved. The furtherest I could go is $$ f(m,n)=\sum_{k=0}^{\min(m,n)}\frac{(n+m-k)!}{(n-k)!(m-k)!k!} $$

I'm wondering if $f(m,n)$ could be further simplified?

1

There are 1 best solutions below

0
On BEST ANSWER

These are Delannoy numbers and there is no "simple" formula, you can't further simplify your expression, but you can get some alternatives on the wikipedia page or at OEIS A008288, for example:

$$ f(m,n)=\sum_{k=0}^{\min(m,n)}\binom{m}{k}\binom{n}{k}2^k $$