Vizualizare sursă pentru „Număr eulerian”

{{Infocaseta Șiruri de numere întregi
| named_after = [[Leonhard Euler]]
| publication_year = 1755
| terms_number = infinit
| number = 
| first_terms = [[1 (număr)|1]], 1, 1, 1, [[4 (număr)|4]], 1, 1, [[11 (număr)|11]], 11, 1, 1, [[26 (număr)|26]], [[66 (număr)|66]], 26, 1, 1,[[57 (număr)|57]], [[302 (număr)|302]], 57, 1, 1, [[120 (număr)|120]], 1191, 2416
| OEIS = A008292
| OEIS_name = Triangle of Eulerian numbers
}}

{{Distinge|e (constantă matematică)}}
În [[combinatorică]] un '''număr eulerian''' ''A''(''n'', ''m'') este numărul de [[permutare |permutări]] ale numerelor de la 1 la ''n'' în care exact ''m'' elemente sunt mai mari decât elementul anterior (permutări cu ''m'' „ascensiuni”). Aceștia sunt coeficienții '''polinoamelor euleriene''':
:<math>A_{n}(t) = \sum_{m=0}^{n} A(n,m)\ t^{m}.</math>

Polinoamele euleriene sunt definite de [[funcție generatoare exponențială |funcția generatoare exponențială]]:
: <math>\sum_{n=0}^{\infty} A_{n}(t) \cdot \frac{x^n}{n!} = \frac{t-1}{t - \mathrm{e}^{(t-1) x}}.</math>

Polinoamele euleriene pot fi calculate prin [[recursivitate]]:
:<math>A_{0}(t) = 1,</math>
: <math>A_{n}(t) = t (1-t)\cdot A_{n-1}'(t) + A_{n-1}(t)\cdot (1+(n-1)t),\quad n \ge 1.</math>

Un mod echivalent de a scrie această definiție este de a stabili polinoamele euleriene inductiv prin:
:<math>A_{0}(t) = 1,</math>
: <math>A_{n}(t) = \sum_{k=0}^{n-1} \binom{n}{k} A_{k}(t)\cdot (t-1)^{n-1-k},\quad n \ge 1.</math>

Alte notații pentru ''A''(''n'', ''m'') sunt ''E''(''n'', ''m'') și <math>\textstyle \left\langle {n \atop m} \right\rangle </math>.

== Istoric ==
[[Fișier:EulerianPolynomialsByEuler1755.png|thumb|upright=1.5|Polinoamele cunoscute în prezent drept polinoame euleriene în lucrarea lui Euler din 1755, ''Institutiones calculi differentialis'', part 2, p. 485/6. Coeficienții acestor polinoame sunt cunoscuți ca fiind numere euleriene.]]
În cartea sa ''Institutiones calculi differentialis'' din 1755 [[Leonhard Euler]] a cercetat polinoamele {{math|1=''α''<sub>1</sub>(''x'')&nbsp;=&nbsp;1}}, {{math|1=''α''<sub>2</sub>(''x'')&nbsp;=&nbsp;''x''&nbsp;+&nbsp;1}}, {{math|1=''α''<sub>3</sub>(''x'')&nbsp;=&nbsp;''x''<sup>2</sup>&nbsp;+&nbsp;4''x''&nbsp;+&nbsp;1}} etc. (v. facsimilul). Aceste polinoame sunt o primă formă a ceea ce se numesc acum polinoamele euleriene ''A''<sub>''n''</sub>(''x'').

== Properietăți fundamentale ==
Pentru o [[valoare (matematică) |valoare]] dată ''n''&nbsp;&gt;&nbsp;0, indicele ''m'' din ''A''(''n'', ''m'') poate lua valori de la 0 la ''n''&nbsp;&minus;&nbsp;1. Pentru ''n'' fix există o singură permutare care are 0 ascensiuni: (''n'', ''n''&nbsp;&minus;&nbsp;1, ''n''&nbsp;&minus;&nbsp;2, ..., 1). Există, de asemenea, o singură permutare care are ''n''&nbsp;&minus;&nbsp;1 ascensiuni; aceasta este permutarea cu ordine crescătoare (1, 2, 3, ..., ''n''). Prin urmare, ''A''(''n'', 0) și ''A''(''n'', ''n''&nbsp;&minus;&nbsp;1) sunt 1 pentru toate valorile lui ''n''.

Inversarea unei permutări cu ''m'' ascensiuni creează o altă permutare în care există ''n''&nbsp;&minus;&nbsp;''m''&nbsp;&minus;&nbsp;1 ascensiuni.
Prin urmare, ''A''(''n'', ''m'') = ''A''(''n'', ''n''&nbsp;&minus;&nbsp;''m''&nbsp; &minus;&nbsp;1).

Valorile lui ''A''(''n'', ''m'') pot fi calculate manual pentru valori mici ale lui ''n'' și ''m''. De exemplu
:{| class="wikitable"
|-
! ''n''
! ''m''
! Permutări
! ''A''(''n'', ''m'')
|-
| 1
| 0
| (1)
| ''A''(1,0) = 1
|-
|rowspan="2" | 2
| 0
| (2, 1)
| ''A''(2,0) = 1
|-
| 1
| (1, '''2''')
| ''A''(2,1) = 1
|-
|rowspan="3" | 3
| 0
| (3, 2, 1)
| ''A''(3,0) = 1
|-
| 1
| (1, '''3''', 2) (2, 1, '''3''') (2, '''3''', 1) (3, 1, '''2''')
| ''A''(3,1) = 4
|-
| 2
| (1, '''2''', '''3''')
| ''A''(3,2) = 1
|}

Pentru valori mari ale lui ''n'', ''A''(''n'', ''m'') poate fi calculat cu relația recursivă
:<math>A(n,m)=(n-m)A(n-1,m-1) + (m+1)A(n-1,m).</math>

De exemplu
:<math>A(4,1)=(4-1)A(3,0) + (1+1)A(3,1)=3 \times 1 + 2 \times 4 = 11.</math>

Valorile lui ''A''(''n'', ''m'') pentru 0 ≤ ''n'' ≤ 9 sunt:<ref>{{OEIS|A008292}}</ref>
:{| class="wikitable" style="text-align:right;"
|-
! {{separator diagonal|''n''&nbsp;|&nbsp;''m''}}
! width="50" | 0
! width="50" | 1
! width="50" | 2
! width="50" | 3
! width="50" | 4
! width="50" | 5
! width="50" | 6
! width="50" | 7
! width="50" | 8
|-
! 1
| 1 || || || || || || || ||
|-
! 2
| 1 || 1 || || || || || || ||
|-
! 3
| 1 || 4 || 1 || || || || || ||
|-
! 4
| 1 || 11 || 11 || 1 || || || || ||
|-
! 5
| 1 || 26 || 66 || 26 || 1 || || || ||
|-
! 6
| 1 || 57 || 302 || 302 || 57 || 1 || || ||
|-
! 7
| 1 || 120 || 1191 || 2416 || 1191 || 120 || 1 || ||
|-
! 8
| 1 || 247 || 4293 || 15619 || 15619 || 4293 || 247 || 1 ||
|-
! 9
| 1 || 502 || 14608 || 88234 || 156190 || 88234 || 14608 || 502 || 1
|}

[[Tablou triunghiular |Tabloul triunghiular]] de mai sus se numește '''triunghiul lui Euler''' și are unele caracteristici comune cu [[triunghiul lui Pascal]]. Suma valorilor elementelor din rândul ''n'' este [[factorial]]ul ''n''!.

== Formula explicită ==
Formula explicită pentru ''A''(''n'', ''m'') este<ref>L. Comtet, 1974, p. 243</ref>
:<math>A(n,m)=\sum_{k=0}^{m+1}(-1)^k \binom{n+1}{k} (m+1-k)^n.</math>

Se poate vedea din această formulă, precum și din interpretarea combinatorică, că <math>A(n,n) = 0</math> pentru <math>n>0</math>, astfel încât <math>A_{ n}(t)</math> este un [[polinom]] de [[gradul unui polinom |gradul]] <math>n-1</math> pentru <math>n>0</math>.

== Proprietățile sumelor ==
Din definiția combinatorică reiese clar că suma numerelor euleriene pentru o valoare fixă a lui ''n'' este numărul total de permutări ale numerelor de la 1 la ''n'', deci
:<math>\sum_{m=0}^{n-1}A(n,m)=n! \text{ for }n \ge 1.</math>

Suma ''alternantă'' a numerelor euleriene pentru o valoare fixă a lui ''n'' este legată de {{ill-wd| Q694114||numerele Bernoulli}} ''B''<sub>''n''+1</sub>
:<math>\sum_{m=0}^{n-1}(-1)^{m}A(n,m)=\frac{2^{n+1}(2^{n+1}-1)B_{n+1}}{n+1} \text{ for }n \ge 1.</math>

Alte proprietăți ale sumelor numerelor euleriene sunt:
:<math>\sum_{m=0}^{n-1}(-1)^m\frac{A(n,m)}{\binom{n-1}{m}}=0 \text{ for }n \ge 2,</math>
:<math>\sum_{m=0}^{n-1}(-1)^m\frac{A(n,m)}{\binom{n}{m}}=(n+1)B_{n} \text{ for }n \ge 2,</math>
unde ''B''<sub>''n''</sub> este al ''n''-lea număr Bernoulli.

== Identități ==
Numerele euleriene sunt implicate în funcția generatoare pentru șirul ''n'' al puterilor:
:<math>\sum_{k=0}^{\infty}k^n x^k = \frac{\sum_{m=0}^{n-1}A(n,m)x^{m+1}}{(1-x)^{n+1}} = \frac{x \cdot A_n(x)}{(1-x)^{n+1}}</math>
pentru <math>n \geq 0</math>. Asta presupune că 0<sup>0</sup> = 0 și ''A''(0,0) = 1 (deoarece există o permutare a elementelor inexistente și nu are ascensiuni).

'''Identitatea lui Worpitzky'''<ref>{{de icon}} {{cite journal |last1=Worpitzky |first1=J. |title=Studien über die Bernoullischen und Eulerschen Zahlen |journal=Journal für die reine und angewandte Mathematik |date=1883 |volume=94 |pages=203–232 |url=https://eudml.org/doc/148532}}</ref> exprimă ''x''<sup>''n''</sup> ca o {{ill-wd| Q27628||combinație liniară}} de numere euleriene cu [[coeficient binomial |coeficienții binomiali]]:
:<math>x^n=\sum_{m=0}^{n-1}A(n,m)\binom{x+m}{n}.</math>

Din identitatea lui Worpitzky rezultă că
:<math>\sum_{k=1}^{N}k^n=\sum_{m=0}^{n-1}A(n,m)\binom{N+1+m}{n+1}.</math>

Altă identitate interesantă este
:<math>\frac{e}{1-ex}=\sum_{n=0}^\infty\frac{A_n(x)}{n!(1-x)^{n+1}}.</math>
Numărătorul din membrul drept este un polinom eulerian.

Pentru o funcție fixă <math>f: \mathbb{R} \rightarrow \mathbb{C}</math> care este integrabilă pe <math>(0, n)</math> există formula integrală<ref>Exercițiul 6.65 din ''Concrete Mathematics'' de Graham, Knuth și Patashnik</ref>
:<math>\int_0^1 \cdots \int_0^1 f\left(\left\lfloor x_1 + \cdots + x_n\right\rfloor\right) dx_1 \cdots dx_n = \sum_k A(n, k) \frac{f(k)}{n!}. </math>

== Numele euleriene de ordinul al doillea ==
Permutările [[multimulțime |multimulțimii]] {1, 1, 2, 2, ···, ''n'', ''n''} care au proprietatea că pentru fiecare ''k'', toate numerele care apar între cele două apariții ale lui ''k'' în permutare sunt mai mari decât ''k'' sunt numărate de {{ill-wd| Q13520655||dublul factorial}} (2''n''−1)!!.
Numărul eulerian de ordinul al doilea, notat <math>\scriptstyle \left\langle \! \left\langle {n \atop m} \right\rangle \! \right\rangle</math>, indică numărul tuturor acestor permutări care au exact ''m'' ascensiuni. De exemplu, pentru ''n'' = 3 există 15 astfel de permutări, 1 fără ascensiuni, 8 cu o singură ascensiune și 6 cu două ascensiuni:
: 332211, 
: 221133, 221331, 223311, 233211, 113322, 133221, 331122, 331221,  
: 112233, 122133, 112332, 123321, 133122, 122331. 

Numerele euleriene de ordinul al doilea satisfac relația de recurență, care decurge direct din definiția de mai sus:
:<math> \left\langle \!\! \left\langle {n \atop m} \right\rangle \!\! \right\rangle = (2n-m-1) \left\langle \!\! \left\langle {n-1 \atop m-1} \right\rangle \!\! \right\rangle + (m+1) \left\langle \!\! \left\langle {n-1 \atop m} \right\rangle \!\! \right\rangle, </math>

cu [[condiție inițială |condiția inițială]] pentru ''n'' = 0, exprimată în notația cu paranteze Iverson:
:<math> \left\langle \!\! \left\langle {0 \atop m} \right\rangle \!\! \right\rangle = [m=0]. </math>

Corespunzător, polinomul eulerian de ordinul al doilea, notat aici ''P<sub>n</sub>'' (nu există nicio notație standard pentru ele) sunt
:<math>P_n(x) = \sum_{m=0}^n  \left\langle \!\! \left\langle {n \atop m} \right\rangle \!\! \right\rangle x^m </math>
iar relațiile de recurență de mai sus sunt transformate într-o relație de recurență pentru șirul ''P<sub>n</sub>''(''x''):
:<math> P_{n+1}(x) = (2nx+1) P_n(x) - x(x-1) P_n^\prime(x) </math>
cu condiția inițială
:<math> P_0(x) = 1. </math>

Această din urmă recurență poate fi scrisă într-o formă oarecum mai compactă cu ajutorul unui factor integrant:
:<math> (x-1)^{-2n-2} P_{n+1}(x) = \left( x(1-x)^{-2n-1} P_n(x) \right)^\prime </math>
astfel încât funcția rațională
:<math> u_n(x) = (x-1)^{-2n} P_{n}(x) </math>
satisface o recurență autonomă simplă:
:<math> u_{n+1} = \left( \frac{x}{1-x} u_n \right)^\prime, \quad u_0=1, </math>
de unde se obțin polinoamele euleriene de ordinul al doilea ca ''P<sub>n</sub>''(''x'') = (1−''x'')<sup>2''n''</sup> ''u<sub>n</sub>''(''x''), și numerele euleriene de ordinul al doilea drept coeficienți.

Iată câteva valori ale numerelor euleriene de ordinul al doilea:
:{| class="wikitable" style="text-align:right;"
|-
! {{separator diagonal|''n''&nbsp;|&nbsp;''m''}}
! width="50" | 0
! width="50" | 1
! width="50" | 2
! width="50" | 3
! width="50" | 4
! width="50" | 5
! width="50" | 6
! width="50" | 7
! width="50" | 8
|-
! 1
| 1 || || || || || || || ||
|-
! 2
| 1 || 2 || || || || || || ||
|-
! 3
| 1 || 8 || 6 || || || || || ||
|-
! 4
| 1 || 22 || 58 || 24 || || || || ||
|-
! 5
| 1 || 52 || 328 || 444 || 120 || || || ||
|-
! 6
| 1 || 114 || 1452 || 4400 || 3708 || 720 || || ||
|-
! 7
| 1 || 240 || 5610 || 32120 || 58140 || 33984 || 5040 || ||
|-
! 8
| 1 || 494 || 19950 || 195800 || 644020 || 785304 || 341136 || 40320 ||
|-
! 9
| 1 || 1004 || 67260 || 1062500 || 5765500 || 12440064 || 11026296 || 3733920 || 362880
|}
Suma elementelor din al ''n''-lea rând, care este și valoarea lui ''P''<sub>''n''</sub>(1), este (2''n'' − 1)!!.

Indexarea numerelor euleriene de ordinul al doilea vine în trei variante:  după Riordan și Comtet<ref>{{OEIS|A008517}}</ref>, OEIS A201637 după Graham, Knuth și Patashnik<ref>{{OEIS|A201637}}</ref> și OEIS A340556, extinzând definiția lui Gessel și Stanley<ref>{{OEIS|A340556}}</ref>.

== Note ==
<references responsive/>

== Bibliografie ==
* {{la icon}} Eulerus, Leonardus [Leonhard Euler] (1755). ''Institutiones calculi differentialis cum eius usu in analysi finitorum ac doctrina serierum [Foundations of differential calculus, with applications to finite analysis and series]''. Academia imperialis scientiarum Petropolitana; Berolini: Officina Michaelis.
* {{en icon}} {{cite journal|first1=L. |last1=Carlitz|title=Eulerian Numbers and polynomials | year=1959|journal=Math. Mag.|volume=32 | number=5 | pages=247–260|doi=10.2307/3029225|jstor=3029225}}
* {{en icon}} {{cite journal|first1=H. W. |last1=Gould|title=Evaluation of sums of convolved powers using Stirling and Eulerian Numbers|year=1978|journal=Fib. Quart.|volume =16 |pages=488–497|number=6|url=https://www.fq.math.ca/16-6.html}}
* {{en icon}} {{cite journal|first1=Jacques | last1=Desarmenien | first2=Dominique | last2=Foata | title=The signed Eulerian numbers| journal=Discrete Math.
|year=1992|volume=99 | number=1–3| pages=49–58|doi=10.1016/0012-365X(92)90364-L| doi-access=free}}
* {{en icon}} {{cite journal|year=1992|journal=Europ. J. Combinat. | volume=13 | pages=379–399|number=5|title= On the Eulerian Numbers M=max (A(n,k))|first=Leonce |last1=Lesieur | first2=Jean-Louis | last2=Nicolas|doi=10.1016/S0195-6698(05)80018-6|doi-access=free}}
* {{en icon}} {{cite journal
|first1=P. L. |last1=Butzer | first2=M. |last2=Hauss
|title=Eulerian numbers with fractional order parameters
|journal=Aequationes Mathematicae | year=1993 | volume=46|issue=1–2 |pages=119–142
|url=http://resolver.sub.uni-goettingen.de/purl?GDZPPN002610515 | doi=10.1007/bf01834003
|s2cid=121868847 }}
* {{en icon}} {{cite journal|first1=M.V. |last1=Koutras|title=Eulerian numbers associated with sequences of polynomials|journal=Fib. Quart.|year=1994|pages=44|volume=32|number=1|url=https://www.fq.math.ca/32-1.html}}
* {{en icon}} {{cite book|last1=Graham|
last2=Knuth|last3=Patashnik|year=1994|title=Concrete Mathematics: A Foundation for Computer Science|edition=2nd|publisher=Addison-Wesley|pages=267–272}}
<!-- Vezi și http://www.combinatorics.org/Volume_4/PDF/v4i2r18.pdf -->
* {{en icon}} {{cite journal|first1=Leetsch C. |last1=Hsu | first2=Peter | last2=Jau-Shyong Shiue| title=On certain summation problems and generalizations of Eulerian polynomials and numbers|journal=Discrete Math. | volume=204 | year=1999 |issue=1–3 | doi=10.1016/S0012-365X(98)00379-3|pages=237–247|doi-access=free }}
* {{en icon}} {{cite arXiv|eprint=0710.1124 |title=Apostol-Bernoulli functions, derivative polynomials and Eulerian polynomials|year=2007|first1=Khristo N. |last1=Boyadzhiev|class=math.CA}}
* {{en icon}} {{cite book|first1=T. Kyle|last1= Petersen|year=2015|title=Eulerian Numbers|series= Birkhäuser Advanced Texts Basler Lehrbücher|publisher=Birkhäuser|doi=10.1007/978-1-4939-3091-3_1|pages=3–18|isbn= 978-1-4939-3090-6}}

== Legături externe ==
* {{en icon}} [http://oeis.org/wiki/Eulerian_polynomials Eulerian Polynomials] at [[OEIS]] Wiki. 
* {{en icon}} {{MathWorld|title=Eulerian Number|urlname=EulerianNumber}}
* {{en icon}} {{MathWorld|title=Euler's Number Triangle|urlname=EulersNumberTriangle}}
* {{en icon}} {{MathWorld|title=Worpitzky's Identity|urlname=WorpitzkysIdentity}}
* {{en icon}} {{MathWorld|title=Second-Order Eulerian Triangle|urlname=Second-OrderEulerianTriangle}}
* {{en icon}} [http://go.helms-net.de/math/binomial_new/01_12_Eulermatrix.pdf Euler-matrix] (generalized rowindexes, divergent summation)
{{Portal|Matematică}}

[[Categorie:Combinatorică]]
[[Categorie:Subiecte factoriale și binomiale]]
[[Categorie:Șiruri de numere întregi]]
[[Categorie:Triunghiuri de numere]]