Număr eulerian

șir polinomial

În combinatorică un număr eulerian A(n, m) este numărul de 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:

Număr eulerian
Numit dupăLeonhard Euler
Anul publicării1755
Nr. de termeni cunoscuțiinfinit
Primii termeni1, 1, 1, 1, 4, 1, 1, 11, 11, 1, 1, 26, 66, 26, 1, 1,57, 302, 57, 1, 1, 120, 1191, 2416
Index OEIS
  • A008292
  • Triangle of Eulerian numbers
Nu confundați cu e (constantă matematică).

Polinoamele euleriene sunt definite de funcția generatoare exponențială:

Polinoamele euleriene pot fi calculate prin recursivitate:

Un mod echivalent de a scrie această definiție este de a stabili polinoamele euleriene inductiv prin:

Alte notații pentru A(n, m) sunt E(n, m) și .

 
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 α1(x) = 1, α2(x) = x + 1, α3(x) = x2 + 4x + 1 etc. (v. facsimilul). Aceste polinoame sunt o primă formă a ceea ce se numesc acum polinoamele euleriene An(x).

Properietăți fundamentale

modificare

Pentru o valoare dată n > 0, indicele m din A(n, m) poate lua valori de la 0 la n − 1. Pentru n fix există o singură permutare care are 0 ascensiuni: (n, n − 1, n − 2, ..., 1). Există, de asemenea, o singură permutare care are n − 1 ascensiuni; aceasta este permutarea cu ordine crescătoare (1, 2, 3, ..., n). Prin urmare, A(n, 0) și A(n, n − 1) sunt 1 pentru toate valorile lui n.

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

Valorile lui A(n, m) pot fi calculate manual pentru valori mici ale lui n și m. De exemplu

n m Permutări A(n, m)
1 0 (1) A(1,0) = 1
2 0 (2, 1) A(2,0) = 1
1 (1, 2) A(2,1) = 1
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ă

 

De exemplu

 

Valorile lui A(n, m) pentru 0 ≤ n ≤ 9 sunt:[1]

 m
n 
0 1 2 3 4 5 6 7 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

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 factorialul n!.

Formula explicită

modificare

Formula explicită pentru A(n, m) este[2]

 

Se poate vedea din această formulă, precum și din interpretarea combinatorică, că   pentru  , astfel încât   este un polinom de gradul   pentru  .

Proprietățile sumelor

modificare

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

 

Suma alternantă a numerelor euleriene pentru o valoare fixă a lui n este legată de numerele Bernoulli⁠(d) Bn+1

 

Alte proprietăți ale sumelor numerelor euleriene sunt:

 
 

unde Bn este al n-lea număr Bernoulli.

Identități

modificare

Numerele euleriene sunt implicate în funcția generatoare pentru șirul n al puterilor:

 

pentru  . Asta presupune că 00 = 0 și A(0,0) = 1 (deoarece există o permutare a elementelor inexistente și nu are ascensiuni).

Identitatea lui Worpitzky[3] exprimă xn ca o combinație liniară⁠(d) de numere euleriene cu coeficienții binomiali:

 

Din identitatea lui Worpitzky rezultă că

 

Altă identitate interesantă este

 

Numărătorul din membrul drept este un polinom eulerian.

Pentru o funcție fixă   care este integrabilă pe   există formula integrală[4]

 

Numele euleriene de ordinul al doillea

modificare

Permutările 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 dublul factorial⁠(d) (2n−1)!!. Numărul eulerian de ordinul al doilea, notat  , 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:

 

cu condiția inițială pentru n = 0, exprimată în notația cu paranteze Iverson:

 

Corespunzător, polinomul eulerian de ordinul al doilea, notat aici Pn (nu există nicio notație standard pentru ele) sunt

 

iar relațiile de recurență de mai sus sunt transformate într-o relație de recurență pentru șirul Pn(x):

 

cu condiția inițială

 

Această din urmă recurență poate fi scrisă într-o formă oarecum mai compactă cu ajutorul unui factor integrant:

 

astfel încât funcția rațională

 

satisface o recurență autonomă simplă:

 

de unde se obțin polinoamele euleriene de ordinul al doilea ca Pn(x) = (1−x)2n un(x), și numerele euleriene de ordinul al doilea drept coeficienți.

Iată câteva valori ale numerelor euleriene de ordinul al doilea:

 m
n 
0 1 2 3 4 5 6 7 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 Pn(1), este (2n − 1)!!.

Indexarea numerelor euleriene de ordinul al doilea vine în trei variante: după Riordan și Comtet[5], OEIS A201637 după Graham, Knuth și Patashnik[6] și OEIS A340556, extinzând definiția lui Gessel și Stanley[7].

  1. ^ Șirul A008292 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
  2. ^ L. Comtet, 1974, p. 243
  3. ^ de Worpitzky, J. (). „Studien über die Bernoullischen und Eulerschen Zahlen”. Journal für die reine und angewandte Mathematik. 94: 203–232. 
  4. ^ Exercițiul 6.65 din Concrete Mathematics de Graham, Knuth și Patashnik
  5. ^ Șirul A008517 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
  6. ^ Șirul A201637 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
  7. ^ Șirul A340556 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)

Bibliografie

modificare

Legături externe

modificare