Î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:
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 .
Istoric 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 , , etc. (v. facsimilul). Aceste polinoame sunt o primă formă a ceea ce se numesc acum polinoamele euleriene An(x).
Properietăți fundamentale 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 {| 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ă
De exemplu
Valorile lui A(n, m) pentru 0 ≤ n ≤ 9 sunt: {| class="wikitable" style="text-align:right;" |- ! ! 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
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ă Formula explicită pentru A(n, m) esteL. Comtet, 1974, p. 243
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 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 Bn+1
Alte proprietăți ale sumelor numerelor euleriene sunt:
unde Bn este al n-lea număr Bernoulli.
Identități 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 exprimă xn ca o combinație liniară 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ăExercițiul 6.65 din Concrete Mathematics de Graham, Knuth și Patashnik
Numele euleriene de ordinul al doillea 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 (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: {| class="wikitable" style="text-align:right;" |- ! ! 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 Pn(1), este (2n − 1)!!.
Indexarea numerelor euleriene de ordinul al doilea vine în trei variante: după Riordan și Comtet, OEIS A201637 după Graham, Knuth și Patashnik și OEIS A340556, extinzând definiția lui Gessel și Stanley.
Note
Bibliografie 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.
Legături externe Eulerian Polynomials at OEIS Wiki.
Euler-matrix (generalized rowindexes, divergent summation)
Categorie:Combinatorică Categorie:Subiecte factoriale și binomiale Categorie:Șiruri de numere întregi Categorie:Triunghiuri de numere