Eulernummer av det första slaget

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 10 juni 2020; verifiering kräver 1 redigering .

I kombinatorik är Eulernumret av det första slaget från n till k , betecknat eller , antalet permutationer av ordning n med k hissar , det vill säga sådana permutationer att det finns exakt k -index j för vilka . $\left\langle {n \atop k}\right\rangle$ $E(n,k)$ $\pi =(\pi _{1},\pi _{2},\dots ,\pi _{n})$ $\pi _{j}<\pi _{{j+1}}$

Eulertal av det första slaget har också en geometrisk och probabilistisk tolkning - talet uttrycker: ${\frac {1}{n!)}\left\langle {n \atop k}\right\rangle$

volymen av en del av en n - dimensionell hyperkub avgränsad av hyperplan och ; $x_{1}+x_{2}+\dots +x_{n}=k$ $x_{1}+x_{2}+\dots +x_{n}=k-1$
sannolikheten att summan av n oberoende variabler likformigt fördelade i intervallet ligger mellan k -1 och k . $[0,1]$

Exempel

Fjärde ordningens permutationer som har exakt två lyft måste uppfylla en av tre olikheter: , eller . Det finns exakt 11 sådana permutationer: $\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.

Därför . $\left\langle {4 \atop 2}\right\rangle =11$

Egenskaper

För ett givet naturligt tal finns det bara en permutation utan lyft, det vill säga . Det finns också en enda permutation som har n -1 lyft, dvs. På det här sättet, $n$ $(n,n-1,n-2,\prickar,1)$ $(1,2,3,\prickar,n-1,n)$

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

för alla naturliga .

n

Spegelbilden av en permutation med m lyft är en permutation med n - m -1 lyft. På det här sättet,

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

Triangel av Euler-tal av det första slaget

Betydelsen av Euler-tal för små värden på n och k ges i följande tabell (sekvens A008292 i OEIS ): $\left\langle {n \atop k}\right\rangle$

n \ k	0	ett	2	3	fyra	5	6	7	åtta	9
0	ett
ett	ett	0
2	ett	ett	0
3	ett	fyra	ett	0
fyra	ett	elva	elva	ett	0
5	ett	26	66	26	ett	0
6	ett	57	302	302	57	ett	0
7	ett	120	1191	2416	1191	120	ett	0
åtta	ett	247	4293	15619	15619	4293	247	ett	0
9	ett	502	14608	88234	156190	88234	14608	502	ett	0

Det är lätt att förstå att värdena på matrisens huvuddiagonal ges av formeln: $\left\langle {n \atop n}\right\rangle =[n=0].$

Eulers triangel, som Pascals triangel , är vänster och höger symmetrisk. Men i det här fallet är symmetrilagen något annorlunda:

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

för n > 0.

Det vill säga, en permutation har n -1- k stiger om och endast om dess "reflektion" har k stiger.

Återkommande formel

Varje permutation från mängden resulterar i permutationer från om vi infogar ett nytt element n på alla möjliga sätt. Om vi sätter in i den -e positionen får vi permutationen . Antalet höjningar i är lika med antalet höjningar i om eller om ; och det är större än antalet lyft i om eller om . Därför har den totalt sätt att konstruera permutationer från , som har lyft, plus sätt att konstruera permutationer från , som har lyft. Sedan har den önskade återkommande formeln för heltal formen: $\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)\vänster\langle {n-1 \top k}\höger\rangle$ $\rho$ $k$ $((n-2)-(k-1)+1)\vänster\langle {n-1 \atop k-1}\höger\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}\right\rangle .

Låt oss också anta det

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

(för heltal ),

k

och på : $k<0$

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

Explicita formler

Explicit formel för Euler-tal av det första slaget:

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

gör att man kan få relativt enkla uttryck för små värden på 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}.

Summeringsformler

Från den kombinatoriska definitionen är det uppenbart att summan av Euler-talen av det första slaget i den n :e raden är lika , eftersom det är lika med antalet av alla permutationer i ordningen : $n!$ $n$

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

Teckenväxlande summor av Euler-tal av det första slaget för ett fast värde på n är relaterade till Bernoulli-tal : $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.

Följande identiteter är också giltiga, som förbinder Euler-nummer av det första slaget med Stirling-nummer av det andra slaget :

\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 =\summa _{{k=1}}^{{\infty } }{\frac {k^{n}}{2^{k}}}=\summa _{{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}}\summa _{{k= 1}}^{{\infty }}{\frac {k^{n}}{3^{k}}}

Genererande funktion

Den genererande funktionen för Euler-tal av det första slaget har formen:

{\frac {1-w}{e^{{{(w-1)z}}-w}}=\summa _{{m,n\geq 0}}\left\langle {n \top m} \ höger\rangle w^{m}{\frac {z^{n}}{n!)}}

Eulertalen av det första slaget är också relaterade till genereringsfunktionen för sekvensen av -te potenser ( polylogaritmen av en heltals negativ ordning): $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}}}}.

Dessutom Z-transformen från

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

är generatorn av de första N raderna av triangelns Euler-tal när nämnaren för det e elementet i transformationen annulleras genom att multiplicera med : $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}}}\right\}\right]

Vorpitsky-identiteten

Vorpitsky-identiteten uttrycker en maktfunktion som summan av produkter av Eulertal av det första slaget och generaliserade binomialkoefficienter :

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

Särskilt:

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}

och så vidare. Dessa identiteter kan lätt bevisas genom induktion .

Vorpitsky-identiteten ger ett annat sätt att beräkna summan av de första kvadraterna: $n$

\sum _{{k=1}}^{n}k^{2}=\summa _{{k=1}}^{n}\left\langle {2 \atop 0}\right\rangle {k \choose 2}+\left\langle {2 \atop 1}\right\rangle {k+1 \choose 2}=\summa _{{k=1}}^{n}{k \choose 2}+{ k+1 \välj 2}=

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

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

Litteratur

Donald Knuth , Ronald Graham , Oren Patashnik . Eulertal // Konkret matematik. Grunden för datavetenskap = konkret matematik. En stiftelse för datavetenskap. — M .: Mir ; Binom. Knowledge Lab , 2006. - S. 703. - ISBN 5-94774-560-7 .
D. Knut. Grundläggande algoritmer // Konsten att programmera . - M . : Williams, 2006. - T. 1.
Weisstein, Eric W. Eulerian Number (engelska) på Wolfram MathWorld- webbplatsen .
Weisstein, Eric W. Worpitzkys identitet (engelska) på Wolfram MathWorld- webbplatsen .
Euleriska tal . MathPages.