Delannoy számok

A Delanoy számok [1] (vagy Delanoy számok [2] ; fr. Delannoy ) D(a, b) a kombinatorikában egy téglalaprács ( a , b ) bal alsó sarkától az átlósan szemközti sarokig tartó utak számát írják le , csak felfelé irányuló mozdulatokkal, jobbra vagy fel-jobbra („ királymozgás ”). Egy a -dimenziós D(a,b) sejtautomatában a Neumann b sugarú szomszédságában lévő sejtek száma adott , a szekvencia az OEIS -ben A008288 ; a szomszédság felszínén lévő cellák számát az A266213 szekvencia határozza meg az OEIS -ben . Nevét Henri Auguste Delannoy francia matematikusról kapta [3] .

Néhány jelentés

Egy n × n négyzetrács esetén az első Delannoy-számok ( n = 0-val kezdődnek) az A001850 sorozat az OEIS -ben :

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

Például D(3,3)=63, mivel egy 3 × 3-as négyzetben 63 különböző Delannoy útvonal van:

Azok az utak, amelyek nem emelkednek az átló fölé, a Schroeder-számokat írják le .

A további értékek a táblázatban láthatók:

k\n	0	egy	2	3	négy	5	6	7	nyolc	9	tíz
0	egy	egy	egy	egy	egy	egy	egy	egy	egy	egy
egy	egy	3	5	7	9	tizenegy	13	tizenöt	17	19	21
2	egy	5	13	25	41	61	85	113	145	181	221

Tulajdonságok

A Delannoy számok kielégítik a rekurzív relációt : , kezdeti feltételként vehetjük D (0, k )= D ( k ,0)=1. ${\megjelenítési stílus \ D(m,n)=D(m-1,n)+D(m-1,n-1)+D(m,n-1)}$

Ez az egyenlet analóg Pascal-háromszöggel a C( m , n ) binomiális együtthatók esetében :

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

amely ugyanazon csúcsok közötti utak számára vonatkozik, de feltéve, hogy csak a cellák oldalain szabad mozogni.

Ha figyelembe vesszük azokat a helyeket, ahol az utak metszik az átlót, akkor összefüggést kaphatunk a Delannoy-számok és a binomiális együtthatók között [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)

kívül

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

ahol a szekvencia az A266213 az OEIS -ben . $A(m,k)$

Függvény generálása számokhoz:

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

Ha a négyzetes útvonalakat vesszük figyelembe, a Delannoy-számok a következők:

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

, hol van a Legendre polinom .

P_n(x)

Egyéb tulajdonságok számukra:

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}+\lpont

Lásd még

Jegyzetek

↑ Smirnov E. Yu. Három nézet az azték gyémántról
↑ Kohas K. Azték gyémántok és négyzetek hasítása dominókra
↑ Banderier, Cyril & Schwer, Sylviane (2005), Miért a Delannoy-számok? , Journal of Statistical Planning and Inference 135 (1): 40–54 , DOI 10.1016/j.jspi.2005.02.004
↑ Martin Aigner. Egy tanfolyam a felsorolásról . - Springer, 2007. - 19. o . - ISBN 978-3-540-39032-4 .

Linkek

Weisstein, Eric W. Delannoy szám (angolul) a Wolfram MathWorld webhelyén .
Richard P Stanley. Enumeratív kombinatorika. - Cambridge University Press, 1999. - V. 2. - P. 185. - ISBN 0-521-56069-1 .
A Delannoy-számok említése egy orosz nyelvű cikkben.