concise formula for number of paths from (0,0) to (n,m) with horizontal, vertical and diagonal moves? The number of increasing paths from (0,0) to (n,m) with only vertical (north) and horizontal (east) moves can be easily proved to be $\binom{n+m}{n}$. When adding the possibility of making diagonal (north-east) moves, I get that the total number of possible paths is $F(n,m)=\sum_{p=\max(n,m)}^{n+m}\binom{p}{n+m-p, p-m, p-n}$.
I am wondering if there is a more concise (without the sum) formula for $F$ or any pointer to a more precise study of $F$? The relation $F(n,m)=F(n-1,m)+F(n-1,m-1)+F(n,m-1)$ can also provide us with the bivariate generating function of $F$ but I am not sure that helps... Many thanks in advance.
 A: These are Delannoy numbers A008288. 
One of the ways they arise is as the count of domino tilings of a modified Aztec diamond. Then the Lindstrom-Gessel-Viennot theorem says that the number of domino tilings of an Aztec diamond of order $n$, $2^{n+1\choose 2}$ is the determinant of $[F(i,j)]_{0\le i,j\le n}$. An LDU decomposition of this matrix into a lower-triangular Pascal's triangle, a diagonal matrix with powers of $2$, and an upper triangular Pascal's triange, is suggested by the formula
$$F(i,j) =  \sum_{d=0} 2^d {i \choose d} {j \choose d},$$
equation 3 on the MathWorld page linked above. Here is the decomposition for $n=4$:
$$\left[ \begin{array}{ccccc} 1 & 1 & 1 & 1 & 1 \\\ 1 & 3 & 5 & 7 & 9 \\\ 1 & 5 & 13 & 25 & 41 \\\ 1 & 7 & 25 & 63 & 129 \\\ 1 & 9 & 41 & 129 & 321
\end{array}
\right]
= \left[\begin{array}{ccccc} 1&0&0&0&0 \\\ 1&1&0&0&0 \\\ 1&2&1&0&0 \\\ 1&3&3&1&0 \\\ 1&4&6&4&1\end{array}\right]
\left[\begin{array}{ccccc} 1 & 0 & 0 &0&0 \\\ 0&2&0&0&0 \\\ 0&0&4&0&0 \\\ 0&0&0&8&0 \\\ 0&0&0&0&16\end{array}\right]
\left[\begin{array}{ccccc} 1&1&1&1&1 \\\ 0&1&2&3&4 \\\ 0&0&1&3&6 \\\ 0&0&0&1&4 \\\ 0&0&0&0&1\end{array}\right]$$
The number of domino tilings of the Aztec diamond of order $4$ is $1\times2\times4\times8\times16$. I think I wrote up a related proof for the enumeration of domino tilings of an Aztec diamond in the domino tiling mailing list in 1997 or 1998.
