Euleriansk nummer

I matematikk , og mer presist i kombinatorisk analyse , er Eulerian-tallet A ( n , m ) antall permutasjoner av heltall fra 1 til n som nøyaktig m- elementer er større enn forrige element (permutasjoner med m «montert") . Eulerianske tall er koeffisientene til de Euleriske polynomene :

{\ displaystyle A_ {n} (X) = \ sum _ {m = 0} ^ {n} A (n, m) \ X ^ {m} (A1 = A2 = 1, A2 = 1 + X, A3 = 1 + 4X + X ^ {2}, ...)}

Disse polynomene vises i telleren for uttrykk knyttet til generatorfunksjonen til sekvensen . $\ scriptstyle 1 ^ {n}, \ 2 ^ {n}, \ 3 ^ {n}, \ \ prikker$

Disse tallene dannes etter A008292 fra OEIS .

Andre notasjoner for A ( n , m ) er E ( n , m ) og $\ left \ langle {n \ på toppen av} \ høyre \ rangle.$

Historisk

I 1755, i hans bok Institutiones calculi differentialis , Leonhard Euler studerte polynomene a- 1 ( x ) = 1, α 2 ( x ) = x + 1, α 3 ( x ) = x 2 + 4 x + 1, etc. (se faksimilen motsatt). Disse polynomene er en forskjøvet form av våre Euleriske polynomer A n ( x ).

I analogi med notasjonen av binomiale koeffisienter og med Stirling-tall og notasjonen ble foreslått av Donald Knuth i 1968 i The Art of Computer Programming . $\ left ({n \ ovenpå k} \ høyre)$ $\ venstre [{n \ på toppen av k} \ høyre]$ $\ venstre \ {{n \ på toppen av k} \ høyre \},$ $\ left \ langle {n \ på toppen m} \ høyre \ rangle$

Elementære egenskaper

For en gitt n > 0 kan indeksen m til A ( n , m ) variere fra 0 til n - 1. For fast n er det bare en permutasjon uten å stige, den fallende permutasjonen ( n , n - 1, n - 2, ..., 1). Det er også en enkelt permutasjon med n - 1 stigende, identisk (eller stigende) permutasjon (1, 2, 3, ..., n ). Dermed er A ( n , 0) = A ( n , n - 1) = 1 for alle n .

Å reversere en permutasjon med m stigninger skaper en annen permutasjon med n - m - 1 stigninger; så

A ( n , m ) = A ( n , n - m - 1).

Verdiene til A ( n , m ) kan beregnes "for hånd" for små verdier av n og m . for eksempel

ikke	m	Kombinasjonsmuligheter	A ( n , m )
1	0	(1)	A (1.0) = 1
2	0	(2, 1)	A (2.0) = 1
2	1	(1, 2 )	A (2.1) = 1
3	0	(3, 2, 1)	A (3.0) = 1
	1	(1, 3 , 2) (2, 1, 3 ) (2, 3 , 1) (3, 1, 2 )	A (3.1) = 4
	2	(1, 2 , 3 )	A (3.2) = 1

For større verdier på n kan A ( n , m ) beregnes ved hjelp av gjentakelsesrelasjonen

A (n, m) = (nm) A (n-1, m-1) + (m + 1) A (n-1, m).

for eksempel

A (4,1) = (4-1) A (3,0) + (1 + 1) A (3,1) = 3 \ ganger 1 + 2 \ ganger 4 = 11.

Verdiene til A ( n , m ) for 0 ≤ n ≤ 9 (det er fortsettelsen A008292 til OEIS ) er:

n \ m	0	1	2	3	4	5	6	7	8
0	1
1	1
2	1	1
3	1	4	1
4	1	11	11	1
5	1	26	66	26	1
6	1	57	302	302	57	1
7	1	120	1191	2416	1191	120	1
8	1	247	4293	15619	15619	4293	247	1
9	1	502	14608	88234	156190	88234	14608	502	1

Dette trekantede bordet kalles Eulers trekant , og har noen av egenskapene til Pascals trekant . Summen av n- raden er antallet av alle permutasjonene, eller den faktiske faktoren n !.

Eksplisitt formel

En eksplisitt formel for A ( n , m ) er

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

Sumberegninger

I følge deres kombinasjonsdefinisjon er summen av Eulerian-tallene for en gitt verdi på n det totale antall permutasjoner av heltall fra 1 til n , og derfor

\ sum _ {{m = 0}} ^ {{n-1}} A (n, m) = n!.

Den vekslende summen av Eulerian-tallene for en gitt verdi på n er relatert til Bernoulli-tallet 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}}.

Her er andre summeringsformler:

\ sum _ {{m = 0}} ^ {{n-1}} (- 1) ^ {m} {\ frac {A (n, m)} {{\ binom {n-1} {m}} }} = 0,

\ sum _ {{m = 0}} ^ {{n-1}} (- 1) ^ {m} {\ frac {A (n, m)} {{\ binom {n} {m}}}} = (n + 1) B _ {{n}},

hvor B n er den n- te Bernoulli nummer .

Identiteter

Eulerian-tallene vises i generatorfunksjonen til sekvensen av n- emekrefter

{\ displaystyle \ sum _ {k = 1} ^ {\ infty} k ^ {n} x ^ {k} = {\ frac {\ sum _ {m = 0} ^ {n-1} A (n, m ) x ^ {m + 1}} {(1-x) ^ {n + 1}}} = {\ frac {xA_ {n} (x)} {(1-x) ^ {n + 1}}} .}

Den identiteten av Worpitzky ekspresser x n som lineær kombinasjon av tall Eulersk med binomialkoeffisienter :

x ^ {n} = \ sum _ {{m = 0}} ^ {{n-1}} A (n, m) {\ binom {x + m} {n}}.

En annen bemerkelsesverdig identitet oppnås ved transformasjonen:

e ^ {k} = \ sum _ {{n = 0}} ^ {\ infty} {\ frac {k ^ {n}} {n!}}

(x ^ {k}) (e ^ {k}) = \ sum _ {{n = 0}} ^ {\ infty} {\ frac {(x ^ {k}) (k ^ {n})} { ikke!}}

\ sum _ {{k = 1}} ^ {\ infty} (x ^ {k}) (e ^ {k}) = \ sum _ {{k = 1}} ^ {\ infty} \ sum _ {{ n = 0}} ^ {\ infty} {\ frac {(x ^ {k}) (k ^ {n})} {n!}}

For , begrepene til venstre danner en konvergent geometrisk serie, og begrepene til høyre er positive; vi kan derfor bytte innkalling. Ved å bruke den forrige identiteten får vi:

0 \ leq x <{1} / {e}

\ sum _ {{k = 1}} ^ {\ infty} (xe) ^ {k} = \ sum _ {{k = 1}} ^ {\ infty} \ sum _ {{n = 0}} ^ { \ infty} {\ frac {(x ^ {k}) (k ^ {n})} {n!}}

{\ frac {ex} {1-ex}} = \ sum _ {{n = 0}} ^ {\ infty} \ sum _ {{k = 1}} ^ {\ infty} {\ frac {(x ^ {k}) (k ^ {n})} {n!}} = \ sum _ {{n = 0}} ^ {\ infty} {\ frac {\ sum _ {{m = 0}} ^ {{ n}} A (n, m) x ^ {{m + 1}}} {n! (1-x) ^ {{n + 1}}}}

Til syvende og sist har vi det

0 \ leq x <{1} / {e}

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

Summen av telleren til høyre er summen av Euler-polynomene.

En bemerkelsesverdig sannsynlighetsidentitet tillater en enkel demonstrasjon av en sentral grensesetning for antall stigninger av en permutasjon som er tilfeldig tegnet. Hvis er en sekvens med ensartede iid tilfeldige variabler over [0,1] og hvis $\ scriptstyle \ (U_ {1}, U_ {2}, \ prikker, U_ {n}) \$

S_ {n} = \ sum _ {{k = 1}} ^ {n} U_ {k}, \ quad X_ {n} = \ left \ lfloor S_ {n} \ right \ rfloor,

så

{\ mathbb P} \ left (k \ leq S_ {n} <k + 1 \ right) = {\ mathbb P} \ left (X_ {n} = k \ right) \ = {\ frac {A (n, k)} {n!}}.

Eulerian nummer av den andre typen

Antallet flersettpermutasjoner slik at for hver k er alle tallene mellom de to forekomstene av k større enn k , produktet av odde heltall opp til 2 n -1 (noen ganger kalt dobbeltfaktor av (2 n -1) , og bemerket (2 n -1) !!); vi har . $\ {1,1,2,2, \ cdots, n, n \}$ $(2n-1) !! = \ prod _ {{{k = 1}}} ^ {n} (2k-1) = {\ frac {{{(2n)!}} {{2 ^ {n} n !}}}$

Den Eulersk rekke andre slag , bemerket, teller antall av alle disse permutasjoner ha nøyaktig m bestigninger. For eksempel, for n = 3, er det 3 !! = 15 permutasjoner av denne typen, en uten stigning, 8 med en stigning og 6 med to stigende: $\ venstre \ langle \! \! \ venstre \ langle {n \ på toppen m} \ høyre \ rangle \! \! \ høyre \ rangle,$

332211, \;

221133, \; 221331, \; 223311, \; 233211, \; 113322, \; 133221, \; 331122, \; 331221,

112233, \; 122133, \; 112332, \; 123321, \; 133122, \; 122331.

Fra denne definisjonen er det lett å vise at tallene tilfredsstiller gjentakelse: $\ left \ langle \! \! \ left \ langle {n \ på toppen m} \ høyre \ rangle \! \! \ right \ rangle$

\ venstre \ langle \! \! \ venstre \ langle {n \ på toppen m} \ høyre \ rangle \! \! \ høyre \ rangle = (2n-m-1) \ venstre \ langle \! \! \ venstre \ langle {{n-1} \ på toppen {m-1}} \ høyre \ rangle \! \! \ høyre \ rangle + (m + 1) \ venstre \ langle \! \! \ venstre \ langle {{n-1} \ på toppen {m}} \ høyre \ rangle \! \! \ høyre \ rangle,

med de første forholdene:

\ venstre \ langle \! \! \ venstre \ langle {0 \ oppå m} \ høyre \ rangle \! \! \ høyre \ rangle = 0 \

for m > 0 og .

\ left \ langle \! \! \ left \ langle {0 \ på toppen 0} \ høyre \ rangle \! \! \ right \ rangle = 1

Vi får dem til å svare til de euleriske polynomene av den andre typen, bemerket her : $P_ {n}$

P_ {n} (x): = \ sum _ {{n = 0}} ^ {n} \ venstre \ langle \! \! \ Venstre \ langle {n \ oppå m} \ høyre \ rangle \! \! \ høyre \ rangle x ^ {m}

;

fra de foregående gjentakelsesrelasjonene, trekker vi ut at P n (x) tilfredsstiller forholdet:

P _ {{n + 1}} (x) = (2nx + 1) P_ {n} (x) -x (x-1) P_ {n} ^ {\ prime} (x)

, med

P_ {0} (x) = 1.

Vi kan omskrive det:

(x-1) ^ {{- 2n-2}} P _ {{n + 1}} (x) = \ left (x (1-x) ^ {{- 2n-1}} P_ {n} ( x) \ høyre) ^ {\ prime}

;

dermed den rasjonelle funksjonen

u_ {n} (x): = (x-1) ^ {{- 2n}} P _ {{n}} (x)

fornøyd:

u _ {{n + 1}} = \ left ({\ frac {x} {1-x}} u_ {n} \ right) ^ {\ prime} \ quad, u_ {0} = 1,

hvorfra vi henter polynomene i form P n (x) = (1-x) 2n u n (x); deretter Eulerianske tall av den andre typen som er deres koeffisienter.

Her er noen verdier av disse tallene (etter A008517 av OEIS )

n \ m	0	1	2	3	4	5	6	7	8
0	1
1	1
2	1	2
3	1	8	6
4	1	22	58	24
5	1	52	328	444	120
6	1	114	1452	4400	3708	720
7	1	240	5610	32120	58140	33984	5040
8	1	494	19950	195800	644020	785304	341136	40320
9	1	1004	67260	1062500	5765500	12440064	11026296	3733920	362880

Summen av n- raden er P n (1) = (2n-1) !!.

Relaterte artikler

Merknader og referanser

Merknader

se (i) S. Tanny , " En sannsynlig tolkning av Eulerianske tall " , Duke Math. J. , vol. 40,1973, s. 717-722eller (en) RP Stanley , “ Eulerian partitions of a unit hypercube ” , Higher Combinatorics , Dordrecht, M. Aigner, red., Reidel,1977.

Referanser

(fr) Denne artikkelen er delvis eller helt hentet fra den engelske Wikipedia- artikkelen med tittelen " Eulerian number " ( se listen over forfattere ) .
(la) Leonhard Euler , Institutiones calculi differentialis cum eius usu in analysi finitorum ac doctrina serierum (Fundament of Differential Calculus, with applications to Finite Analysis and to series) , vol. II, Academia imperialis scientiarum Petropolitana ,1755( les online ) , kap. VII
(en) Ronald Graham , Donald Knuth og Oren Patashnik , Concrete Mathematics : A Foundation for Computer Science , 1994 (andre utgave), Addison-Wesley, s. 267–272

Eksterne linker

(in) Eulerian Polynomials på wiki til OEIS
(en) Eulerian Numbers on MathPages
(no) Eric W. Weisstein , “ Eulerian Number ” , på MathWorld
(no) Eric W. Weisstein , " Euler's Number Triangle " , på MathWorld
(no) Eric W. Weisstein , “ Worpitzky's Identity ” , på MathWorld
(no) Eric W. Weisstein , “ Second-Order Eulerian Triangle ” , på MathWorld
(en) Euler's Triangle på siden til Gottfried Helms, fra University of Cassel