Wikipedia · einfach zusammengefasst · Stand
Euler-Zahlen
Zum Eulerschen Dreieck in der Kugelgeometrie siehe Kugeldreieck. Die nach Leonhard Euler benannte Euler-Zahl A n,k in der Kombinatorik, auch geschrieben als …
Inhalt4 Abschnitte
Bedeutung und Definition
Euler-Zahlen A_{n,k}, auch E(n,k) oder \bigl\langle {n \atop k}\bigr\rangle geschrieben, zählen in der Kombinatorik bestimmte Permutationen von 1,\ldots,n. Sie geben an, wie viele Anordnungen genau k Anstiege enthalten. Ein Anstieg liegt vor, wenn ein Element größer als das unmittelbar vorhergehende Element ist. Gleichwertig kann man Permutationen mit genau k Abstiegen zählen, wenn man „größer“ durch „kleiner“ ersetzt.
Bei einer anderen Definition bezeichnet a(n,k) die Zahl der Permutationen mit genau k maximalen monoton steigenden Abschnitten. Dann ist der zweite Parameter um eins verschoben: a(n,k)=A_{n,k-1}.
Euler-Dreieck und Rekursion
Die Euler-Zahlen lassen sich ähnlich wie Binomialkoeffizienten im Pascalschen Dreieck als Euler-Dreieck anordnen. Die erste Zeile entspricht n=1, die erste Spalte k=0. Die ersten Zeilen lauten:
- 1
- 1\quad 1
- 1\quad 4\quad 1
- 1\quad 11\quad 11\quad 1
- 1\quad 26\quad 66\quad 26\quad 1
Jeder Eintrag wird aus zwei Einträgen der vorherigen Zeile berechnet:
A_{n,k}=(n-k)A_{n-1,k-1}+(k+1)A_{n-1,k}.
Dies gilt für n>0, mit A_{0,0}=1 und A_{0,k}=0 für k\ne0.
Wichtige Eigenschaften und Formeln
Für n>0 gilt A_{n,0}=1: Es gibt genau eine Permutation ohne Anstiege. Außerdem sind die Zahlen symmetrisch:
A_{n,n-1-k}=A_{n,k}.
Die Summe aller Euler-Zahlen einer Zeile ergibt die Anzahl aller Permutationen:
\sum_{k=0}^{n}A_{n,k}=n!
für n\ge0, wobei A_{n,n}=0 gesetzt wird.
Eine direkte Berechnung aus Binomialkoeffizienten ist durch
A_{n,k}=\sum_{i=0}^{k}(-1)^i\binom{n+1}{i}(k+1-i)^n
möglich, für n,k\ge0. Daraus folgen etwa
- A_{n,1}=2^n-(n+1),
- A_{n,2}=3^n-2^n(n+1)+\tfrac12n(n+1),
- A_{n,3}=4^n-3^n(n+1)+2^n\tfrac12n(n+1)-\tfrac16(n-1)n(n+1).
Die Worpitzky-Identität lautet
\sum_{k=0}^{n}A_{n,k}\binom{x+k}{n}=x^n.
Hier ist x eine Variable und \binom{x+k}{n} ein verallgemeinerter Binomialkoeffizient. Eine erzeugende Funktion, also eine Potenzreihe, die alle A_{n,k} zusammenfasst, 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 Bernoulli-Zahlen \beta_m ist
\sum_{k=0}^{m-1}(-1)^kA_{m-1,k}=\frac{(-2)^m(2^m-1)}{m}\beta_m
für m>0.
Euler-Polynome
Das Euler-Polynom fasst die Euler-Zahlen einer Zeile als Koeffizienten zusammen:
A_n(x)=\sum_{k=0}^{n-1}A_{n,k}x^k.
Beispiele sind A_0(x)=A_1(x)=1, A_2(x)=1+x, A_3(x)=1+4x+x^2 und A_4(x)=1+11x+11x^2+x^3.
Die Rekursion der Polynome lautet
A_{n+1}(x)=(1+nx)A_n(x)+x(1-x)A_n'(x),
wobei A_n'(x) die Ableitung von A_n(x) ist. Ihre erzeugende Funktion ist
\sum_{n=0}^{\infty}A_n(x)\frac{t^n}{n!}=\frac{x-1}{x-e^{(x-1)t}}.
Euler-Polynome stehen im Zähler der geschlossenen Form von Potenzreihen:
\sum_{k=0}^{\infty}(k+1)^n x^k=\frac{A_n(x)}{(1-x)^{n+1}}
für n=0,1,2,\ldots und |x|<1. Beispielsweise ergibt sich für n=0 die geometrische Reihe \sum_{k=0}^{\infty}x^k=\frac1{1-x}; für n=2 gilt
1+4x+9x^2+16x^3+\ldots=\frac{1+x}{(1-x)^3}.