Număr eulerian

Î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ă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	A008292 Triangle of Eulerian numbers

Nu confundați cu e (constantă matematică).

$A_{n}(t)=\sum _{m=0}^{n}A(n,m)\ t^{m}.$

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

$\sum _{n=0}^{\infty }A_{n}(t)\cdot {\frac {x^{n}}{n!}}={\frac {t-1}{t-\mathrm {e} ^{(t-1)x}}}.$

Polinoamele euleriene pot fi calculate prin recursivitate:

$A_{0}(t)=1,$

$A_{n}(t)=t(1-t)\cdot A_{n-1}'(t)+A_{n-1}(t)\cdot (1+(n-1)t),\quad n\geq 1.$

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

$A_{0}(t)=1,$

$A_{n}(t)=\sum _{k=0}^{n-1}{\binom {n}{k}}A_{k}(t)\cdot (t-1)^{n-1-k},\quad n\geq 1.$

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

Istoric

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

$A(n,m)=(n-m)A(n-1,m-1)+(m+1)A(n-1,m).$

De exemplu

$A(4,1)=(4-1)A(3,0)+(1+1)A(3,1)=3\times 1+2\times 4=11.$

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

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ă

Formula explicită pentru A(n, m) este

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

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

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

$\sum _{m=0}^{n-1}A(n,m)=n!{\text{ for }}n\geq 1.$

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

$\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\geq 1.$

Alte proprietăți ale sumelor numerelor euleriene sunt:

$\sum _{m=0}^{n-1}(-1)^{m}{\frac {A(n,m)}{\binom {n-1}{m}}}=0{\text{ for }}n\geq 2,$

$\sum _{m=0}^{n-1}(-1)^{m}{\frac {A(n,m)}{\binom {n}{m}}}=(n+1)B_{n}{\text{ for }}n\geq 2,$

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

Identități

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

$\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}}}$

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

Identitatea lui Worpitzky exprimă xⁿ ca o combinație liniară^⁠(d) de numere euleriene cu coeficienții binomiali:

$x^{n}=\sum _{m=0}^{n-1}A(n,m){\binom {x+m}{n}}.$

Din identitatea lui Worpitzky rezultă că

$\sum _{k=1}^{N}k^{n}=\sum _{m=0}^{n-1}A(n,m){\binom {N+1+m}{n+1}}.$

Altă identitate interesantă este

${\frac {e}{1-ex}}=\sum _{n=0}^{\infty }{\frac {A_{n}(x)}{n!(1-x)^{n+1}}}.$

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

Pentru o funcție fixă $f:\mathbb {R} \rightarrow \mathbb {C}$ care este integrabilă pe $(0,n)$ există formula integrală

$\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!}}.$

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 $\scriptstyle \left\langle \!\left\langle {n \atop m}\right\rangle \!\right\rangle$, 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:

$\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 ,$

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

$\left\langle \!\!\left\langle {0 \atop m}\right\rangle \!\!\right\rangle =[m=0].$

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

$P_{n}(x)=\sum _{m=0}^{n}\left\langle \!\!\left\langle {n \atop m}\right\rangle \!\!\right\rangle x^{m}$

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

$P_{n+1}(x)=(2nx+1)P_{n}(x)-x(x-1)P_{n}^{\prime }(x)$

cu condiția inițială

$P_{0}(x)=1.$

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

$(x-1)^{-2n-2}P_{n+1}(x)=\left(x(1-x)^{-2n-1}P_{n}(x)\right)^{\prime }$

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

$u_{n}(x)=(x-1)^{-2n}P_{n}(x)$

satisface o recurență autonomă simplă:

$u_{n+1}=\left({\frac {x}{1-x}}u_{n}\right)^{\prime },\quad u_{0}=1,$

de unde se obțin polinoamele euleriene de ordinul al doilea ca P_n(x) = (1−x)²ⁿ u_n(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 P_n(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.

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. (1959). „Eulerian Numbers and polynomials”. Math. Mag. 32 (5): 247–260. doi:10.2307/3029225. JSTOR 3029225. 
• en Gould, H. W. (1978). „Evaluation of sums of convolved powers using Stirling and Eulerian Numbers”. Fib. Quart. 16 (6): 488–497. 
• en Desarmenien, Jacques; Foata, Dominique (1992). „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 (1992). „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. (1993). „Eulerian numbers with fractional order parameters”. Aequationes Mathematicae. 46 (1–2): 119–142. doi:10.1007/bf01834003. 
• en Koutras, M.V. (1994). „Eulerian numbers associated with sequences of polynomials”. Fib. Quart. 32 (1): 44. 
• en Graham; Knuth; Patashnik (1994). Concrete Mathematics: A Foundation for Computer Science (ed. 2nd). Addison-Wesley. pp. 267–272. 
• en Hsu, Leetsch C.; Jau-Shyong Shiue, Peter (1999). „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. (2007). „Apostol-Bernoulli functions, derivative polynomials and Eulerian polynomials”. arXiv:0710.1124  [math.CA]. 
• en Petersen, T. Kyle (2015). 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)