Numeri euleriani

In combinatoria, il numero euleriano A(n, m) è il numero di permutazioni dei numeri fra 1 e n nelle quali esattamente m elementi sono maggiori di quelli precedenti. Tali numeri sono anche i coefficienti dei polinomi di Eulero:

${\displaystyle A_{n}(t)=\sum _{m=0}^{n}A(n,m)\ t^{m}.}$

I polinomi di Eulero sono definiti dalla funzione generatrice esponenziale:

${\displaystyle \sum _{n=0}^{\infty }A_{n}(t)\,{\frac {x^{n}}{n!}}={\frac {t-1}{t-\mathrm {e} ^{(t-1)\,x}}}.}$

Essi possono essere calcolati attraverso la seguente formula ricorsiva:

${\displaystyle A_{0}(t)=1,\,}$

${\displaystyle A_{n}(t)=t\,(1-t)\,A_{n-1}'(t)+A_{n-1}(t)\,(1+(n-1)\,t),\quad n\geq 1.}$

Un modo equivalente per dare questa definizione è quello di definire i polinomi di Eulero induttivamente:

${\displaystyle A_{0}(t)=1,\,}$

${\displaystyle A_{n}(t)=\sum _{k=0}^{n-1}{\binom {n}{k}}\,A_{k}(t)\,(t-1)^{n-1-k},\quad n\geq 1.}$

Le notazioni per questi numeri sono A(n, m), E(n, m) e ${\displaystyle \scriptstyle \left\langle {n \atop m}\right\rangle }$.

Essi non vanno confusi con i numeri di Eulero.

Storia

Polinomi di Eulero

Nel 1755 Eulero si occupò, nel libro Institutiones calculi differentialis, dei polinomi α₁(x) = 1, α₂(x) = x + 1, α₃(x) = x^2 + 4x + 1, ecc. Tali polinomi sono una variante di quelli che oggi sono chiamati polinomi di Eulero A_n(x).

Proprietà

Per ogni valore n > 0, l'indice m in A(n, m) può assumere valori compresi tra 0 e n − 1. Per n dato, esiste una sola permutazione con nessun valore maggiore di quello che lo precede; è la permutazione (n, n − 1, n − 2, ..., 1). Inoltre ne esiste una sola con n − 1 valori maggiori del precedente; è la permutazione (1, 2, 3, ..., n). Perciò, A(n, 0) e A(n, n − 1) valgono 1 per ogni valore di n.

L'inversione di una permutazione con m numeri maggiori dei rispettivi numeri precedenti genera un'altra permutazione in cui tali valori sono in quantità n − m − 1. Dunque A(n, m) = A(n, n − m − 1).

I valori di A(n, m) possono essere calcolati a mano per valori piccoli di n e m. Ad esempio, per n ≤ 3, si ha:

n	m	Permutazioni	A(n, m)
1	0	(1)	A(1,0) = 1
2	0	(2, 1)	A(2,0) = 1
	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

Per valori più grandi di n, A(n, m) si può calcolare usando la ricorsione

${\displaystyle A(n,m)=(n-m)A(n-1,m-1)+(m+1)A(n-1,m).}$

Da cui, ad esempio:

${\displaystyle A(4,1)=(4-1)A(3,0)+(1+1)A(3,1)=3\times 1+2\times 4=11.}$

I valori di A(n, m) (sequenza A008292 dell'OEIS) per 0 ≤ n ≤ 9 sono:

n \ m	0	1	2	3	4	5	6	7	8
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

Questa disposizione triangolare si chiama triangolo di Eulero e condivide alcune caratteristiche con il triangolo di Tartaglia. La somma dei numeri sulla riga n-esima è ${\displaystyle n!}$.

Formula chiusa

Una forma chiusa per A(n, m) è la seguente:

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

Proprietà della somma

È evidente dalla definizione di combinatoria che la somma dei numeri di Eulero per un dato valore di n è il numero totale di permutazioni dei numeri tra 1 e n, ovvero

${\displaystyle \sum _{m=0}^{n-1}A(n,m)=n!{\text{ per }}n\geq 1.}$

La serie alternata dei numeri di Eulero per n dato è strettamente collegata ai numeri di Bernoulli B_n+1

${\displaystyle \sum _{m=0}^{n-1}(-1)^{m}A(n,m)={\frac {2^{n+1}(2^{n+1}-1)B_{n+1}}{n+1}}{\text{ per }}n\geq 1.}$

Altre sommatorie interessanti per i numeri di Eulero sono:

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

${\displaystyle \sum _{m=0}^{n-1}(-1)^{m}{\frac {A(n,m)}{\binom {n}{m}}}=(n+1)B_{n}{\text{ per }}n\geq 2,}$

dove B_n è l'n-esimo numero di Bernoulli.

Identità

I numeri di Eulero compaiono nella funzione generatrice delle sequenze di potenze n-esime

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

Questo implica che 0^0 = 0 e A(0,0) = 1 (poiché esiste una permutazione di 0 elementi, e nessuno di essi può essere maggiore di un altro).

L'identità di Worpitzky permette di esprimere x^n come combinazione lineare di numeri di Eulero con i coefficienti binomiali:

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

Da questa identità segue che

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

Un'altra curiosa identità è

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

Dove il numeratore delle frazioni di destra è un polinomio di Eulero.

Numeri euleriani di seconda specie

Le permutazioni del multiinsieme {1, 1, 2, 2, ···, n, n} con la proprietà che, per ogni k, tutti i numeri compresi tra le due occorrenze di k nella permutazione sono maggiori di k, possono essere contate attraverso il semifattoriale ${\displaystyle (2n-1)!!}$. I numeri euleriani di seconda specie, indicati con ${\displaystyle \scriptstyle \left\langle \!\!\left\langle {n \atop m}\right\rangle \!\!\right\rangle }$, servono a contare il numero di permutazioni con esattamente m elementi che sono più grandi dell'elemento che li precede. Ad esempio, se n = 3 ci sono 15 permutazioni di questo tipo:

${\displaystyle 332211,\;}$

${\displaystyle 221133,\;221331,\;223311,\;233211,\;113322,\;133221,\;331122,\;331221,}$

${\displaystyle 112233,\;122133,\;112332,\;123321,\;133122,\;122331.}$

I numeri euleriani di seconda specie soddisfano la relazione di ricorrenza, che discende dalla definizione:

${\displaystyle \left\langle \!\!\left\langle {n \atop m}\right\rangle \!\!\right\rangle =(2n-m-1)\left\langle \!\!\left\langle {n-1 \atop m-1}\right\rangle \!\!\right\rangle +(m+1)\left\langle \!\!\left\langle {n-1 \atop m}\right\rangle \!\!\right\rangle ,}$

con la condizione iniziale che n = 0, espressa attraverso le parentesi di Iverson:

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

Analogamente, i polinomi euleriani di seconda specie, qui indicati con P_n (non esiste una notazione standard) sono

${\displaystyle P_{n}(x):=\sum _{m=0}^{n}\left\langle \!\!\left\langle {n \atop m}\right\rangle \!\!\right\rangle x^{m}}$

e per essi vale la seguente relazione di ricorrenza:

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

con condizione iniziale

${\displaystyle P_{0}(x)=1.}$

Quest'ultima ricorrenza può essere scritta in modo più compatto attraverso un fattore di integrazione:

${\displaystyle (x-1)^{-2n-2}P_{n+1}(x)=\left(x(1-x)^{-2n-1}P_{n}(x)\right)^{\prime }}$

tale che la funzione razionale

${\displaystyle u_{n}(x):=(x-1)^{-2n}P_{n}(x)}$

soddisfa la seguente relazione di ricorrenza:

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

da cui si ottengono i polinomi di Eulero nella forma P_n(x) = (1−x)^2n u_n(x), e i numeri euleriani di seconda specie come coefficienti.

Questi sono i primi valori per i numeri euleriani di seconda specie (sequenza A008517 dell'OEIS):

n \ m	0	1	2	3	4	5	6	7	8
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

In cui, di conseguenza, la somma della riga n-esima (che corrisponde anche al valore di P_n(1)), è ${\displaystyle (2n-1)!!}$.

Bibliografia

• (LA) Leonardo Eulero, Institutiones calculi differentialis cum eius usu in analysi finitorum ac doctrina serierum [Fondamenti del calcolo differenziale, con applicazioni in analisi finita e serie], Academia imperialis scientiarum Petropolitana; Berolini: Officina Michaelis, 1755.
• (EN) Graham, Knuth e Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2ª ed., Addison-Wesley, 1994, pp. 267-272.
• (EN) Eulerian numbers with fractional order parameters, in Aequationes Mathematicae, vol. 46, 1993, pp. 119–142, DOI:10.1007/bf01834003.
• (EN) T. K. Petersen, Eulerian Numbers, Birkhaüser, 2015.

Voci correlate

• Numeri di Eulero
• Coefficiente binomiale
• Fattoriale
• Numeri di Bernoulli

Collegamenti esterni

• (EN) Euler-matrix (PDF), su go.helms-net.de. URL consultato il 7 gennaio 2017.