Delannoyn numerot

Delanoy-luvut [1] (tai Delanoy-luvut [2] ; fr. Delannoy ) D(a, b) kombinatoriikassa kuvaavat polkujen lukumäärää suorakaiteen muotoisen hilan vasemmasta alakulmasta ( a , b ) diagonaalisesti vastakkaiseen kulmaan, käyttämällä vain ylöspäin suuntautuvia liikkeitä, oikealle tai ylös-oikealle (" kuningasliike "). A - ulotteisessa soluautomaatissa D(a,b) on annettu solujen lukumäärä von Neumannin alueella , jonka säde on b , sekvenssi on A008288 OEIS : ssä ; solujen lukumäärä naapuruston pinnalla määritellään sekvenssillä A266213 OEIS : ssä . Nimetty ranskalaisen matemaatikon Henri Auguste Delannoyn mukaan[3] .

Joitakin merkityksiä

Neliöruudukossa n × n ensimmäiset Delannoy-luvut (alkaen n = 0:sta) ovat sarja A001850 OEIS : ssä :

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

Esimerkiksi D(3,3)=63, koska 3 × 3 neliössä on 63 erilaista Delannoy-polkua:

Polut, jotka eivät nouse diagonaalin yläpuolelle, kuvaavat Schroeder-lukuja .

Lisäarvot näkyvät taulukossa:

k\n	0	yksi	2	3	neljä	5	6	7	kahdeksan	9	kymmenen
0	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi	yksi
yksi	yksi	3	5	7	9	yksitoista	13	viisitoista	17	19	21
2	yksi	5	13	25	41	61	85	113	145	181	221

Ominaisuudet

Delannoy-luvut täyttävät rekursiivisen suhteen : , alkuehdoksi voidaan ottaa D (0, k )= D ( k ,0)=1. ${\näyttötyyli \ D(m,n)=D(m-1,n)+D(m-1,n-1)+D(m,n-1)}$

Tämä yhtälö on analoginen Pascalin kolmion kanssa binomiaalisille kertoimille C( m , n ):

{\näyttötyyli \ C(m,n)=C(m-1,n)+C(n-1,m)}

joka viittaa samojen kärkien välisten polkujen määrään, mutta edellyttäen, että liikkeet vain solujen sivuilla ovat sallittuja.

Jos otamme huomioon paikat, joissa polut leikkaavat diagonaalin, voimme johtaa Delannoy-lukujen ja binomikertoimien välisen suhteen [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)

sitä paitsi

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

jossa sekvenssi on A266213 OEIS : ssä . $A(m,k)$

Luoda funktio numeroille:

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

Kun otetaan huomioon neliölliset polut, Delannoy-luvut ovat:

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

, missä on Legendren polynomi .

P_n(x)

Muut ominaisuudet heille:

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

Katso myös

Muistiinpanot

↑ Smirnov E. Yu. Kolme näkymää atsteekkien timantista
↑ Kohas K. Atsteekkien timanttien ja neliöiden halkaisu dominoiksi
↑ Banderier, Cyril & Schwer, Sylviane (2005), Miksi Delannoy-numerot? , Journal of Statistical Planning and Inference, osa 135 (1): 40–54 , DOI 10.1016/j.jspi.2005.02.004
↑ Martin Aigner. Luettelokurssi . - Springer, 2007. - s . 19 . - ISBN 978-3-540-39032-4 .

Linkit

Weisstein, Eric W. Delannoy Number (englanniksi) Wolfram MathWorld -verkkosivustolla .
Richard P Stanley. Enumeratiivinen kombinatoriikka. - Cambridge University Press, 1999. - V. 2. - P. 185. - ISBN 0-521-56069-1 .
Delannoy-numeroiden maininta venäjänkielisessä artikkelissa.