Euler-Zahlen
# Euler-Zahlen

Die nach Leonhard Euler benannte Euler-Zahl $A_{n,k}$ in der Kombinatorik, auch geschrieben als $E(n,k)$ oder $\textstyle {\bigl \langle }\!{n \atop k}\!{\bigr \rangle }$, ist die Anzahl der Permutationen (Anordnungen) von $1,\ldots ,n$, in denen genau $k$ Elemente größer als das vorhergehende sind, die also genau $k$ Anstiege enthalten. Äquivalent dazu ist die Definition mit „kleiner“ statt „größer“ und „Abstiege“ statt „Anstiege“. Nach einer anderen Definition ist die Euler-Zahl $a(n,k)$ die Anzahl der Permutationen von $1,\ldots ,n$ mit genau $k$ maximalen monoton ansteigenden Abschnitten, wodurch der zweite Parameter gegenüber der hier verwendeten Definition um eins verschoben ist: $a(n,k)=A_{n,k-1}$.

## Euler-Dreieck

Wie die Binomialkoeffizienten im Pascalschen Dreieck können die Euler-Zahlen im Euler-Dreieck angeordnet werden (erste Zeile $n=1$, erste Spalte $k=0$; Folge A008292 in OEIS):

Dabei kann man mit der folgenden Rekursionsformel jeden Eintrag aus den beiden darüberstehenden berechnen:

    $A_{n,k}=(n-k)\,A_{n-1,k-1}+(k+1)\,A_{n-1,k}$

für $n>0$ mit $A_{0,0}=1$ und $A_{0,k}=0$ für $k\not =0$. Auch die Konvention $A_{0,-1}=1$ und $A_{0,k}=0$ für $k\not =-1$ wäre sinnvoll, sie ist bei der alternativen Definition üblich.

## Eigenschaften

Direkt aus der Definition folgen $A_{n,0}=1$ und $A_{n,n-1-k}=A_{n,k}$ für $n>0$ und

    $\sum _{k=0}^{n}A_{n,k}=n!$

für $n\geq 0$, wobei $A_{n,n}=0$ gesetzt wird.

Aus den Binomialkoeffizienten können die Euler-Zahlen mit der Formel

    $A_{n,k}=\sum _{i=0}^{k}\,(-1)^{i}{\binom {n+1}{i}}(k+1-i)^{n}$

für $n,k\geq 0$ berechnet werden, insbesondere

* $A_{n,1}=2^{n}-(n+1),$ Folge A000295 in OEIS,
* $A_{n,2}=3^{n}-2^{n}\,(n+1)+{\tfrac {1}{2}}\,n\,(n+1),$ Folge A000460 in OEIS und
* $A_{n,3}=4^{n}-3^{n}\,(n+1)+2^{n}\,{\tfrac {1}{2}}\,n\,(n+1)-{\tfrac {1}{6}}\,(n-1)\,n\,(n+1),$ Folge A000498 in OEIS.

Es gilt die Worpitzky-Identität (Worpitzky 1883)

    $\sum _{k=0}^{n}A_{n,k}\,{\binom {x+k}{n}}=x^{n}$

für $n\geq 0$, wobei $x$ eine Variable und ${\tbinom {x+k}{n}}$ ein verallgemeinerter Binomialkoeffizient ist.

Eine erzeugende Funktion für $A_{n,k}$ ist

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

Eine Beziehung zu den Bernoulli-Zahlen $\beta _{m}$ wird durch die alternierende Summe

    $\sum _{k=0}^{m-1}(-1)^{k}A_{m-1,k}={\frac {(-2)^{m}\,(2^{m}-1)}{m}}\,\beta _{m}$

für $m>0$ hergestellt.

## Euler-Polynome

Das Euler-Polynom $A_{n}(x)$ ist definiert durch

    $A_{n}(x)=\sum _{k=0}^{n-1}A_{n,k}\,x^{k}\,,$

also

* $A_{0}(x)=A_{1}(x)=1,$
* $A_{2}(x)=1+x,$
* $A_{3}(x)=1+4x+x^{2},$
* $A_{4}(x)=1+11x+11x^{2}+x^{3},$
* $A_{5}(x)=1+26x+66x^{2}+26x^{3}+x^{4},$
* $A_{6}(x)=1+57x+302x^{2}+302x^{3}+57x^{4}+x^{5},$
* $A_{7}(x)=1+120x+1191x^{2}+2416x^{3}+1191x^{4}+120x^{5}+x^{6}.$

Aus den entsprechenden Gleichungen für die Euler-Zahlen erhält man die Rekursionsformel

    $A_{n+1}(x)=(1+n\,x)\,A_{n}(x)+x\,(1-x)\,A_{n}^{\prime }(x)$

und die erzeugende Funktion

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

Die Euler-Polynome kommen im Zähler der geschlossenen Darstellung gewisser Potenzreihen vor:

$\sum _{k=0}^{\infty }(k+1)^{n}x^{k}=1^{n}+2^{n}x+3^{n}x^{2}+4^{n}x^{3}+\ldots ={\frac {A_{n}(x)}{(1-x)^{n+1}}}$ für $n=0,\,1,\,2,\ldots$ und $|x|<1$.

Spezialfälle:

$n=0:\sum _{k=0}^{\infty }x^{k}=1+x+x^{2}+x^{3}+\ldots ={\frac {A_{0}(x)}{1-x}}={\frac {1}{1-x}}$ (geometrische Reihe),

$n=1:\sum _{k=0}^{\infty }(k+1)x^{k}=1+2x+3x^{2}+4x^{3}+\ldots ={\frac {A_{1}(x)}{(1-x)^{2}}}={\frac {1}{(1-x)^{2}}}$,

$n=2:\sum _{k=0}^{\infty }(k+1)^{2}x^{k}=1+4x+9x^{2}+16x^{3}+\ldots ={\frac {A_{2}(x)}{(1-x)^{3}}}={\frac {1+x}{(1-x)^{3}}}$

usw.

