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 $\left\langle {n \atop m}\right\rangle$.

Grundläggande egenskaper och exempel

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.

n	m	Permutationer	E(n, m)
1	0	(1)	1
2	0	(2, 1)	1
	1	(1, 2)	1
3	0	(3, 2, 1)	1
	1	(1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2)	4
	2	(1, 2, 3)	1

Egenskaper

Eulerska tal uppfyller rekursionsformeln:

$\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

$\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:

$\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:

$\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:

$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

$\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

$\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

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

$\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

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

Eulerska tal av andra slaget

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 $\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:

$\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

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

Det totala antalet permutationer med egenskapen ovan är:

$\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.

Referenser

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