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 .

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:

med begynnelsevillkoret

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:

.

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

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

Av denna formler följer att

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

Andra summor med Eulerska tal är

En intressant oändlig serie är

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

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:

med begynnelsevillkoret

Det totala antalet permutationer med egenskapen ovan är:

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