Număr eulerian

Format:Distinge Î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:

$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}^{\mathrm{\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^{\prime }-1}(t)+A_{n-1}(t)\cdot (1+(n-1)t),n\ge 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}(\genfrac{}{}{0ex}{}{n}{k})A_k(t)\cdot (t-1{)}^{n-1-k},n\ge 1.$

Alte notații pentru A(n, m) sunt E(n, m) și $⟨\genfrac{}{}{0ex}{}{n}{m}⟩$.

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 Format:Math, Format:Math, Format:Math 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:

Format:Separator diagonal	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(\genfrac{}{}{0ex}{}{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\ge 1.$

Suma alternantă a numerelor euleriene pentru o valoare fixă a lui n este legată de Format:Ill-wd 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\ge 1.$

Alte proprietăți ale sumelor numerelor euleriene sunt:

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

$\sum _{m=0}^{n-1}(-1{)}^m\frac{A(n,m)}{(\genfrac{}{}{0ex}{}{n}{m})}=(n+1)B_n\text{ for }n\ge 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}^{\mathrm{\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\ge 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 Format:Ill-wd de numere euleriene cu coeficienții binomiali:

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

Din identitatea lui Worpitzky rezultă că

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

Altă identitate interesantă este

$\frac{e}{1-ex}=\sum _{n=0}^{\mathrm{\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:ℝ\to ℂ$ care este integrabilă pe $(0,n)$ există formula integrală

$\underset{0}{\overset{1}{\int }}\cdots \underset{0}{\overset{1}{\int }}f\left(\lfloor x_1+\cdots +x_n\rfloor \right)d{x}_1\cdots d{x}_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 Format:Ill-wd (2n−1)!!. Numărul eulerian de ordinul al doilea, notat $⟨⟨\genfrac{}{}{0ex}{}{n}{m}⟩⟩$, 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:

$⟨⟨\genfrac{}{}{0ex}{}{n}{m}⟩⟩=(2n-m-1)⟨⟨\genfrac{}{}{0ex}{}{n-1}{m-1}⟩⟩+(m+1)⟨⟨\genfrac{}{}{0ex}{}{n-1}{m}⟩⟩,$

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

$⟨⟨\genfrac{}{}{0ex}{}{0}{m}⟩⟩=[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⟨⟨\genfrac{}{}{0ex}{}{n}{m}⟩⟩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)={(x(1-x{)}^{-2n-1}{P}_n(x))}^{\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 },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:

Format:Separator diagonal	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

• Format: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.
• Format:En icon Format:Cite journal
• Format:En icon Format:Cite journal
• Format:En icon Format:Cite journal
• Format:En icon Format:Cite journal
• Format:En icon Format:Cite journal
• Format:En icon Format:Cite journal
• Format:En icon Format:Cite book
• Format:En icon Format:Cite journal
• Format:En icon Format:Cite arXiv
• Format:En icon Format:Cite book

Legături externe

• Format:En icon Eulerian Polynomials at OEIS Wiki.
• Format:En icon Format:MathWorld
• Format:En icon Format:MathWorld
• Format:En icon Format:MathWorld
• Format:En icon Format:MathWorld
• Format:En icon Euler-matrix (generalized rowindexes, divergent summation)