Euler-Zahlen

Die nach Leonhard Euler benannte Euler-Zahl A_n,k in der Kombinatorik, auch geschrieben als $E(n,k)$ oder $⟨\genfrac{}{}{0ex}{}{n}{k}⟩$, ist die Anzahl der Permutationen (Anordnungen) von $1,\dots ,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,\dots ,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$; Vorlage: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:

$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=0$. Auch die Konvention $A_{0,-1}=1$ und $A_{0,k}=0$ für $k=-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\ge 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(\genfrac{}{}{0ex}{}{n+1}{i})(k+1-i{)}^n$

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

• $A_{n,1}=2^n-(n+1),$ Vorlage:OEIS,
• $A_{n,2}=3^n-2^n(n+1)+\frac{1}{2}n(n+1),$ Vorlage:OEIS und
• $A_{n,3}=4^n-3^n(n+1)+2^n\frac{1}{2}n(n+1)-\frac{1}{6}(n-1)n(n+1),$ Vorlage:OEIS.

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

$\sum _{k=0}^n{A}_{n,k}(\genfrac{}{}{0ex}{}{x+k}{n})=x^n$

für $n\ge 0$, wobei $x$ eine Variable und $(\genfrac{}{}{0ex}{}{x+k}{n})$ ein verallgemeinerter Binomialkoeffizient ist.

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

$\sum _{n=0}^{\mathrm{\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

Euler-Zahlen als Koeffizienten von Euler-Polynomen

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+nx)A_n(x)+x(1-x)A_n^{\prime }(x)$

und die erzeugende Funktion

$\sum _{n=0}^{\mathrm{\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}^{\mathrm{\infty }}(k+1{)}^n{x}^k=1^n+2^{n}x+3^n{x}^2+4^n{x}^3+\dots =\frac{A_n(x)}{(1-x{)}^{n+1}}$ für $n=0,1,2,\dots$ und $|x|<1$.

Spezialfälle:

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

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

$n=2:\sum _{k=0}^{\mathrm{\infty }}(k+1{)}^2{x}^k=1+4x+9x^2+16x^3+\dots =\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)