Numerele Euler de primul fel

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 10 iunie 2020; verificarea necesită 1 editare .

În combinatorică , numărul Euler de primul fel de la n la k , notat sau , este numărul de permutări de ordin n cu k ridicări , adică astfel de permutări încât există exact k indici j pentru care . $\left\langle {n \atop k}\right\rangle$ $E(n,k)$ $\pi =(\pi _{1},\pi _{2},\dots ,\pi _{n})$ $\pi _{j}<\pi _{{j+1}}$

Numerele Euler de primul fel au și o interpretare geometrică și probabilistă - numărul exprimă: ${\frac {1}{n!)}\left\langle {n \atop k}\right\rangle$

volumul unei părți dintr -un hipercub n - dimensional delimitat de hiperplanuri și ; $x_{1}+x_{2}+\dots +x_{n}=k$ $x_{1}+x_{2}+\dots +x_{n}=k-1$
probabilitatea ca suma n variabile independente distribuite uniform în interval se situează între k -1 și k . $[0,1]$

Exemplu

Permutările de ordinul al patrulea care au exact două ridicări trebuie să satisfacă una dintre cele trei inegalități: , sau . Există exact 11 astfel de permutări: $\pi$ $\pi _{1}<\pi _{2}>\pi _{3}<\pi _{4}$ $\pi _{1}<\pi _{2}<\pi _{3}>\pi _{4}$ $\pi _{1}>\pi _{2}<\pi _{3}<\pi _{4}$

1324, 1423, 2314, 2413, 3412, 1243, 1342, 2341, 2134, 3124, 4123.

Prin urmare . $\left\langle {4 \atop 2}\right\rangle =11$

Proprietăți

Pentru un număr natural dat, există o singură permutare fără ridicări, adică . Există, de asemenea, o singură permutare care are n -1 ridicări, adică . În acest fel, $n$ $(n,n-1,n-2,\puncte,1)$ $(1,2,3,\puncte ,n-1,n)$

\left\langle {n \atop 0}\right\rangle =\left\langle {n \atop n-1}\right\rangle =1

pentru toate naturale .

n

Imaginea în oglindă a unei permutări cu m ridicări este o permutare cu n - m -1 ridicări. În acest fel,

\left\langle {n \atop m}\right\rangle =\left\langle {n \atop nm-1}\right\rangle .

Triunghiul numerelor Euler de primul fel

Semnificația numerelor Euler pentru valorile mici ale lui n și k este dată în următorul tabel (secvența A008292 în OEIS ): $\left\langle {n \atop k}\right\rangle$

n \ k	0	unu	2	3	patru	5	6	7	opt	9
0	unu
unu	unu	0
2	unu	unu	0
3	unu	patru	unu	0
patru	unu	unsprezece	unsprezece	unu	0
5	unu	26	66	26	unu	0
6	unu	57	302	302	57	unu	0
7	unu	120	1191	2416	1191	120	unu	0
opt	unu	247	4293	15619	15619	4293	247	unu	0
9	unu	502	14608	88234	156190	88234	14608	502	unu	0

Este ușor de înțeles că valorile de pe diagonala principală a matricei sunt date de formula: $\left\langle {n \atop n}\right\rangle =[n=0].$

Triunghiul lui Euler, ca și triunghiul lui Pascal , este simetric la stânga și la dreapta. Dar în acest caz, legea simetriei este oarecum diferită:

\left\langle {n \atop k}\right\rangle =\left\langle {n \atop n-1-k}\right\rangle

pentru n > 0.

Adică, o permutare are n -1- k crește dacă și numai dacă „reflexia” ei are k crește.

Formula recurentă

Fiecare permutare din mulțime are ca rezultat permutări de la dacă inserăm un nou element n în toate modurile posibile. Inserând în poziţia -a, obţinem permutarea . Numărul de creșteri în este egal cu numărul de creșteri în dacă sau dacă ; și este mai mare decât numărul de ridicări în if sau if . Prin urmare, în total are modalități de a construi permutări din , care au lifting, plus modalități de a construi permutări din , care au lifting. Apoi formula recurentă dorită pentru numere întregi are forma: $\rho =\rho _{1}\dots \rho _{{n-1}}$ $\{1,2,3,n-1\}$ $n$ $\{1,2,3,n\}$ $n$ $j$ $\pi =\rho _{1}\dots \rho _{{j-1}}n\rho _{j}\dots \rho _{{n-1}}$ $\pi$ $\rho$ $j=1$ $\pi _{{j-1}}<\pi _{j}$ $\rho$ $j=n$ $\rho _{{j-1}}>\rho _{j}$ $\pi$ $(k+1)\left\langle {n-1 \atop k}\right\rangle$ $\rho$ $k$ $((n-2)-(k-1)+1)\left\langle {n-1 \atop k-1}\right\rangle$ $\rho$ $k-1$ $n>0$

\left\langle {n \atop k}\right\rangle =(k+1)\left\langle {n-1 \atop k}\right\rangle +(nk)\left\langle {n-1 \atop k-1}\dreapta\rangle .

Să presupunem și noi că

\left\langle {0 \atop k}\right\rangle =[k=0]

(pentru numere întregi ),

k

si la : $k<0$

\left\langle {n \atop k}\right\rangle =0.

Formule explicite

Formula explicită pentru numerele Euler de primul fel:

\left\langle {n \atop m}\right\rangle =\sum _{{k=0}}^{{m}}{n+1 \choose k}(m+1-k)^{n} (-1)^{k}

permite obținerea de expresii relativ simple pentru valori mici ale lui m :

\left\langle {n \atop 0}\right\rangle =1;

\left\langle {n \atop 1}\right\rangle =2^{n}-n-1;

\left\langle {n \atop 2}\right\rangle =3^{n}-(n+1)2^{n}+{n+1 \choose 2}.

Formule de însumare

Din definiția combinatorie, este evident că suma numerelor Euler de primul fel situate în al n -lea rând este egală , deoarece este egală cu numărul tuturor permutărilor de ordin : $n!$ $n$

\sum _{{m=0}}^{n}\left\langle {n \atop m}\right\rangle =n!

Sumele alternate de semne ale numerelor Euler de primul fel pentru o valoare fixă a lui n sunt legate de numerele Bernoulli : $B_{{n+1}}$

\sum _{{m=0}}^{n}(-1)^{m}\left\langle {n \atop m}\right\rangle ={\frac {2^{{n+1}} (2^{{n+1}}-1)B_{{n+1}}}{n+1}},

\sum _{{m=0}}^{n}(-1)^{m}\left\langle {n \atop m}\right\rangle {n \choose m}^{{-1}}= (n+1)B_{n},

\sum _{{m=0}}^{n}(-1)^{m}\left\langle {n \atop m}\right\rangle {n-1 \choose m}^{{-1} }=0.

Următoarele identități sunt, de asemenea, valide, conectând numerele Euler de primul fel cu numerele Stirling de al doilea fel :

\sum _{{k=nm}}^{n}\left\langle {n \atop k}\right\rangle {k \choose nm}=m!\left\{{n \atop m}\right\ }

\sum _{{k=0}}^{n}2^{k}\left\langle {n \atop k}\right\rangle =\sum _{{k=1}}^{{\infty } }{\frac {k^{n}}{2^{k}}}=\sum _{{k=1}}^{{n}}k!\left\{{n \atop k}\right \}

\sum _{{k=0}}^{n}3^{k}\left\langle {n \atop k}\right\rangle =2^{{n+1}}\sum _{{k= 1}}^{{\infty }}{\frac {k^{n}}{3^{k}}}

Funcție de generare

Funcția generatoare a numerelor Euler de primul fel are forma:

{\frac {1-w}{e^{{{(w-1)z}}-w}}=\sum _{{m,n\geq 0}}\left\langle {n \atop m} \ dreapta\rangle w^{m}{\frac {z^{n}}{n!)}}

Numerele Euler de primul fel sunt, de asemenea, legate de funcția generatoare a secvenței de -lea puteri ( polilogaritmul unui ordin negativ întreg): $n$

\sum _{{k=1}}^{{\infty }}k^{n}x^{k}={\frac {\sum _{{m=0}}^{{n-1}} \left\langle {n \atop m}\right\rangle x^{{m+1}}}{(1-x)^{{n+1}}}}.

În plus, transformarea Z din

\left\{n^{k}\right\}_{{k=1}}^{N}

este generatorul primelor N rânduri de numere triunghiulare Euler când numitorul celui de-al-lea element al transformării este anulat prin înmulțirea cu : $n$ $(z-1)^{{j+1}}$

Z\left[\{n^{k}\}_{{k=1}}^{3}=\left\{{\frac {z}{(z-1)^{2}}},{ \frac {z+z^{2}}{(z-1)^{3}}},{\frac {z+4z^{2}+z^{3}}{(z-1)^{ 4}}}\dreapta\}\dreapta]

Identitatea Vorpitsky

Identitatea Vorpitsky exprimă o funcție de putere ca suma produselor numerelor Euler de primul fel și a coeficienților binomi generalizați :

x^{n}=\sum _{{m=0}}^{{n-1}}\left\langle {n \atop m}\right\rangle {x+m \choose n}.

În special:

x^{2}={x \choose 2}+{x+1 \choose 2}

x^{3}={x \choose 3}+4{x+1 \choose 3}+{x+2 \choose 3}

x^{4}={x \choose 4}+11{x+1 \choose 4}+11{x+2 \choose 4}+{x+3 \choose 4}

și așa mai departe.Aceste identități sunt ușor dovedite prin inducție .

Identitatea Vorpitsky oferă o altă modalitate de a calcula suma primelor pătrate: $n$

\sum _{{k=1}}^{n}k^{2}=\sum _{{k=1}}^{n}\left\langle {2 \atop 0}\right\rangle {k \choose 2}+\left\langle {2 \atop 1}\right\rangle {k+1 \choose 2}=\sum _{{k=1}}^{n}{k \choose 2}+{ k+1 \alege 2}=

=\left({1 \choose 2}+{2 \choose 2}+\dots +{n \choose 2}\right)+\left({2 \choose 2}+{3 \choose 2}+\dots +{n+1 \alegeți 2}\right)=

={n+1 \choose 3}+{n+2 \choose 3}={\frac {n(n+1)(2n+1)}{6}}.

Literatură

Donald Knuth , Ronald Graham , Oren Patashnik . Numerele Euler // Matematică concretă. Foundation of Computer Science = Concrete Mathematics. O fundație pentru informatică. — M .: Mir ; Binom. Knowledge Lab , 2006. - P. 703. - ISBN 5-94774-560-7 .
D. Knut. Algoritmi de bază // Arta programarii . - M . : Williams, 2006. - T. 1.
Weisstein, Eric W. Eulerian Number (engleză) pe site-ul web Wolfram MathWorld .
Weisstein, Eric W. Worpitzky's Identity (engleză) pe site-ul Wolfram MathWorld .
Numerele euleriene . MathPages.