Eulerskt tal

Från Wikipedia
Hoppa till: navigering, sök

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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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 Bn+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 \ge 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 \ge 2
\sum_{m=0}^{n-1}(-1)^m\frac{A(n,m)}{\binom{n}{m}}=(n+1)B_{n} \text{ för }n \ge 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[redigera | redigera wikitext]

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)n är en fallande potens.

Referenser[redigera | redigera wikitext]

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