3
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$ Jan 27, 2011 at 12:21
  • $\begingroup$ Thanks for the tip! Will definitely do that next time. Thanks to everyone for helping me on this one!! $\endgroup$
    – mcuturi
    Jan 27, 2011 at 21:53

1 Answer 1

6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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