You've essentially described the Delannoy Numbers. See http://www.research.att.com/~nja… for a list of references.

This isn't exactly a closed form, but here's a formula that might be helpful to you:

[math] f(x,y) = \sum_{d=0}^{\min\{x-1,y-1\}} 2^d \binom{x-1}{d}\binom{y-1}{d}.[/math]

Although this doesn't solve the general problem, it gives you a simple upper-bound. I think the bound would be tight when

[math]x \approx y[/math] but would be very loose when [math]x << y[/math] or [math]y << x[/math].

[math]f(x, y) \leq (1 + \sqrt{2})^{x+y}[/math]

You can prove that this holds by induction. It clearly holds when [math]x=1[/math] or [math]y=1[/math]. For the induction:

Let [math]\phi=1+\sqrt{2}[/math]

[math]f(x, y) = f(x-1,y) + f(x-1, y-1)[/math] [math] + f(x, y-1)[/math]

[math] \leq 2\phi^{x+y-1} + \phi^{x+y-2} [/math]

[math] = \phi^{x+y} [/math]

Side note: as always one guesses that value of [math]\phi[/math] by solving [math]\phi^2 = 2\phi + 1[/math]