Números de Delannoy

Henri–Auguste Delannoy
Números de Delannoy
Nombrado por	Henri–Auguste Delannoy
No. de términos conocidos	Infinito
Fórmula
índice OEIS	A008288; Raíz cuadrada 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.[1]

Hay 25 caminos de Delannoy entre (0,0) y (3,2), por tanto D(3,2)=25

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$ ,[2] 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,[3] 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,[4] 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[5] 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:[6]

m n	0	1	2	3	4	5	6	7	8
0	1	1	1	1	1	1	1	1	1
1	1	3	5	7	9	11	13	15	17
2	1	5	13	25	41	61	85	113	145
3	1	7	25	63	129	231	377	575	833
4	1	9	41	129	321	681	1289	2241	3649
5	1	11	61	231	681	1683	3653	7183	13073
6	1	13	85	377	1289	3653	8989	19825	40081
7	1	15	113	575	2241	7183	19825	48639	108545
8	1	17	145	833	3649	13073	40081	108545	265729
9	1	19	181	1159	5641	22363	75517	224143	598417

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:

            1
          1 1
        1 3 1
      1 5 5 1
    1 7 13 7 1
  1 9 25 25 9 1
1 11 41 63 41 11 1

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,[8]

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

.

Véase también

Referencias

Banderier, Cyril; Schwer, Sylviane (2005), «Why Delannoy numbers?», Journal of Statistical Planning and Inference 135 (1): 40-54, S2CID 16226115, arXiv:math/0411128, doi:10.1016/j.jspi.2005.02.004.
Covington, Michael A. (2004), «The number of distinct alignments of two strings», Journal of Quantitative Linguistics 11 (3): 173-182, S2CID 40549706, doi:10.1080/0929617042000314921.
Luther, Sebastian; Mertens, Stephan (2011), «Counting lattice animals in high dimensions», Journal of Statistical Mechanics: Theory and Experiment 2011 (9): P09026, Bibcode:2011JSMTE..09..026L, S2CID 119308823, arXiv:1106.1078, doi:10.1088/1742-5468/2011/09/P09026.
Breukelaar, R.; Bäck, Th. (2005), «Using a Genetic Algorithm to Evolve Behavior in Multi Dimensional Cellular Automata: Emergence of Behavior», Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation (GECCO '05), New York, NY, USA: ACM, pp. 107-114, ISBN 1-59593-010-8, S2CID 207157009, doi:10.1145/1068009.1068024.
Aigner, Martin (2007). A course in enumeration. Springer. p. 19. ISBN 3-540-39032-4. Graduate Text in Mathematics.
Sulanke, Robert A. (2003), «Objects counted by the central Delannoy numbers», Journal of Integer Sequences 6 (1): Article 03.1.5, MR 1971435.
(sucesión A008288 en OEIS)
Peart, Paul; Woan, Wen-Jin (2002). «A bijective proof of the Delannoy recurrence». Congressus Numerantium 158: 29-33. ISSN 0384-9864. Zbl 1030.05003.

Bibliografía

Stanley, Richard P. (1999). Enumerative Combinatorics. Vol. 2. Cambridge University Press. p. 185. ISBN 0-521-56069-1.

Enlaces externos

Weisstein, Eric W. «Delannoy Number». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.

Datos: Q2886564

Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.

[1] Banderier, Cyril; Schwer, Sylviane (2005), «Why Delannoy numbers?», Journal of Statistical Planning and Inference 135 (1): 40-54, S2CID 16226115, arXiv:math/0411128, doi:10.1016/j.jspi.2005.02.004.

[2] Covington, Michael A. (2004), «The number of distinct alignments of two strings», Journal of Quantitative Linguistics 11 (3): 173-182, S2CID 40549706, doi:10.1080/0929617042000314921.

[3] Luther, Sebastian; Mertens, Stephan (2011), «Counting lattice animals in high dimensions», Journal of Statistical Mechanics: Theory and Experiment 2011 (9): P09026, Bibcode:2011JSMTE..09..026L, S2CID 119308823, arXiv:1106.1078, doi:10.1088/1742-5468/2011/09/P09026.

[4] Breukelaar, R.; Bäck, Th. (2005), «Using a Genetic Algorithm to Evolve Behavior in Multi Dimensional Cellular Automata: Emergence of Behavior», Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation (GECCO '05), New York, NY, USA: ACM, pp. 107-114, ISBN 1-59593-010-8, S2CID 207157009, doi:10.1145/1068009.1068024.

[5] Aigner, Martin (2007). A course in enumeration. Springer. p. 19. ISBN 3-540-39032-4. Graduate Text in Mathematics.

[6] Sulanke, Robert A. (2003), «Objects counted by the central Delannoy numbers», Journal of Integer Sequences 6 (1): Article 03.1.5, MR 1971435.

[7] (sucesión A008288 en OEIS)

[8] Peart, Paul; Woan, Wen-Jin (2002). «A bijective proof of the Delannoy recurrence». Congressus Numerantium 158: 29-33. ISSN 0384-9864. Zbl 1030.05003.