- Números de Delannoy
-
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
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[1] que permite calcular los números de Delannoy sin necesidad de Recursión:
.Referencias
- ↑ Aigner, Martin (2007). A course in enumeration. Springer. pp. 19. Graduate Text in Mathematics. ISBN 978-3-540-39032-4.
- Stanley, Richard P. (1999). Enumerative Combinatorics. Vol. 2. Cambridge University Press. pp. 185. ISBN 0-521-56069-1.
Categorías:- Combinatoria enumerativa
- Sucesiones de números enteros
Wikimedia foundation. 2010.
