Números de Delannoy
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.
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 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: 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:
Esta ecuación está relacionada con la Identidad de Pascal para coeficientes binomiales C(m,n):
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.
El número de Delannoy D(3,3) es igual a 63.
La matriz de Delannoy es una matriz de los números Delannoy:[6] 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,[7] en el que cada número es la suma de los tres números anteriores: 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: Para
pasos diagonales (es decir, noreste), debe haber
Como estos pasos se pueden realizar en cualquier orden, el número de dichas rutas viene dado por el teorema multinomial Por lo tanto, se obtiene la expresión de forma cerrada Una expresión alternativa viene dada por o por la serie infinita Y también donde
La relación de recurrencia básica para los números de Delannoy se ve fácilmente como Esta relación de recurrencia también conduce directamente a la función generadora Sustituyendo
en la primera expresión de forma cerrada anterior, reemplazando
y un poco de álgebra, se obtiene mientras que la segunda expresión anterior produce Los números centrales de Delannoy satisfacen también una relación de recurrencia de tres términos entre ellos,[8] y tienen una función generadora El comportamiento asintótico principal de los números centrales de Delannoy viene dado por donde y
