Delannoy numre

Delannoy-tal [1] (eller Delanoy-tal [2] ; fr. Delannoy ) D(a, b) beskriver i kombinatorik antallet af stier fra det nederste venstre hjørne af et rektangulært gitter ( a , b ) til det diagonalt modsatte hjørne, kun ved at bruge opadgående træk, højre eller op-højre (" kongetræk "). I en a - dimensionel cellulær automat D(a,b) er antallet af celler i von Neumann-kvarteret med radius b givet , sekvensen er A008288 i OEIS ; antallet af celler på overfladen af nabolaget er specificeret af sekvensen A266213 i OEIS . Opkaldt efter den franske matematiker Henri Auguste Delannoy[3] .

Nogle betydninger

For et n × n kvadratisk gitter er de første Delannoy-tal (startende med n = 0) sekvensen A001850 i OEIS :

1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, …

For eksempel, D(3,3)=63, da der er 63 forskellige Delannoy-stier i et 3 × 3 kvadrat:

Stier, der ikke hæver sig over diagonalen, beskriver Schroeder-tal .

Yderligere værdier er vist i tabellen:

k\n	0	en	2	3	fire	5	6	7	otte	9	ti
0	en	en	en	en	en	en	en	en	en	en
en	en	3	5	7	9	elleve	13	femten	17	19	21
2	en	5	13	25	41	61	85	113	145	181	221

Egenskaber

Delannoy-tal opfylder den rekursive relation : , som startbetingelser kan vi tage D (0, k )= D ( k ,0)=1. $\ D(m,n)=D(m-1,n)+D(m-1,n-1)+D(m,n-1)$

Denne ligning er analog med Pascals trekant for binomiale koefficienter C( m , n ):

\ C(m,n)=C(m-1,n)+C(n-1,m)

som refererer til antallet af stier mellem de samme hjørner, men forudsat at kun bevægelser på siderne af cellerne er tilladt.

Hvis vi tager højde for de steder, hvor stierne skærer diagonalen, så kan vi udlede en sammenhæng mellem Delannoy-tal og binomiale koefficienter [4] :

\ D(m,n)=\sum _{k=0}^{m}C(m,k)C(n+mk,m)=\sum _{k=0}^{m} 2^{k}C(m,k)C(n,k)

Udover

D(m,n)=\sum _{k=0}^{n}A(m,k),

hvor sekvensen er A266213 i OEIS . $A(m,k)$

Genereringsfunktion for tal:

\sum _{p,q=0}^{\infty}D(p,q)x^{p}y^{q}={\frac {1}{1-xy-xy))

Når kvadrerede stier betragtes, er Delannoy-tallene:

D(n)=D(n,n)=P_{n}(3)

, hvor er Legendre polynomiet .

P_n(x)

Andre egenskaber for dem:

D(n)={\frac {3(2n-1)D(n-1)-(n-1)D(n-2)}{n))

\sum _{n=0}^{\infty}D(n)x^{n}={\frac {1}{\sqrt {1-6x+x^{2))))=1 +3x+13x^{2}+63x^{3}+321x^{4}+\ldots

Se også

Noter

↑ Smirnov E. Yu. Tre synspunkter på den aztekiske diamant
↑ Kohas K. Opdeler aztekiske diamanter og firkanter i dominobrikker
↑ Banderier, Cyril & Schwer, Sylviane (2005), Hvorfor Delannoy-numre? , Journal of Statistical Planning and Inference bind 135 (1): 40–54 , DOI 10.1016/j.jspi.2005.02.004
↑ Martin Aigner. Et kursus i opregning . - Springer, 2007. - S. 19 . - ISBN 978-3-540-39032-4 .

Delannoy numre

Nogle betydninger

Egenskaber

Se også

Noter

Links