Dieser Artikel behandelt die ganzen Zahlen des Euler-Dreiecks.
Die nach Leonhard Euler benannte Euler-Zahl An,k in der Kombinatorik, auch geschrieben als E ( n , k ) {\displaystyle E(n,k)} oder ⟨ n k ⟩ {\displaystyle \textstyle {\bigl \langle }\!{n \atop k}\!{\bigr \rangle }} , ist die Anzahl der Permutationen (Anordnungen) von 1 , … , n {\displaystyle 1,\ldots ,n} , in denen genau k {\displaystyle k} Elemente größer als das vorhergehende sind, die also genau k {\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 a ( n , k ) {\displaystyle a(n,k)} die Anzahl der Permutationen von 1 , … , n {\displaystyle 1,\ldots ,n} mit genau k {\displaystyle 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 {\displaystyle a(n,k)=A_{n,k-1}} .
Wie die Binomialkoeffizienten im Pascalschen Dreieck können die Euler-Zahlen im Euler-Dreieck angeordnet werden (erste Zeile n = 1 {\displaystyle n=1} , erste Spalte k = 0 {\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:
A n , k = ( n − k ) A n − 1 , k − 1 + ( k + 1 ) A n − 1 , k {\displaystyle A_{n,k}=(n-k)\,A_{n-1,k-1}+(k+1)\,A_{n-1,k}} für n > 0 {\displaystyle n>0} mit A 0 , 0 = 1 {\displaystyle A_{0,0}=1} und A 0 , k = 0 {\displaystyle A_{0,k}=0} für k ≠ 0 {\displaystyle k\not =0} . Auch die Konvention A 0 , − 1 = 1 {\displaystyle A_{0,-1}=1} und A 0 , k = 0 {\displaystyle A_{0,k}=0} für k ≠ − 1 {\displaystyle k\not =-1} wäre sinnvoll, sie ist bei der alternativen Definition üblich.
Direkt aus der Definition folgen A n , 0 = 1 {\displaystyle A_{n,0}=1} und A n , n − 1 − k = A n , k {\displaystyle A_{n,n-1-k}=A_{n,k}} für n > 0 {\displaystyle n>0} und
∑ k = 0 n A n , k = n ! {\displaystyle \sum _{k=0}^{n}A_{n,k}=n!} für n ≥ 0 {\displaystyle n\geq 0} , wobei A n , n = 0 {\displaystyle A_{n,n}=0} gesetzt wird.
Aus den Binomialkoeffizienten können die Euler-Zahlen mit der Formel
A n , k = ∑ i = 0 k ( − 1 ) i ( n + 1 i ) ( k + 1 − i ) n {\displaystyle A_{n,k}=\sum _{i=0}^{k}\,(-1)^{i}{\binom {n+1}{i}}(k+1-i)^{n}} für n , k ≥ 0 {\displaystyle n,k\geq 0} berechnet werden, insbesondere
A n , 1 = 2 n − ( n + 1 ) , {\displaystyle A_{n,1}=2^{n}-(n+1),} Folge A000295 in OEIS , A n , 2 = 3 n − 2 n ( n + 1 ) + 1 2 n ( n + 1 ) , {\displaystyle 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 1 2 n ( n + 1 ) − 1 6 ( n − 1 ) n ( n + 1 ) , {\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]
∑ k = 0 n A n , k ( x + k n ) = x n {\displaystyle \sum _{k=0}^{n}A_{n,k}\,{\binom {x+k}{n}}=x^{n}} für n ≥ 0 {\displaystyle n\geq 0} , wobei x {\displaystyle x} eine Variable und ( x + k n ) {\displaystyle {\tbinom {x+k}{n}}} ein verallgemeinerter Binomialkoeffizient ist.
Eine erzeugende Funktion für A n , k {\displaystyle A_{n,k}} ist
∑ n = 0 ∞ ∑ k = 0 n A n , k t n n ! x k = x − 1 x − e ( x − 1 ) t . {\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 β m {\displaystyle \beta _{m}} wird durch die alternierende Summe
∑ k = 0 m − 1 ( − 1 ) k A m − 1 , k = ( − 2 ) m ( 2 m − 1 ) m β m {\displaystyle \sum _{k=0}^{m-1}(-1)^{k}A_{m-1,k}={\frac {(-2)^{m}\,(2^{m}-1)}{m}}\,\beta _{m}} für m > 0 {\displaystyle m>0} hergestellt.
Euler-Zahlen als Koeffizienten von Euler-Polynomen[ 2] Das Euler-Polynom A n ( x ) {\displaystyle A_{n}(x)} ist definiert durch
A n ( x ) = ∑ k = 0 n − 1 A n , k x k , {\displaystyle A_{n}(x)=\sum _{k=0}^{n-1}A_{n,k}\,x^{k}\,,} also
A 0 ( x ) = A 1 ( x ) = 1 , {\displaystyle A_{0}(x)=A_{1}(x)=1,} A 2 ( x ) = 1 + x , {\displaystyle A_{2}(x)=1+x,} A 3 ( x ) = 1 + 4 x + x 2 , {\displaystyle A_{3}(x)=1+4x+x^{2},} A 4 ( x ) = 1 + 11 x + 11 x 2 + x 3 , {\displaystyle A_{4}(x)=1+11x+11x^{2}+x^{3},} A 5 ( x ) = 1 + 26 x + 66 x 2 + 26 x 3 + x 4 , {\displaystyle A_{5}(x)=1+26x+66x^{2}+26x^{3}+x^{4},} A 6 ( x ) = 1 + 57 x + 302 x 2 + 302 x 3 + 57 x 4 + x 5 , {\displaystyle A_{6}(x)=1+57x+302x^{2}+302x^{3}+57x^{4}+x^{5},} A 7 ( x ) = 1 + 120 x + 1191 x 2 + 2416 x 3 + 1191 x 4 + 120 x 5 + x 6 . {\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
A n + 1 ( x ) = ( 1 + n x ) A n ( x ) + x ( 1 − x ) A n ′ ( x ) {\displaystyle A_{n+1}(x)=(1+n\,x)\,A_{n}(x)+x\,(1-x)\,A_{n}^{\prime }(x)} und die erzeugende Funktion
∑ n = 0 ∞ A n ( x ) t n n ! = x − 1 x − e ( x − 1 ) t . {\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:
∑ k = 0 ∞ ( k + 1 ) n x k = 1 n + 2 n x + 3 n x 2 + 4 n x 3 + … = A n ( x ) ( 1 − x ) n + 1 {\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 n = 0 , 1 , 2 , … {\displaystyle n=0,\,1,\,2,\ldots } und | x | < 1 {\displaystyle |x|<1} .
Spezialfälle:
n = 0 : ∑ k = 0 ∞ x k = 1 + x + x 2 + x 3 + … = A 0 ( x ) 1 − x = 1 1 − x {\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 ),
n = 1 : ∑ k = 0 ∞ ( k + 1 ) x k = 1 + 2 x + 3 x 2 + 4 x 3 + … = A 1 ( x ) ( 1 − x ) 2 = 1 ( 1 − x ) 2 {\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}}}} ,
n = 2 : ∑ k = 0 ∞ ( k + 1 ) 2 x k = 1 + 4 x + 9 x 2 + 16 x 3 + … = A 2 ( x ) ( 1 − x ) 3 = 1 + x ( 1 − x ) 3 {\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.
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) ↑ Julius Worpitzky : Studien über die Bernoullischen und Eulerschen Zahlen , Journal für die reine und angewandte Mathematik 94, 1883, S. 203–232 ↑ Leonhard Euler : Institutiones calculi differentialis Teil 2, Academia imperialis scientiarum Petropolitanae, 1755, S. 485–486 (lateinisch)