Euler-Zahlen

Die nach Leonhard Euler benannte Euler-Zahl A_n,k in der Kombinatorik, auch geschrieben als ${\displaystyle E(n,k)}$ oder ${\displaystyle \textstyle {\bigl \langle }\!{n \atop k}\!{\bigr \rangle }}$, ist die Anzahl der Permutationen (Anordnungen) von ${\displaystyle 1,\ldots ,n}$, in denen genau ${\displaystyle k}$ Elemente größer als das vorhergehende sind, die also genau ${\displaystyle 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 ${\displaystyle a(n,k)}$ die Anzahl der Permutationen von ${\displaystyle 1,\ldots ,n}$ mit genau ${\displaystyle k}$ maximalen monoton ansteigenden Abschnitten, wodurch der zweite Parameter gegenüber der hier verwendeten Definition um eins verschoben ist: ${\displaystyle 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 ${\displaystyle n=1}$, erste Spalte ${\displaystyle k=0}$; Folge A008292 in OEIS):

                             1
                          1     1
                       1     4     1
                    1    11    11     1
                 1    26    66    26     1
              1    57    302   302   57     1
           1    120  1191  2416  1191   120    1
        1    247  4293  15619 15619 4293   247    1
     1    502  14608 88234 156190 88234 14608 502    1
  1    ...   ...   ...   ...   ...   ...   ...   ...    1

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

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

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

Eigenschaften

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

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

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

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

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

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

• ${\displaystyle A_{n,1}=2^{n}-(n+1),}$ Folge A000295 in OEIS,
• ${\displaystyle A_{n,2}=3^{n}-2^{n}\,(n+1)+{\tfrac {1}{2}}\,n\,(n+1),}$ Folge A000460 in OEIS und
• ${\displaystyle 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)^[1]

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

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

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

${\displaystyle \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 ${\displaystyle \beta _{m}}$ wird durch die alternierende Summe

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

für ${\displaystyle m>0}$ hergestellt.

Euler-Polynome

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

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

also

• ${\displaystyle A_{0}(x)=A_{1}(x)=1,}$
• ${\displaystyle A_{2}(x)=1+x,}$
• ${\displaystyle A_{3}(x)=1+4x+x^{2},}$
• ${\displaystyle A_{4}(x)=1+11x+11x^{2}+x^{3},}$
• ${\displaystyle A_{5}(x)=1+26x+66x^{2}+26x^{3}+x^{4},}$
• ${\displaystyle A_{6}(x)=1+57x+302x^{2}+302x^{3}+57x^{4}+x^{5},}$
• ${\displaystyle 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

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

und die erzeugende Funktion

${\displaystyle \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:

${\displaystyle \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 ${\displaystyle n=0,\,1,\,2,\ldots }$ und ${\displaystyle |x|<1}$.

Spezialfälle:

${\displaystyle 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),

${\displaystyle 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}}}}$,

${\displaystyle 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.

Literatur

• L. Euler: Remarques sur un beau rapport entre les séries des puissances tant directes que réciproques (1749), Mémoires de l’académie royale des sciences et belles-lettres 17, 1768, S. 83–106 (französisch; Euler-Zahlen als Koeffizienten auf S. 85)
• David P. Roselle: Permutations by number of rises and successions, Proceedings of the AMS 19, 1968, S. 8–16 (englisch)
• Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Concrete mathematics: a foundation for computer science, Addison-Wesley, Reading 1988, 2. Auflage 1994, ISBN 0-201-55802-5, S. 267–272 (englisch; Knuths Webseite zum Buch mit Errata: Concrete Mathematics, Second Edition)
• Kenneth H. Rosen, John G. Michaels et al. (Hrsg.): Handbook of Discrete and Combinatorial Mathematics, CRC Press LLC, 1999, ISBN 0-8493-0149-1 (englisch)
• Friedrich Hirzebruch: Eulerian polynomials (PDF-Datei, 96 kB), Münster Journal of Mathematics 1, 2008, S. 9–14 (englisch)

Weblinks

• Eric W. Weisstein: Eulerian Number, Euler’s Number Triangle und Worpitzky’s Identity in MathWorld (englisch)
• Permutations: Order Notation in der NIST Digital Library of Mathematical Functions (englisch)
• Eulerian polynomials von Peter Luschny, 18. August 2010 (englisch)

Einzelnachweise

1. ↑ Julius Worpitzky: Studien über die Bernoullischen und Eulerschen Zahlen, Journal für die reine und angewandte Mathematik 94, 1883, S. 203–232
2. ↑ Leonhard Euler: Institutiones calculi differentialis Teil 2, Academia imperialis scientiarum Petropolitanae, 1755, S. 485–486 (lateinisch)