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, …, 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, …, 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):

                             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 ≥ 0.

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 ≥ 0 berechnet werden, insbesondere

• A_n,1 = 2ⁿ − (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)^[1]

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

für n ≥ 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 β_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^[2]

Das Euler-Polynom A_n(x) ist definiert durch

$A_n(x) = \sum_{k=0}^n A_{n,k}\,x^k\,,$

also

• A₀(x) = A₁(x) = 1,
• A₂(x) = 1 + x,
• A₃(x) = 1 + 4x + x²,
• A₄(x) = 1 + 11x + 11x² + x³,
• A₅(x) = 1 + 26x + 66x² + 26x³ + x⁴,
• A₆(x) = 1 + 57x + 302x² + 302x³ + 57x⁴ + x⁵,
• A₇(x) = 1 + 120x + 1191x² + 2416x³ + 1191x⁴ + 120x⁵ + x⁶.

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^\prime_n(x)$

und die erzeugende Funktion

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

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)