Eulerskt tal

Ett eulerskt tal E(n, m) är inom matematik ett tal som är antalet permutationer på mängden {1, 2, ..., n} som har m "stigningar".

En annan beteckning för E(n, m) är ${\displaystyle \left\langle {n \atop m}\right\rangle }$.

En permutation σ på {1, 2, ..., n} har en "stigning" om det i följden σ(1), σ(2), ..., σ(n) finns två på varandra följande element σ(i) och σ(i + 1) så att σ(i) < σ(i + 1). Det eulerska talet E(n, m) är antalet permutationer på {1, 2, ..., n} som har m stigningar. m i A(n, m) kan alltså variera mellan 0 och n - 1.

Det finns, för varje n, en permutation med 0 stigningar (n, n - 1, ..., 2, 1) och en permutation med n - 1 stigningar (1, 2, ..., n - 1, n). Om en permutation har m stigningar, har omvändningen n - m - 1 stigningar. Alltså är E(n, m) = E(n, n - m - 1).

I tabellen nedan finns alla permutationer med m "stigningar" för n = 1, 2, 3 och m = 0, ..., n.

Eulerska tal uppfyller rekursionsformeln:

${\displaystyle \left\langle {n \atop m}\right\rangle =(m+1)\left\langle {n-1 \atop m}\right\rangle +(n-m)\left\langle {n-1 \atop m-1}\right\rangle }$

med begynnelsevillkoret

${\displaystyle \left\langle {0 \atop k}\right\rangle =[k=0]}$

där Iversonklammern [k = 0] antar värdet ett endast då k = 0 och noll annars.

Eulerska tal kan uttryckas med hjälp av binomialkoefficienter:

${\displaystyle \left\langle {n \atop m}\right\rangle =\sum _{k=0}\left({n+1 \atop k}\right)(m+1-k)^{n}(-1)^{k}}$.

Eftersom det finns totalt n! permutationer på {1, 2, ..., n} får man att:

${\displaystyle \sum _{m=0}^{n-1}\left\langle {n \atop m}\right\rangle =n!.}$

Med hjälp av eulerska tal kan man hitta en koppling mellan vanliga potenser och binomialkoefficienter:

${\displaystyle x^{n}=\sum _{k=0}^{n-1}\left\langle {n \atop k}\right\rangle \left({{x+k} \atop n}\right).}$

Av denna formler följer att

${\displaystyle \sum _{k=1}^{N}k^{n}=\sum _{m=0}^{n-1}A(n,m){\binom {N+1+m}{n+1}}.}$

Den alternerande summan av Eulerska talen är relaterat till Bernoullitalet B_n+1

${\displaystyle \sum _{m=0}^{n-1}(-1)^{m}A(n,m)={\frac {2^{n+1}(2^{n+1}-1)B_{n+1}}{n+1}}{\text{ för }}n\geq 1.}$

Andra summor med Eulerska tal är

${\displaystyle \sum _{m=0}^{n-1}(-1)^{m}{\frac {A(n,m)}{\binom {n-1}{m}}}=0{\text{ för }}n\geq 2}$

${\displaystyle \sum _{m=0}^{n-1}(-1)^{m}{\frac {A(n,m)}{\binom {n}{m}}}=(n+1)B_{n}{\text{ för }}n\geq 2.}$

En intressant oändlig serie är

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

En annan typ av eulerska tal fås om man betraktar permutationer på multimängden {1, 1, 2, 2, ..., n, n} med egenskapen att mellan de två förekomsterna av m finns bara tal som är större än m. Antalet sådana permutationer med k stigningar är ett eulerskt tal av andra slaget och betecknas ${\displaystyle \left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle .}$

För n = 3 finns totalt 15 permutationer som beskrivits ovan, en med ingen stigning, åtta med en stigning och sex med två stigningar:

Ingen stigning: 332211

En stigning: 221133, 221331, 223311, 233211, 113322, 133221, 331122, 331221

Två stigningar: 112233, 122133, 112332, 123321, 133122, 122331

Eulerska tal av andra slaget uppfyller:

${\displaystyle \left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle =(2n-k-1)\left\langle \!\!\left\langle {{n-1} \atop {k-1}}\right\rangle \!\!\right\rangle +(k+1)\left\langle \!\!\left\langle {{k-1} \atop {m}}\right\rangle \!\!\right\rangle ,}$

med begynnelsevillkoret

${\displaystyle \left\langle \!\!\left\langle {0 \atop k}\right\rangle \!\!\right\rangle =[k=0].}$

Det totala antalet permutationer med egenskapen ovan är:

${\displaystyle \sum _{k=0}^{n-1}\left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle ={\frac {(2n)^{\underline {n}}}{2^{n}}}}$

där (2n)ⁿ är en fallande potens.

• Graham; Knuth, Patashnik (1994). Concrete Mathematics. Addison-Wesley. ISBN 0-201-55802-5