Números de Delannoy
# Números de Delannoy

En matemáticas, un número de Delannoy $D$ describe el número de caminos desde la esquina suroeste (0, 0) de una cuadrícula rectangular hasta la esquina noreste (m, n), usando solo pasos individuales al norte, noreste o este. Los números de Delannoy llevan el nombre del oficial del ejército francés y matemático aficionado Henri Delannoy.

El número de Delannoy $D(m,n)$ también cuenta el número de alineaciones globales de dos secuencias de longitudes $m$ y $n$, el número de puntos en un retículo entero o politopo de cruce de dimensión m que están como máximo a n pasos desde el origen, y, en teorías de autómatas celulares, el número de celdas en una vecindad de von Neumann de dimensión m y de radio n, mientras que el número de celdas en una superficie de una vecindad de von Neumann de dimensión m de radio n se da con (sucesión A266213 en OEIS).

En combinatoria, los números de Delannoy D(m,n) son coeficientes que cuentan el número de caminos de Delannoy, esto es, caminos que van de (0,0) a (m,n) usando los movimientos

* (a,b) → (a,b+1),
* (a,b) → (a+1,b),
* (a,b) → (a+1,b+1).

Así, por ejemplo D(3,2)=25 puesto que hay 25 caminos de Delannoy, ilustrados en la figura.

Los primeros números de Delannoy se ilustran en la siguiente matriz rectangular:

| k\n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| - | - | - | - | - | - | - | - | - | - | - | - |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 |
| 2 | 1 | 5 | 13 | 25 | 41 | 61 | 85 | 113 | 145 | 181 | 221 |

## Fórmulas relativas a números de Delannoy

El hecho de que sólo es posible llegar a (m,n) pasando por uno de los tres vértices (m-1,n), (m-1,n-1), (m,n-1) se establece una ecuación de recurrencia:

   $\ D(m,n)=D(m-1,n)+D(m-1,n-1)+D(m,n-1)$,

donde D(0,k)=D(k,0)=1.

Esta ecuación está relacionada con la Identidad de Pascal para coeficientes binomiales C(m,n):

   $\ C(m,n)=C(m-1,n)+C(n-1,m)$.

puesto que los coeficientes binomiales se pueden interpretar como el número de caminos entre (0,0) y (m,n) usando únicamente los movimientos vertical y horizontal.

Clasificando los caminos de Delannoy de acuerdo al número de pasos diagonales, se obtiene la siguiente fórmula que permite calcular los números de Delannoy sin necesidad de recursión:

   $\ D(m,n)=\sum _{k}C(m,k)C(n+k,m)$.

## Ejemplo

El número de Delannoy D(3,3) es igual a 63. La siguiente figura ilustra los 63 caminos de Delannoy de (0, 0) a (3, 3):

El subconjunto de caminos que no se elevan por encima de la diagonal SW-NE se cuentan mediante una familia de números relacionados, los números de Schröder.

## Matriz de Delannoy

La matriz de Delannoy es una matriz de los números Delannoy:

    mn  0 1 2 3 4 5 6 7 8 0 111111111 1 1357911131517 2 151325416185113145 3 172563129231377575833 4 1941129321681128922413649 5 1116123168116833653718313073 6 113853771289365389891982540081 7 115113575224171831982548639108545 8 11714583336491307340081108545265729 9 119181115956412236375517224143598417

En esta matriz, los números de la primera fila son todos uno, los números de la segunda fila son los números pares e impares, los números de la tercera fila son los números cuadrados centrados y los números de la cuarta fila son los números octaédricos centrados. Alternativamente, los mismos números se pueden organizar en una matriz triangular parecida al Triángulo de Pascal, también llamado triángulo tribonacci, en el que cada número es la suma de los tres números anteriores:

## Números centrales de Delannoy

Los números centrales de Delannoy D(n)= D(n,n) son los números para un cuadrado n'' × cuadrícula n. Los primeros números centrales de Delannoy (que comienzan con n=0) son:

    1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, ... (sucesión A001850 en OEIS).

## Cálculo

### Números de Delannoy

Para $k$ pasos diagonales (es decir, noreste), debe haber $m-k$ pasos en la dirección $x$ y $n-k$ pasos en la dirección $y$ para alcanzar el punto $(m,n)$. Como estos pasos se pueden realizar en cualquier orden, el número de dichas rutas viene dado por el teorema multinomial

    ${\binom {m+n-k}{k,m-k,n-k}}={\binom {m+n-k}{m}}{\binom {m}{k}}$

Por lo tanto, se obtiene la expresión de forma cerrada

    $D(m,n)=\sum _{k=0}^{\min(m,n)}{\binom {m+n-k}{m}}{\binom {m}{k}}.$

Una expresión alternativa viene dada por

    $D(m,n)=\sum _{k=0}^{\min(m,n)}{\binom {m}{k}}{\binom {n}{k}}2^{k}$

o por la serie infinita

    $D(m,n)=\sum _{k=0}^{\infty }{\frac {1}{2^{k+1}}}{\binom {k}{n}}{\binom {k}{m}}.$

Y también

    $D(m,n)=\sum _{k=0}^{n}A(m,k),$

donde $A(m,k)$ se da con (sucesión A266213 en OEIS).

La relación de recurrencia básica para los números de Delannoy se ve fácilmente como

    $D(m,n)={\begin{cases}1&{\text{si }}m=0{\text{ o }}n=0\\D(m-1,n)+D(m-1,n-1)+D(m,n-1)&{\text{en caso contrario}}\end{cases}}$

Esta relación de recurrencia también conduce directamente a la función generadora

    $\sum _{m,n=0}^{\infty }D(m,n)x^{m}y^{n}=(1-x-y-xy)^{-1}.$

### Números centrales de Delannoy

Sustituyendo $m=n$ en la primera expresión de forma cerrada anterior, reemplazando $k\leftrightarrow n-k$ y un poco de álgebra, se obtiene

    $D(n)=\sum _{k=0}^{n}{\binom {n}{k}}{\binom {n+k}{k}},$

mientras que la segunda expresión anterior produce

    $D(n)=\sum _{k=0}^{n}{\binom {n}{k}}^{2}2^{k}.$

Los números centrales de Delannoy satisfacen también una relación de recurrencia de tres términos entre ellos,

    $nD(n)=3(2n-1)D(n-1)-(n-1)D(n-2),$

y tienen una función generadora

    $\sum _{n=0}^{\infty }D(n)x^{n}=(1-6x+x^{2})^{-1/2}.$

El comportamiento asintótico principal de los números centrales de Delannoy viene dado por

    $D(n)={\frac {c\,\alpha ^{n}}{\sqrt {n}}}\,(1+O(n^{-1}))$

donde

    $\alpha =3+2{\sqrt {2}}\approx 5.828$

y

    $c=(4\pi (3{\sqrt {2}}-4))^{-1/2}\approx 0.5727$.
