Eulerova čísla prvního druhu

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 10. června 2020; ověření vyžaduje 1 úpravu .

V kombinatorice je Eulerovo číslo prvního druhu od n do k , označované nebo , je počet permutací řádu n s k výtahy , tedy takových permutací , že existuje právě k indexů j , pro které . $\left\langle {n \atop k}\right\rangle$ $E(n,k)$ $\pi =(\pi _{1},\pi _{2},\tečky ,\pi _{n})$ $\pi _{j}<\pi _{{j+1}}$

Eulerova čísla prvního druhu mají také geometrickou a pravděpodobnostní interpretaci - číslo vyjadřuje: ${\frac {1}{n!)}\left\langle {n \atop k}\right\rangle$

objem části n - rozměrné hyperkrychle ohraničené nadrovinami a ; $x_{1}+x_{2}+\tečky +x_{n}=k$ $x_{1}+x_{2}+\tečky +x_{n}=k-1$
pravděpodobnost , že součet n nezávislých proměnných rovnoměrně rozložených v segmentu leží mezi k -1 a k . $[0,1]$

Příklad

Permutace čtvrtého řádu , které mají přesně dva zdvihy, musí splňovat jednu ze tří nerovností: , nebo . Existuje přesně 11 takových permutací: $\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.

Proto . $\left\langle {4 \nahoře 2}\right\rangle =11$

Vlastnosti

Pro dané přirozené číslo existuje pouze jedna permutace bez výtahů, tedy . Existuje také jedna permutace, která má n -1 zdvihů, tj . Takto, $n$ $(n,n-1,n-2,\tečky,1)$ $(1,2,3,\tečky ,n-1,n)$

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

pro všechny přirozené .

n

Zrcadlovým obrazem permutace s m zdvihy je permutace s n - m -1 zdvihů. Takto,

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

Trojúhelník Eulerových čísel prvního druhu

Význam Eulerových čísel pro malé hodnoty n a k je uveden v následující tabulce (sekvence A008292 v OEIS ): $\left\langle {n \atop k}\right\rangle$

n \ k	0	jeden	2	3	čtyři	5	6	7	osm	9
0	jeden
jeden	jeden	0
2	jeden	jeden	0
3	jeden	čtyři	jeden	0
čtyři	jeden	jedenáct	jedenáct	jeden	0
5	jeden	26	66	26	jeden	0
6	jeden	57	302	302	57	jeden	0
7	jeden	120	1191	2416	1191	120	jeden	0
osm	jeden	247	4293	15619	15619	4293	247	jeden	0
9	jeden	502	14608	88234	156190	88234	14608	502	jeden	0

Je snadné pochopit, že hodnoty na hlavní diagonále matice jsou dány vzorcem: $\left\langle {n \nahoře n}\right\rangle =[n=0].$

Eulerův trojúhelník, stejně jako Pascalův trojúhelník , je symetrický vlevo a vpravo. Ale v tomto případě je zákon symetrie poněkud odlišný:

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

pro n > 0.

To znamená, že permutace má n -1- k vzestupů právě tehdy, když její "odraz" má k vzestupy.

Opakovaný vzorec

Každá permutace z množiny má za následek permutace z pokud vložíme nový prvek n všemi možnými způsoby. Vložením na -tou pozici získáme permutaci . Počet nárůstů v se rovná počtu nárůstů v if nebo if ; a je větší než počet výtahů v if nebo if . Celkově tedy má způsoby, jak konstruovat permutace z , které mají výtahy, plus způsoby, jak konstruovat permutace z , které mají výtahy. Potom má požadovaný opakující se vzorec pro celá čísla tvar: $\rho =\rho _{1}\tečky \rho _{{n-1}}$ $\{1,2,3,n-1\}$ $n$ $\{1,2,3,n\}$ $n$ $j$ $\pi =\rho _{1}\tečky \rho _{{j-1}}n\rho _{j}\tečky \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 \nahoře k}\vpravo\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}\pravý\úhelník .

Předpokládejme to také

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

(pro celá čísla ),

k

a na : $k<0$

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

Explicitní vzorce

Explicitní vzorec pro Eulerova čísla prvního druhu:

\left\langle {n \nahoře m}\right\rangle =\součet _{{k=0}}^{{m}}{n+1 \choose k}(m+1-k)^{n} (-1)^{k}

umožňuje získat relativně jednoduché výrazy pro malé hodnoty 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 \vyberte 2}.

Sumační vzorce

Z kombinatorické definice je zřejmé, že součet Eulerových čísel prvního druhu umístěných v n-té řadě je roven , protože se rovná počtu všech permutací řádu : $n$ $n$

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

Znaménko se střídající součty Eulerových čísel prvního druhu pro pevnou hodnotu n souvisí s Bernoulliho čísly : $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 \nahoře m}\right\rangle {n \choose m}^{{-1}}= (n+1)B_{n},

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

Následující identity jsou také platné, spojují Eulerova čísla prvního druhu se Stirlingovými čísly druhého druhu :

\sum _{{k=nm}}^{n}\left\langle {n \nahoře k}\right\rangle {k \vyberte nm}=m!\left\{{n \nahoře m}\vpravo\ }

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

Generující funkce

Generující funkce Eulerových čísel prvního druhu má tvar:

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

Eulerova čísla prvního druhu také souvisí s generující funkcí posloupnosti -tých mocnin ( polylogaritmus celočíselného záporného řádu): $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}}}}.

Navíc Z-transformace z

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

je generátorem prvních N řádků Eulerových čísel trojúhelníku, když je jmenovatel tého prvku transformace zrušen násobením : $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}}}\vpravo\}\vpravo]

Identita Vorpitského

Vorpitského identita vyjadřuje mocninnou funkci jako součet součinů Eulerových čísel prvního druhu a zobecněných binomických koeficientů :

x^{n}=\součet _{{m=0}}^{{n-1}}\left\langle {n \atop m}\right\rangle {x+m \vyberte n}.

Zejména:

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

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

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

atd. Tyto identity lze snadno dokázat indukcí .

Vorpitského identita poskytuje další způsob, jak vypočítat součet prvních čtverců: $n$

\sum _{{k=1}}^{n}k^{2}=\součet _{{k=1}}^{n}\left\langle {2 \nahoře 0}\right\rangle {k \vyberte 2}+\vlevo\langle {2 \nahoře 1}\vpravo\rangle {k+1 \vyberte 2}=\součet _{{k=1}}^{n}{k \vyberte 2}+{ k+1 \vyberte 2}=

=\left({1 \vyberte 2}+{2 \vyberte 2}+\tečky +{n \vyberte 2}\vpravo)+\left({2 \vyberte 2}+{3 \vyberte 2}+\tečky +{n+1 \vyberte 2}\vpravo)=

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

Literatura

Donald Knuth , Ronald Graham , Oren Patashnik . Eulerova čísla // Konkrétní matematika. Základ informatiky = konkrétní matematika. Nadace pro informatiku. — M .: Mir ; Binomický. Knowledge Lab , 2006. - S. 703. - ISBN 5-94774-560-7 .
D. Knut. Základní algoritmy // Umění programování . - M .: Williams, 2006. - T. 1.
Weisstein, Eric W. Eulerian Number (anglicky) na webových stránkách Wolfram MathWorld .
Weisstein, Eric W. Worpitzky's Identity (anglicky) na webových stránkách Wolfram MathWorld .
Eulerovská čísla . MathPages.