Números de Delannoy

En matemáticas, un número 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.[1]

Números de Delannoy
Nombrado por Henri–Auguste Delannoy
No. de términos conocidos Infinito
Fórmula
índice OEIS
Hay 25 caminos de Delannoy entre (0,0) y (3,2), por tanto D(3,2)=25

El número de Delannoy también cuenta el número de alineaciones globales de dos secuencias de longitudes y ,[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\n012345678910
0 11111111111
1 13579111315171921
2 151325416185113145181221

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:

,

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

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.

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:

.

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 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,[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 pasos diagonales (es decir, noreste), debe haber pasos en la dirección y pasos en la dirección para alcanzar el punto . 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 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

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

Números centrales de Delannoy

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

.

Véase también

Referencias

  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.

Bibliografía

Enlaces externos

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.