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:

A_{n} (t) = \sum_{m = 0}^{n} A (n, m) t^{m} .

I polinomi di Eulero sono definiti dalla funzione generatrice esponenziale:

\sum_{n = 0}^{\infty} A_{n} (t) \frac{x^{n}}{n!} = \frac{t - 1}{t - e^{(t - 1) x}} .

Essi possono essere calcolati attraverso la seguente formula ricorsiva:

A_{0} (t) = 1,

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

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

A_{0} (t) = 1,

A_{n} (t) = \sum_{k = 0}^{n - 1} (\binom{n}{k}) A_{k} (t) (t - 1)^{n - 1 - k}, n \geq 1 .

Le notazioni per questi numeri sono A(n, m), E(n, m) e $⟨ \binom{n}{m} ⟩$ .

Essi non vanno confusi con i numeri di Eulero.

Storia

File:EulerianPolynomialsByEuler1755.png

Polinomi di Eulero

Nel 1755 Eulero si occupò, nel libro Institutiones calculi differentialis, dei polinomi α₁(x) = 1, α₂(x) = x + 1, α₃(x) = x² + 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
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

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

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

Da cui, ad esempio:

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 è $n!$ .

Formula chiusa

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

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

\sum_{m = 0}^{n - 1} A (n, m) = n! per n \geq 1 .

La serie alternata dei numeri di Eulero per n dato è strettamente collegata ai numeri di Bernoulli 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} per n \geq 1 .

Altre sommatorie interessanti per i numeri di Eulero sono:

\sum_{m = 0}^{n - 1} (- 1)^{m} \frac{A (n, m)}{(\binom{n - 1}{m})} = 0 per n \geq 2,

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

dove B_n è lTemplate:'n-esimo numero di Bernoulli.

Identità

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

\sum_{k = 0}^{\infty} k^{n} x^{k} = \frac{\sum_{m = 0}^{n - 1} A (n, m) x^{m + 1}}{(1 - x)^{n + 1}} per n \geq 0 .

Questo implica che 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ⁿ come combinazione lineare di numeri di Eulero con i coefficienti binomiali:

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

Da questa identità segue che

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

Un'altra curiosa identità è

\frac{e}{1 - e x} = \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 $(2 n - 1)!!$ . I numeri euleriani di seconda specie, indicati con $⟨ ⟨ \binom{n}{m} ⟩ ⟩$ , 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:

332211,

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

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

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

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

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

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

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

P_{n} (x) : = \sum_{m = 0}^{n} ⟨ ⟨ \binom{n}{m} ⟩ ⟩ x^{m}

e per essi vale la seguente relazione di ricorrenza:

P_{n + 1} (x) = (2 n x + 1) P_{n} (x) - x (x - 1) P_{n}^{'} (x)

con condizione iniziale

P_{0} (x) = 1 .

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

(x - 1)^{- 2 n - 2} P_{n + 1} (x) = {(x (1 - x)^{- 2 n - 1} P_{n} (x))}^{'}

tale che la funzione razionale

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

soddisfa la seguente relazione di ricorrenza:

u_{n + 1} = {(\frac{x}{1 - x} u_{n})}^{'}, u_{0} = 1,

da cui si ottengono i polinomi di Eulero nella forma P_n(x) = (1−x)²ⁿ 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)), è $(2 n - 1)!!$ .

Bibliografia

Voci correlate

Collegamenti esterni

Template:Cita web

Template:Portale

Numeri euleriani

Indice

Storia

Proprietà

Formula chiusa

Proprietà della somma

Identità

Numeri euleriani di seconda specie

Bibliografia

Voci correlate

Collegamenti esterni

Menu di navigazione

Numeri euleriani

Storia

Proprietà

Formula chiusa

Proprietà della somma

Identità

Numeri euleriani di seconda specie

Bibliografia

Voci correlate

Collegamenti esterni

Menu di navigazione

Ricerca