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.



concise formula for number of paths from (0,0) to (n,m) with horizontal, vertical and diagonal moves?
These are [Delannoy numbers](http://mathworld.wolfram.com/DelannoyNumber.html) [A008288](http://oeis.org/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](http://en.wikipedia.org/wiki/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.


