Números de Delannoy

Hi ha 25 camins de Delannoy entre (0,0) i (3,2), per tant D(3,2)=25

En matemàtiques, un número de Delannoy $D$ descriu el número de camins des del cantó suroest (0, 0) d'una cuadrícula rectangular fins al cantó noreste (m, n), usant sol passos individuals al nort, noreste o est. Els números de Delannoy duen el nom de l'oficial de l'eixèrcit francés i matemàtic aficionat Henri Delannoy.^[1]

El número de Delannoy $D (m, n)$ també conta el número d'alliniacions globals de dos seqüències de llongituts $m$ i $n$ ,^[2] el número de punts en un retícul sancer o politopo de creuament de dimensió m que estan com a màxim a n passos des de l'orige, i, en teories d'autómates celulars, el número de celes en una veïnat de von Neumann de dimensió m i de ràdio n, mentres que el número de celes en una superfície d'una veïnat de von Neumann de dimensió m de ràdio n es dona en Plantilla:OEIS.

En combinatòria, els números de Delannoy D(m,n) són coeficients que conten el número de camins de Delannoy, açò és, camins que van de (0,0) a (m,n) usant els moviments

(a,b) → (a,b+1),
(a,b) → (a+1,b),
(a,b) → (a+1,b+1).

Aixina, per eixemple D(3,2)=25 lloc que hi ha 25 camins de Delannoy, ilustrats en la figura.

Els primers números de Delannoy s'ilustren en la següent matriu rectangular:

k	! 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òrmules relatives a números de Delannoy

El fet de que només és possible aplegar a (m,n) passant per un dels tres vèrtiços (m-1,n), (m-1,n-1), (m,n-1) s'establix una equació de recurrencia:

$D (m, n) = D (m - 1, n) + D (m - 1, n - 1) + D (m, n - 1)$ ,

a on D(0,k)=D(k,0)=1.

Esta equació està relacionada en l'Identitat de Pascal para coeficients binomiales C(m,n):

$C (m, n) = C (m - 1, n) + C (n - 1, m)$ .

posat que els coeficients binomiales es poden interpretar com el número de camins entre (0,0) i (m,n) usant únicament els moviments vertical i horisontal.

Classificant els camins de Delannoy d'acort al número de passos diagonals, s'obté la següent fòrmula^[3] que permet calcular els números de Delannoy sense necessitat de recursión:

$D (m, n) = \sum_{k} C (m, k) C (n + k, m)$ .

Eixemple

El número de Delannoy D(3,3) és igual a 63. La següent figura ilustra els 63 camins de Delannoy de (0, 0) a (3, 3):

Archiu:Delannoy3x3.svg

El subconjunt de camins que no s'eleven per damunt de la diagonal SW-NE es conten per mig d'una família de números relacionats, els números de Schröder.

Vore també

Referències

↑ (2005).«Why Delannoy numbers?».Journal of Statistical Planning and Inference.135(1)
40–54.doi:10.1016/j.jspi.2005.02.004.
↑ (2004).«The number of distinct alignments of two strings».Journal of Quantitative Linguistics.11(3)
173–182.doi:10.1080/0929617042000314921.
↑ Aigner, Martin (2007). A course in enumeration, Springer, pp. 19. ISBN 978-3-540-39032-4.

Bibliografia

Stanley (1999). Enumerative Combinatorics. Vol. 2, Cambridge University Press, pp. 185. ISBN 0-521-56069-1.

Referències

Este artícul conté una traducció derivada de «Números de Delannoy» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] (2005).«Why Delannoy numbers?».Journal of Statistical Planning and Inference.135(1)
40–54.doi:10.1016/j.jspi.2005.02.004.

[2] (2004).«The number of distinct alignments of two strings».Journal of Quantitative Linguistics.11(3)
173–182.doi:10.1080/0929617042000314921.

[3] Aigner, Martin (2007). A course in enumeration, Springer, pp. 19. ISBN 978-3-540-39032-4.

[1]

[2]

[3]