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$ Commented 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
    Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .