Apri il menu principale

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:

I polinomi di Eulero sono definiti dalla funzione generatrice esponenziale:

Essi possono essere calcolati attraverso la seguente formula ricorsiva:

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

Le notazioni per questi numeri sono A(n, m), E(n, m) e .

Essi non vanno confusi con i numeri di Eulero.

StoriaModifica

Nel 1755 Eulero si occupò, nel libro Institutiones calculi differentialis, dei polinomi α1(x) = 1, α2(x) = x + 1, α3(x) = x2 + 4x + 1, ecc. (vedi immagine a fianco). Tali polinomi sono una variante di quelli che oggi sono chiamati polinomi di Eulero An(x).

ProprietàModifica

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). Ne esiste anche una sola con n − 1 valori maggiori del precedente; è la permutazione (1, 2, 3, ..., n). Perciò, A(n, 0) e A(n, n − 1) sono uniche 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

 

Da cui, ad esempio:

 

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 è  .

Formula chiusaModifica

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

 

Proprietà della sommaModifica

È 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

 

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

 

Altre sommatorie interessanti per i numeri di Eulero sono:

 
 

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

IdentitàModifica

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

 

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

 

Da questa identità segue che

 

Un'altra curiosa identità è

 

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

Numeri euleriani di seconda specieModifica

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  . I numeri euleriani di seconda specie, indicati con  , 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:

 
 
 

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

 

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

 

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

 

e per essi vale la seguente relazione di ricorrenza:

 

con condizione iniziale

 

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

 

tale che la funzione razionale

 

soddisfa la seguente relazione di ricorrenza:

 

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

BibliografiaModifica

  • (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 correlateModifica

Collegamenti esterniModifica

  • (EN) Euler-matrix (PDF), su go.helms-net.de. URL consultato il 7 gennaio 2017.
  Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica