Números de Delannoy

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:

\ 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

  1. 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. 

Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Chronologie de la vie d'Honoré de Balzac — Honoré de Balzac, né Honoré Balzac[1],[2],[3], à Tours le 20 mai 1799 (1er prairial an VII) et mort à Paris le 18  …   Wikipédia en Français

  • ASSIETTE AU BEURRE (L’) — ASSIETTE AU BEURRE L’ (1901 1914) Hebdomadaire de seize pages environ, tiré en couleurs, L’Assiette au beurre est l’aboutissement de la caricature sociale et de mœurs telle que Le Rire , Le Courrier français et Le Chambard socialiste l’ont… …   Encyclopédie Universelle

  • Mouvement De Libération Des Femmes — Pour les articles homonymes, voir MLF. En France, le Mouvement de libération des femmes est né de plusieurs courants, de réformistes à radicaux. A la fois héritier du mouvement de mai 1968 et du Women s Lib américain naissant, des luttes pour le… …   Wikipédia en Français

  • Mouvement de liberation des femmes — Mouvement de libération des femmes Pour les articles homonymes, voir MLF. En France, le Mouvement de libération des femmes est né de plusieurs courants, de réformistes à radicaux. A la fois héritier du mouvement de mai 1968 et du Women s Lib… …   Wikipédia en Français

  • Mouvement de libération des femmes — Pour les articles homonymes, voir MLF. En France, le Mouvement de libération des femmes est né de plusieurs groupes et courants, de réformistes à radicaux[1]. À la fois héritier du mouvement de mai 1968 et du Women s Lib américain naissant, des… …   Wikipédia en Français

  • Mouvement de libération des femmes (MLF) — Mouvement de libération des femmes Pour les articles homonymes, voir MLF. En France, le Mouvement de libération des femmes est né de plusieurs courants, de réformistes à radicaux. A la fois héritier du mouvement de mai 1968 et du Women s Lib… …   Wikipédia en Français

  • Saison 2 de Interpol — Cet article présente le guide des épisodes de la deuxième saison de la série télévisée Interpol. Celle ci a une numérotation assez particulière, car la première saison n est en réalité composée que de l épisode pilote[1]. Saison 2 de Interpol… …   Wikipédia en Français

  • Paris Saint-Germain Football Club (féminines) — Infobox club sportif Paris Saint Germain FC …   Wikipédia en Français

  • Cirque — Pour les articles homonymes, voir Cirque (homonymie). Chapiteau du cirque Barum en Allemagne. Dans son acception moderne, un cirque est une troupe d artistes, tra …   Wikipédia en Français

  • Cirques — Cirque Pour les articles homonymes, voir Cirque (homonymie). Chapiteau du cirque Barum en Allemagne. Dans son acception moderne, un c …   Wikipédia en Français

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”