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 ), utilizando solo pasos individuales hacia el 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]
Lleva el nombre de | Henri – Auguste Delannoy |
---|---|
No. de términos conocidos | infinito |
Fórmula | |
Índice OEIS |
|
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 una red de enteros m -dimensionales que están como máximo n pasos desde el origen, [3] y, en los autómatas celulares , el número de células en un vecindario de von Neumann m -dimensional de radio n [ 4] mientras que el número de células en una superficie de una vecindad de von Neumann m -dimensional de radio n se da con (secuencia A266213 en la OEIS ).
Ejemplo
El número de Delannoy D (3,3) es igual a 63. La siguiente figura ilustra las 63 rutas de Delannoy desde (0, 0) a (3, 3):
El subconjunto de trayectos que no se elevan por encima de la diagonal SW-NE se cuentan mediante una familia de números relacionada, los números de Schröder .
Matriz Delannoy
La matriz de Delannoy es una matriz infinita de los números de Delannoy: [5]
- metronorte
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 en la primera fila son todos uno, los números en la segunda fila son los números impares , los números en la tercera fila son los números cuadrados centrados y los números en la cuarta fila son los números octaédricos centrados . Alternativamente, los mismos números se pueden organizar en una matriz triangular que se asemeja al triángulo de Pascal , también llamado triángulo tribonacci , [6] en el que cada número es la suma de los tres números que están encima de él:
1 1 1 1 3 1 1 5 5 1 1 7 13 7 1 1 9 25 25 9 11 11 41 63 41 11 1
Números de Central Delannoy
Los números centrales de Delannoy D ( n ) = D ( n , n ) son los números de una cuadrícula cuadrada n × n . Los primeros números centrales de Delannoy (que comienzan con n = 0) son:
Cálculo
Números de Delannoy
Para pasos diagonales (es decir, noreste), debe haber pasos en el dirección y pasos en el dirección para llegar al punto ; Como estos pasos se pueden realizar en cualquier orden, el número de estos caminos viene dado por el coeficiente 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
dónde se da con (secuencia A266213 en la 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 de Central Delannoy
Sustituyendo en la primera expresión de forma cerrada anterior, reemplazando , y un poco de álgebra, da
mientras que la segunda expresión anterior produce
Los números centrales de Delannoy también satisfacen una relación de recurrencia de tres términos entre ellos, [7]
y tener una función generadora
El comportamiento asintótico principal de los números centrales de Delannoy viene dado por
dónde y .
Ver también
Referencias
- ^ Banderier, Cyril; Schwer, Sylviane (2005), "Why Delannoy numbers?", Journal of Statistical Planning and Inference , 135 (1): 40–54, arXiv : math / 0411128 , doi : 10.1016 / j.jspi.2005.02.004 , S2CID 16226115
- ^ Covington, Michael A. (2004), "El número de alineaciones distintas de dos cadenas", Journal of Quantitative Linguistics , 11 (3): 173–182, doi : 10.1080 / 0929617042000314921 , S2CID 40549706
- ^ Lutero, Sebastián; Mertens, Stephan (2011), "Contando animales de celosía en grandes dimensiones" , Journal of Statistical Mechanics: Theory and Experiment , 2011 (9): P09026, arXiv : 1106.1078 , Bibcode : 2011JSMTE..09..026L , doi : 10.1088 / 1742-5468 / 2011/09 / P09026 , S2CID 119308823
- ^ Breukelaar, R .; Bäck, Th. (2005), "Using a Genetic Algorithm to Evolve Behavior in Multi Dimensional Cellular Automata: Emergence of Behavior", Actas de la 7ma Conferencia Anual sobre Computación Genética y Evolutiva (GECCO '05) , Nueva York, NY, EUA: ACM, págs. . 107-114, doi : 10.1145 / 1068009.1068024 , ISBN 1-59593-010-8, S2CID 207157009
- ^ Sulanke, Robert A. (2003), "Objetos contados por los números centrales de Delannoy" (PDF) , Journal of Integer Sequences , 6 (1): Artículo 03.1.5, MR 1971435
- ^ Sloane, N. J. A. (ed.). "Secuencia A008288 (matriz cuadrada de números de Delannoy D (i, j) (i> = 0, j> = 0) leído por antidiagonales)" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.
- ^ Peart, Paul; Woan, Wen-Jin (2002). "Una prueba biyectiva de la recurrencia de Delannoy". Congressus Numerantium . 158 : 29–33. ISSN 0384-9864 . Zbl 1030.05003 .
enlaces externos
- Weisstein, Eric W. "Número de Delannoy" . MathWorld .