Ver el código de «Números de Delannoy»

{{Ficha de serie entera
|named_after= Henri–Auguste Delannoy
|terms_number= [[Infinito]]
|formula= <math>D(m,n)= \sum_{k=0}^{\min(m,n)} \binom{m}{k} \binom{n}{k} 2^k</math>
|OEIS= A008288
|OEIS_name= Raíz cuadrada de Delannoy
}}

[[Archivo:Delannoy32.svg|thumb|275px|Hay 25 caminos de Delannoy entre (0,0) y (3,2), por tanto D(3,2)=25]]

En [[matemáticas]], un '''número de Delannoy''' <math>D</math> 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]].<ref>{{citation|last1=Banderier|first1=Cyril|last2=Schwer|first2=Sylviane|title=Why Delannoy numbers?|year=2005|journal=Journal of Statistical Planning and Inference|volume=135|issue=1|pages=40–54|arxiv=math/0411128|doi=10.1016/j.jspi.2005.02.004|s2cid=16226115 }}</ref>

El número de Delannoy <math> D(m,n) </math> también cuenta el número de [[Alineamiento de secuencias|alineaciones globales]] de dos secuencias de longitudes <math>m</math> y <math>n</math>,<ref>{{citation|last=Covington|first=Michael A.|year=2004|title=The number of distinct alignments of two strings|journal=Journal of Quantitative Linguistics|volume=11|issue=3|pages=173–182|doi=10.1080/0929617042000314921|s2cid=40549706 }}</ref> 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,<ref>{{citation
|last1= Luther|first1= Sebastian
|last2= Mertens|first2= Stephan
|arxiv= 1106.1078
|issue= 9
|journal= Journal of Statistical Mechanics: Theory and Experiment
|page= P09026
|title= Counting lattice animals in high dimensions
|url= http://stacks.iop.org/1742-5468/2011/i=09/a=P09026
|volume= 2011
|year= 2011|bibcode= 2011JSMTE..09..026L
|doi= 10.1088/1742-5468/2011/09/P09026
|s2cid= 119308823
 }}</ref> y, en teorías de [[Autómata celular|autómatas celulares]], el número de celdas en una [[vecindad de von Neumann]] de dimensión ''m'' y de radio ''n'',<ref>{{citation
|last1= Breukelaar|first1= R.
|last2= Bäck|first2= Th.
|contribution= Using a Genetic Algorithm to Evolve Behavior in Multi Dimensional Cellular Automata: Emergence of Behavior
|doi= 10.1145/1068009.1068024
|isbn= 1-59593-010-8
|location= New York, NY, USA
|pages= 107–114
|publisher= ACM
|title= Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation (GECCO '05)
|year= 2005|s2cid= 207157009
 }}</ref> 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 {{OEIS|id=A266213}}.

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:
{| class="wikitable"
! 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 [[Recursión|ecuación de recurrencia]]:
{{ecuación|<math>\ D(m,n)=D(m-1,n) + D(m-1,n-1) + D(m,n-1)</math>,|3=left}}
donde ''D''(0,''k'')=''D''(''k'',0)=1.

Esta ecuación está relacionada con la Identidad de Pascal para [[coeficientes binomiales]]  C(''m'',''n''):
{{ecuación|<math>\ C(m,n) = C(m-1,n)+C(n-1,m)</math>.|3=left}}
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<ref>{{cita libro|apellidos=Aigner|nombre=Martin|editorial=Springer|título=A course in enumeration|año=2007|id=Graduate Text in Mathematics|páginas=19|isbn=978-3-540-39032-4}}</ref> que permite calcular los números de Delannoy sin necesidad de recursión:
{{ecuación|1=<math>\ D(m,n)=\sum_k C(m,k)C(n+k,m)</math>.|3=left}}

==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):

<center>[[Image:Delannoy3x3.svg]]</center>

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úmero de Schröder|números de Schröder]].

==Matriz de Delannoy==
La '''matriz de Delannoy''' es una [[matriz (matemática)|matriz]] de los números Delannoy:<ref>{{citation
|last= Sulanke|first= Robert A.
|title= Objects counted by the central Delannoy numbers
|year= 2003
|journal= Journal of Integer Sequences
|volume= 6
|issue= 1
|page= Article 03.1.5
|mr= 1971435
|url= http://www.emis.de/journals/JIS/VOL6/Sulanke/delannoy.pdf}}</ref>

:{|class="wikitable" style="text-align:right;"
|-
! {{diagonal split header|''n''&nbsp;|&nbsp;''m''}}
! width="50"|0
! width="50"|1
! width="50"|2
! width="50"|3
! width="50"|4
! width="50"|5
! width="50"|6
! width="50"|7
! width="50"|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úmero cuadrado centrado|números cuadrados centrados]] y los números de la cuarta fila son los [[número octaédrico centrado|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''',<ref>{{OEIS|A008288|name=Matriz cuadrada de números de Delannoy D(i,j) (i >= 0, j >= 0) leída por antidiagonales}}</ref> 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'''' &times; 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, ... {{OEIS|id=A001850}}.

==Cálculo==

===Números de Delannoy===
Para <math> k </math> pasos diagonales (es decir, noreste), debe haber <math> m-k </math> pasos en la dirección <math> x </math> y <math> n-k </math> pasos  en la dirección <math> y </math> para alcanzar el punto <math> (m, n) </math>. Como estos pasos se pueden realizar en cualquier orden, el número de dichas rutas viene dado por el [[teorema multinomial]]

:<math> \binom{m+n-k}{k , m-k , n-k}= \binom{m+n-k}{m} \binom{m}{k} </math>

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

:<math> D(m,n)= \sum_{k=0}^{\min(m,n)} \binom{m+n-k}{m} \binom{m}{k} . </math>

Una expresión alternativa viene dada por

:<math> D(m,n)= \sum_{k=0}^{\min(m,n)} \binom{m}{k} \binom{n}{k} 2^k  </math>

o por la serie infinita

:<math> D(m,n)= \sum_{k=0}^\infty \frac{1}{2^{k+1}} \binom{k}{n} \binom{k}{m}. </math>

Y también

:<math> D(m,n)= \sum_{k=0}^{n} A(m,k), </math>

donde <math> A(m,k) </math> se da con {{OEIS|id=A266213}}.

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

:<math>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}</math>

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

:<math> \sum_{m,n= 0}^\infty D(m, n) x^m y^n= (1 - x - y - xy)^{-1} . </math>

===Números centrales de Delannoy===
Sustituyendo <math> m= n </math> en la primera expresión de [[Forma cerrada (matemática)|forma cerrada]] anterior, reemplazando <math> k \leftrightarrow n-k </math> y un poco de álgebra, se obtiene

:<math> D(n)= \sum_{k=0}^n \binom{n}{k} \binom{n+k}{k} , </math>

mientras que la segunda expresión anterior produce

:<math> D(n)= \sum_{k=0}^n \binom{n}{k}^2 2^k . </math>

Los números centrales de Delannoy satisfacen también una relación de recurrencia de tres términos entre ellos,<ref>{{cite journal|last1=Peart|first1=Paul|last2=Woan|first2=Wen-Jin|title=A bijective proof of the Delannoy recurrence|year=2002|journal=Congressus Numerantium|volume=158|pages=29–33|issn=0384-9864|zbl=1030.05003}}</ref>

:<math> n D(n)= 3(2n-1)D(n-1) - (n-1)D(n-2) , </math>

y tienen una función generadora

:<math> \sum_{n= 0}^\infty D(n) x^n= (1-6x+x^2)^{-1/2} . </math>

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

:<math> D(n)= \frac{c \, \alpha^n}{\sqrt{n}} \, (1 + O(n^{-1})) </math>

donde

:<math> \alpha= 3 + 2 \sqrt{2} \approx 5.828 </math>

y

:<math> c= (4 \pi (3 \sqrt{2} - 4))^{-1/2} \approx 0.5727 </math>.

==Véase también==
*[[Número de Motzkin]]
*[[Números de Narayana]]

== Referencias ==
{{listaref}}

==Bibliografía==
* {{cita libro|apellidos=Stanley|nombre=Richard P.|editorial=[[Cambridge University Press]]|año=1999|páginas=185|título=Enumerative Combinatorics. Vol. 2|isbn=0-521-56069-1}}

==Enlaces externos==
*{{MathWorld|title=Delannoy Number|urlname=DelannoyNumber}}

{{Control de autoridades}}
{{ORDENAR:Numeros de Delannoy}}
[[Categoría:Combinatoria]]
[[Categoría:Sucesiones de números enteros|Delannoy]]
[[Categoría:Números epónimos en matemáticas|Delannoy]]
[[Categoría:Triángulos de números]]