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 $⟨ \binom{n}{m} ⟩$ .

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
2	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:

⟨ \binom{n}{m} ⟩ = (m + 1) ⟨ \binom{n - 1}{m} ⟩ + (n - m) ⟨ \binom{n - 1}{m - 1} ⟩

med begynnelsevillkoret

⟨ \binom{0}{k} ⟩ = [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:

⟨ \binom{n}{m} ⟩ = \sum_{k = 0} (\binom{n + 1}{k}) (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} ⟨ \binom{n}{m} ⟩ = n! .

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

x^{n} = \sum_{k = 0}^{n - 1} ⟨ \binom{n}{k} ⟩ (\binom{x + k}{n}) .

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} 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 för n \geq 2

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

En intressant oändlig serie är

\frac{e}{1 - e x} = \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 $⟨ ⟨ \binom{n}{k} ⟩ ⟩ .$

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:

⟨ ⟨ \binom{n}{k} ⟩ ⟩ = (2 n - k - 1) ⟨ ⟨ \binom{n - 1}{k - 1} ⟩ ⟩ + (k + 1) ⟨ ⟨ \binom{k - 1}{m} ⟩ ⟩,

med begynnelsevillkoret

⟨ ⟨ \binom{0}{k} ⟩ ⟩ = [k = 0] .

Det totala antalet permutationer med egenskapen ovan är:

\sum_{k = 0}^{n - 1} ⟨ ⟨ \binom{n}{k} ⟩ ⟩ = \frac{(2 n)^{\underline{n}}}{2^{n}}

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

Referenser

Mall:Bokref

Eulerskt tal

Innehåll

Grundläggande egenskaper och exempel

Egenskaper

Eulerska tal av andra slaget

Referenser

Navigeringsmeny

Eulerskt tal

Grundläggande egenskaper och exempel

Egenskaper

Eulerska tal av andra slaget

Referenser

Navigeringsmeny

Sök