Euler numbers

This article covers the whole numbers of the Euler triangle.

• For other numbers and number sequences named after Euler, see Euler's numbers (explanation of terms) .
• For Euler's triangle in spherical geometry, see spherical triangle .

The Euler number A _{n, k} named after Leonhard Euler in combinatorics, also written as or , is the number of permutations (arrangements) of in which exactly elements are greater than the previous one, i.e. which contain exactly increases. Equivalent to this is the definition with “smaller” instead of “larger” and “descents” instead of “climbs”. According to another definition, the Euler number is the number of permutations of with exactly shifted maximum monotonically increasing sections, whereby the second parameters in relation to the definition used here by one: . ${\displaystyle E(n,k)}$ ${\displaystyle \textstyle {\bigl \langle }\!{n \atop k}\!{\bigr \rangle }}$ ${\displaystyle 1,\ldots ,n}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle a(n,k)}$ ${\displaystyle 1,\ldots ,n}$ ${\displaystyle k}$ ${\displaystyle a(n,k)=A_{n,k-1}}$

Euler triangle

Like the binomial coefficients in Pascal's triangle , the Euler numbers can be arranged in the Euler triangle (first row , first column ; sequence A008292 in OEIS ): ${\displaystyle n=1}$ ${\displaystyle k=0}$

                             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

You can use the following recursion formula to calculate each entry from the two above:

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

for with and for . The convention and for would also make sense; it is common with the alternative definition. ${\displaystyle n>0}$ ${\displaystyle A_{0,0}=1}$ ${\displaystyle A_{0,k}=0}$ ${\displaystyle k\not =0}$ ${\displaystyle A_{0,-1}=1}$ ${\displaystyle A_{0,k}=0}$ ${\displaystyle k\not =-1}$

properties

Follow directly from the definition and for and ${\displaystyle A_{n,0}=1}$ ${\displaystyle A_{n,n-1-k}=A_{n,k}}$ ${\displaystyle n>0}$

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

The Euler numbers can be obtained from the binomial coefficients using the formula

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

to be charged for, in particular ${\displaystyle n,k\geq 0}$

• ${\displaystyle A_{n,1}=2^{n}-(n+1),}$Follow A000295 in OEIS ,
• ${\displaystyle A_{n,2}=3^{n}-2^{n}\,(n+1)+{\tfrac {1}{2}}\,n\,(n+1),}$Follow A000460 in OEIS and
• ${\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),}$Follow A000498 in OEIS .

The Worpitzky identity applies ( Worpitzky 1883)

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

for , where is a variable and a generalized binomial coefficient . ${\displaystyle n\geq 0}$ ${\displaystyle x}$ ${\displaystyle {\tbinom {x+k}{n}}}$

A generating function for is ${\displaystyle A_{n,k}}$

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

A relationship to the Bernoulli numbers is given by the alternating sum ${\displaystyle \beta _{m}}$

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

for manufactured. ${\displaystyle m>0}$

Euler polynomials

Euler numbers as coefficients of Euler polynomials

The Euler polynomial is defined by ${\displaystyle A_{n}(x)}$

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

so

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

The recursion formula is obtained from the corresponding equations for the Euler numbers

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

and the generating function

${\displaystyle \sum _{n=0}^{\infty }A_{n}(x)\,{\frac {t^{n}}{n!}}={\frac {x-1}{x-e^{(x-1)\,t}}}\,.}$

literature

• 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, pp. 83-106 (French; Euler numbers as Coefficients on p. 85 )
• David P. Roselle : Permutations by number of rises and successions , Proceedings of the AMS 19, 1968, pp. 8-16 (English)
• Ronald L. Graham , Donald E. Knuth , Oren Patashnik : Concrete mathematics: a foundation for computer science , Addison-Wesley, Reading 1988, 2nd edition 1994, ISBN 0-201-55802-5 , pp. 267-272 (English ; Knuth's website for the book with errata: Concrete Mathematics, Second Edition )
• Kenneth H. Rosen, John G. Michaels, et al. (Ed.): Handbook of Discrete and Combinatorial Mathematics , CRC Press LLC, 1999, ISBN 0-8493-0149-1 (English)
• Friedrich Hirzebruch : Eulerian polynomials ( PDF file, 96 kB), Münster Journal of Mathematics 1, 2008, pp. 9–14 (English)

Web links

• Eric W. Weisstein: Eulerian Number , Euler's Number Triangle and Worpitzky's Identity in MathWorld (English)
• Permutations: Order Notation in the NIST Digital Library of Mathematical Functions (English)
• Eulerian polynomials by Peter Luschny, August 18, 2010

Individual evidence

1. ↑ Julius Worpitzky : Studies on Bernoulli and Euler's numbers , Journal for pure and applied mathematics 94, 1883, pp. 203-232
2. ^ Leonhard Euler : Institutiones calculi differentialis part 2, Academia imperialis scientiarum Petropolitanae, 1755, pp. 485-486 (Latin)