Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
3  
In general, when you have a sequence of numbers you're interesting in learning more about, the OEIS (oeis.org), which Douglas Zare links to in his answer, is a great place to start looking. –  Mike Spivey Jan 27 '11 at 12:21
    
Thanks for the tip! Will definitely do that next time. Thanks to everyone for helping me on this one!! –  mcuturi Jan 27 '11 at 21:53
add comment

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.