Număr eulerian
Numit după | Leonhard Euler |
---|---|
Anul publicării | 1755 |
Nr. de termeni cunoscuți | infinit |
Primii termeni | 1, 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 |
|
Î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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/43/EulerianPolynomialsByEuler1755.png/330px-EulerianPolynomialsByEuler1755.png)
Î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
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]
- mn
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ă
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
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
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
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:
- mn
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].
Note
- ^ Șirul A008292 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
- ^ L. Comtet, 1974, p. 243
- ^ de Worpitzky, J. (). „Studien über die Bernoullischen und Eulerschen Zahlen”. Journal für die reine und angewandte Mathematik. 94: 203–232.
- ^ Exercițiul 6.65 din Concrete Mathematics de Graham, Knuth și Patashnik
- ^ Șirul A008517 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
- ^ Șirul A201637 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
- ^ Șirul A340556 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
Bibliografie
- la 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 Carlitz, L. (). „Eulerian Numbers and polynomials”. Math. Mag. 32 (5): 247–260. doi:10.2307/3029225. JSTOR 3029225.
- en Gould, H. W. (). „Evaluation of sums of convolved powers using Stirling and Eulerian Numbers”. Fib. Quart. 16 (6): 488–497.
- en Desarmenien, Jacques; Foata, Dominique (). „The signed Eulerian numbers”. Discrete Math. 99 (1–3): 49–58. doi:10.1016/0012-365X(92)90364-L
.
- en Lesieur, Leonce; Nicolas, Jean-Louis (). „On the Eulerian Numbers M=max (A(n,k))”. Europ. J. Combinat. 13 (5): 379–399. doi:10.1016/S0195-6698(05)80018-6
.
- en Butzer, P. L.; Hauss, M. (). „Eulerian numbers with fractional order parameters”. Aequationes Mathematicae. 46 (1–2): 119–142. doi:10.1007/bf01834003.
- en Koutras, M.V. (). „Eulerian numbers associated with sequences of polynomials”. Fib. Quart. 32 (1): 44.
- en Graham; Knuth; Patashnik (). Concrete Mathematics: A Foundation for Computer Science (ed. 2nd). Addison-Wesley. pp. 267–272.
- en Hsu, Leetsch C.; Jau-Shyong Shiue, Peter (). „On certain summation problems and generalizations of Eulerian polynomials and numbers”. Discrete Math. 204 (1–3): 237–247. doi:10.1016/S0012-365X(98)00379-3
.
- en Boyadzhiev, Khristo N. (). „Apostol-Bernoulli functions, derivative polynomials and Eulerian polynomials”. arXiv:0710.1124
[math.CA].
- en Petersen, T. Kyle (). Eulerian Numbers. Birkhäuser Advanced Texts Basler Lehrbücher. Birkhäuser. pp. 3–18. doi:10.1007/978-1-4939-3091-3_1. ISBN 978-1-4939-3090-6.
Legături externe
- en Eulerian Polynomials at OEIS Wiki.
- en Eric W. Weisstein, Eulerian Number la MathWorld.
- en Eric W. Weisstein, Euler's Number Triangle la MathWorld.
- en Eric W. Weisstein, Worpitzky's Identity la MathWorld.
- en Eric W. Weisstein, Second-Order Eulerian Triangle la MathWorld.
- en Euler-matrix (generalized rowindexes, divergent summation)
![]() | Portal Matematică |