Delannoy siffror

Delannoy-tal [1] (eller Delanoy-tal [2] ; fr. Delannoy ) D(a, b) beskriver i kombinatorik antalet banor från det nedre vänstra hörnet av ett rektangulärt gitter ( a , b ) till det diagonalt motsatta hörnet, med endast uppåtgående rörelser, höger eller uppåt-höger (" kungsdrag "). I en a - dimensionell cellulär automat D(a,b) ges antalet celler i von Neumann-området med radie b , sekvensen är A008288 i OEIS ; antalet celler på ytan av grannskapet specificeras av sekvensen A266213 i OEIS . Uppkallad efter den franske matematikern Henri Auguste Delannoy[3] .

Vissa betydelser

För ett n × n kvadratiskt rutnät är de första Delannoy-talen (som börjar med n = 0) sekvensen A001850 i OEIS :

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

Till exempel, D(3,3)=63, eftersom det finns 63 olika Delannoy-banor i en 3 × 3 kvadrat:

Vägar som inte stiger över diagonalen beskriver Schroeder-tal .

Ytterligare värden visas i tabellen:

k\n	0	ett	2	3	fyra	5	6	7	åtta	9	tio
0	ett	ett	ett	ett	ett	ett	ett	ett	ett	ett
ett	ett	3	5	7	9	elva	13	femton	17	19	21
2	ett	5	13	25	41	61	85	113	145	181	221

Egenskaper

Delannoy-tal uppfyller det rekursiva sambandet : , som initiala villkor kan vi ta D (0, k )= D ( k ,0)=1. $\ D(m,n)=D(m-1,n)+D(m-1,n-1)+D(m,n-1)$

Denna ekvation är analog med Pascals triangel för binomialkoefficienter C( m , n ):

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

som hänvisar till antalet banor mellan samma hörn, men förutsatt att endast rörelser på sidorna av cellerna är tillåtna.

Om vi tar hänsyn till platserna där banorna skär diagonalen, så kan vi härleda ett samband mellan Delannoy-tal och binomialkoefficienter [4] :

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

Förutom

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

där sekvensen är A266213 i OEIS . $A(m,k)$

Genereringsfunktion för siffror:

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

När kvadratiska banor beaktas är Delannoy-talen:

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

, var är Legendre-polynomet .

P_n(x)

Andra egenskaper för 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 även

Anteckningar

↑ Smirnov E. Yu. Tre synpunkter på den aztekiska diamanten
↑ Kohas K. Delar upp aztekiska diamanter och rutor till dominobrickor
↑ Banderier, Cyril & Schwer, Sylviane (2005), Varför Delannoy-siffror? , Journal of Statistical Planning and Inference vol 135 (1): 40–54 , DOI 10.1016/j.jspi.2005.02.004
↑ Martin Aigner. En kurs i uppräkning . - Springer, 2007. - S. 19 . - ISBN 978-3-540-39032-4 .

Länkar

Weisstein, Eric W. Delannoy Number (engelska) på Wolfram MathWorld- webbplatsen .
Richard P Stanley. Enumerativ kombinatorik. - Cambridge University Press, 1999. - V. 2. - P. 185. - ISBN 0-521-56069-1 .
Omnämnande av Delannoy-nummer i en ryskspråkig artikel.