This article covers the whole numbers of the Euler 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: .
E.
(
n
,
k
)
{\ displaystyle E (n, k)}
⟨
n
k
⟩
{\ displaystyle \ textstyle {\ bigl \ langle} \! {n \ atop k} \! {\ bigr \ rangle}}
1
,
...
,
n
{\ displaystyle 1, \ ldots, n}
k
{\ displaystyle k}
k
{\ displaystyle k}
a
(
n
,
k
)
{\ displaystyle a (n, k)}
1
,
...
,
n
{\ displaystyle 1, \ ldots, n}
k
{\ displaystyle k}
a
(
n
,
k
)
=
A.
n
,
k
-
1
{\ 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 ):
n
=
1
{\ displaystyle n = 1}
k
=
0
{\ 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:
A.
n
,
k
=
(
n
-
k
)
A.
n
-
1
,
k
-
1
+
(
k
+
1
)
A.
n
-
1
,
k
{\ displaystyle A_ {n, k} = (nk) \, 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.
n
>
0
{\ displaystyle n> 0}
A.
0
,
0
=
1
{\ displaystyle A_ {0,0} = 1}
A.
0
,
k
=
0
{\ displaystyle A_ {0, k} = 0}
k
≠
0
{\ displaystyle k \ not = 0}
A.
0
,
-
1
=
1
{\ displaystyle A_ {0, -1} = 1}
A.
0
,
k
=
0
{\ displaystyle A_ {0, k} = 0}
k
≠
-
1
{\ displaystyle k \ not = -1}
properties
Follow directly from the definition and for and
A.
n
,
0
=
1
{\ displaystyle A_ {n, 0} = 1}
A.
n
,
n
-
1
-
k
=
A.
n
,
k
{\ displaystyle A_ {n, n-1-k} = A_ {n, k}}
n
>
0
{\ displaystyle n> 0}
∑
k
=
0
n
A.
n
,
k
=
n
!
{\ displaystyle \ sum _ {k = 0} ^ {n} A_ {n, k} = n!}
for .
n
≥
0
{\ displaystyle n \ geq 0}
The Euler numbers can be obtained from the binomial coefficients using the formula
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}}
to be charged for, in particular
n
,
k
≥
0
{\ displaystyle n, k \ geq 0}
A.
n
,
1
=
2
n
-
(
n
+
1
)
,
{\ displaystyle A_ {n, 1} = 2 ^ {n} - (n + 1),}
Follow 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), }
Follow A000460 in OEIS and
A.
n
,
3
=
4th
n
-
3
n
(
n
+
1
)
+
2
n
1
2
n
(
n
+
1
)
-
1
6th
(
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),}
Follow A000498 in OEIS .
The Worpitzky identity applies ( Worpitzky 1883)
∑
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}}
for , where is a variable and a generalized binomial coefficient .
n
≥
0
{\ displaystyle n \ geq 0}
x
{\ displaystyle x}
(
x
+
k
n
)
{\ displaystyle {\ tbinom {x + k} {n}}}
A generating function for is
A.
n
,
k
{\ displaystyle A_ {n, k}}
∑
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} {xe ^ {(x-1) \, t}}} \ ,.}
A relationship to the Bernoulli numbers is given by the alternating sum
β
m
{\ displaystyle \ beta _ {m}}
∑
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}}
for manufactured.
m
>
0
{\ displaystyle m> 0}
Euler polynomials
Euler numbers as coefficients of Euler polynomials
The Euler polynomial is defined by
A.
n
(
x
)
{\ displaystyle A_ {n} (x)}
A.
n
(
x
)
=
∑
k
=
0
n
A.
n
,
k
x
k
,
{\ displaystyle A_ {n} (x) = \ sum _ {k = 0} ^ {n} A_ {n, k} \, x ^ {k} \ ,,}
so
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
+
4th
x
+
x
2
,
{\ displaystyle A_ {3} (x) = 1 + 4x + x ^ {2},}
A.
4th
(
x
)
=
1
+
11
x
+
11
x
2
+
x
3
,
{\ displaystyle A_ {4} (x) = 1 + 11x + 11x ^ {2} + x ^ {3},}
A.
5
(
x
)
=
1
+
26th
x
+
66
x
2
+
26th
x
3
+
x
4th
,
{\ displaystyle A_ {5} (x) = 1 + 26x + 66x ^ {2} + 26x ^ {3} + x ^ {4},}
A.
6th
(
x
)
=
1
+
57
x
+
302
x
2
+
302
x
3
+
57
x
4th
+
x
5
,
{\ displaystyle A_ {6} (x) = 1 + 57x + 302x ^ {2} + 302x ^ {3} + 57x ^ {4} + x ^ {5},}
A.
7th
(
x
)
=
1
+
120
x
+
1191
x
2
+
2416
x
3
+
1191
x
4th
+
120
x
5
+
x
6th
.
{\ 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
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)}
and the generating function
∑
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} { xe ^ {(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
Individual evidence
↑ Julius Worpitzky : Studies on Bernoulli and Euler's numbers , Journal for pure and applied mathematics 94, 1883, pp. 203-232
^ Leonhard Euler : Institutiones calculi differentialis part 2, Academia imperialis scientiarum Petropolitanae, 1755, pp. 485-486 (Latin)
<img src="https://de.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">