Números de Delannoy

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Hay 25 caminos de Delannoy entre (0,0) y (3,2), por tanto D(3,2)=25.

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 el siguiente arreglo 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 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[editar]

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[1] 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).

Referencias[editar]

  1. Aigner, Martin (2007). A course in enumeration. Springer. p. 19. ISBN 3-540-39032-4. Graduate Text in Mathematics. 
  • Stanley, Richard P. (1999). Enumerative Combinatorics. Vol. 2. Cambridge University Press. p. 185. ISBN 0-521-56069-1.