Număr Delannoy

Număr Delannoy

Numit după	Henri–Auguste Delannoy
Nr. de termeni cunoscuți	infinit
Formula	$D(m,n)=\sum _{k=0}^{\min(m,n)}{\binom {m}{k}}{\binom {n}{k}}2^{k}$
Index OEIS	A008288 Square array of Delannoy

În matematică, un număr Delannoy D descrie numărul de căi de la colțul de sud-vest (stânga–jos) (0, 0) al unei rețele dreptunghiulare până la colțul din nord-est (dreapta–sus) (m, n), folosind doar pași simpli spre nord, nord-est și est. Numerele Delannoy sunt numite după ofițerul armatei franceze și matematicianul amator Henri Delannoy.

Numărul Delannoy $D(m,n)$ arată și numărul de alinieri din două secvențe de lungimi $m$ și $n$, numărul de puncte dintr-o latice întreagă m-dimensională care se află la maximum n pași de origine, iar în automatele celulare numărul de celule într-o vecinătate von Neumann m-dimensională de rază n unde numărul de celule pe o astfel de suprafață m-dimensională de rază n este dat de seria OEIS A266213.

Exemplu

Numărul Delannoy D(3,3) este 63. Figura următoare ilustrează cele 63 de căi Delannoy de la (0, 0) la (3, 3):

Submulțimea căilor care nu trec deasupra diagonalei SW–NE sunt date de șirul numerelor Schröder.

Matricea Delannoy

Matricea Delannoy este o matrice infinită de numere Delannoy:

m n	0	1	2	3	4	5	6	7	8
0	1	1	1	1	1	1	1	1	1
1	1	3	5	7	9	11	13	15	17
2	1	5	13	25	41	61	85	113	145
3	1	7	25	63	129	231	377	575	833
4	1	9	41	129	321	681	1289	2241	3649
5	1	11	61	231	681	1683	3653	7183	13073
6	1	13	85	377	1289	3653	8989	19825	40081
7	1	15	113	575	2241	7183	19825	48639	108545
8	1	17	145	833	3649	13073	40081	108545	265729
9	1	19	181	1159	5641	22363	75517	224143	598417

În această matrice, numerele din primul rând sunt toate unu, numerele din al doilea rând sunt numerele impare, numerele din al treilea sunt numerele centrate pătratice iar numerele din al patrulea sunt numerele centrate octaedrice. Alternativ, aceleași numere pot fi aranjate într-o matrice triunghiulară asemănătoare cu triunghiul lui Pascal, numit și triunghi tribonacci. în care fiecare număr este suma a trei numere din triunghiul de deasupra sa:

            1
          1   1
        1   3   1
      1   5   5   1
    1   7  13   7   1
  1   9  25  25   9   1
1  11  41  63  41  11   1

Numere Delannoy centrale

Numerele Delannoy centrale D(n) = D(n,n) sunt numerele dintr-o rețea pătrată n × n. Primele numere Delannoy centrale (începând cu n=0) sunt:

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

Calcul

Numerel Delannoy

Făcând pași $k$ diagonali (spre NE), pentru a ajunge în punctul $(m,n)$ trebuie efectuați $m-k$ pași în direcția $x$ și $n-k$ pași în direcția $y$. Pașii pot fi efectuați în orice ordine, astfel că numărul de căi este dat de teorema multinomială ${\binom {m+n-k}{k,m-k,n-k}}={\binom {m+n-k}{m}}{\binom {m}{k}}$. Prin urmare, se obține expresia în forma

$D(m,n)=\sum _{k=0}^{\min(m,n)}{\binom {m+n-k}{m}}{\binom {m}{k}}.$

O altă expresie este dată de

$D(m,n)=\sum _{k=0}^{\min(m,n)}{\binom {m}{k}}{\binom {n}{k}}2^{k}$

sau de seria infinită

$D(m,n)=\sum _{k=0}^{\infty }{\frac {1}{2^{k+1}}}{\binom {k}{n}}{\binom {k}{m}}.$

Și de asemenea

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

unde valorile $A(m,k)$ formează șirul OEIS A266213.

Relația de recurență pentru numerele Delannoy este

$D(m,n)={\begin{cases}1&{\text{dacă }}m=0{\text{ sau }}n=0\\D(m-1,n)+D(m-1,n-1)+D(m,n-1)&{\text{altfel}}\end{cases}}$

Această relație de recurență duce la funcția generatoare

$\sum _{m,n=0}^{\infty }D(m,n)x^{m}y^{n}=(1-x-y-xy)^{-1}.$

Numere Delannoy centrale

Substituind $m=n$ în prima expresie de mai sus și înlocuind $k\leftrightarrow n-k$, după cîteva operații algebrice se obține:

$D(n)=\sum _{k=0}^{n}{\binom {n}{k}}{\binom {n+k}{k}},$

în timp ce a doua expresie de mai sus devine:

$D(n)=\sum _{k=0}^{n}{\binom {n}{k}}^{2}2^{k}.$

Numerele Delannoy centrale satisfac, de asemenea, o relație de recurență de trei termeni între ele,

$nD(n)=3(2n-1)D(n-1)-(n-1)D(n-2),$

și au funcția generatoare

$\sum _{n=0}^{\infty }D(n)x^{n}=(1-6x+x^{2})^{-1/2}.$

Numerele Delannoy centrale tind asimptotic spre

$D(n)={\frac {c\,\alpha ^{n}}{\sqrt {n}}}\,(1+O(n^{-1}))$

unde $\alpha =3+2{\sqrt {2}}\approx 5.828$ și $c=(4\pi (3{\sqrt {2}}-4))^{-1/2}\approx 0.5727$.

Vezi și

• Număr Motzkin
• Număr Narayana
• Număr Schröder
• Număr Schröder–Hiparh
• Număr Catalan

Legături externe

• en Eric W. Weisstein, Delannoy Number la MathWorld.