Funzione generatrice

In matematica una funzione generatrice è una serie formale di potenze i cui coefficienti costituiscono i componenti a_n di una successione indicizzata dai numeri naturali; spesso questa successione viene rappresentata efficacemente dalla funzione generatrice, specialmente quando per questa si trova qualche espressione sufficientemente maneggevole e significativa.

Sono studiati vari tipi di funzioni generatrici, come funzioni generatrici ordinarie, funzioni generatrici esponenziali, serie di Lambert, serie di Bell e serie di Dirichlet; qui di seguito ne sono date le definizioni e alcuni esempi. Ad ogni successione possono essere associate le funzioni generatrici di tutti i tipi. Quale può essere la particolare funzione generatrice che risulta più utile in un dato contesto dipende dalla natura della successione e dai dettagli del problema che si sta affrontando.

Le funzioni generatrici sono spesso individuate in una forma chiusa come funzioni di una variabile formale x. Talvolta risulta utile valutare una funzione generatrice per uno specifico valore reale o complesso della x. Tuttavia occorre tenere presente che le funzioni generatrici sono serie formali di potenze e per esse non viene necessariamente richiesta la convergenza per determinati valori attribuiti alla x.

Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra.

— Herbert Wilf, generatingfunctionology (1994)

La funzione generatrice ordinaria di una successione a_n è

${\displaystyle G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}.}$

Quando il termine funzione generatrice è usato senza qualificazione, di solito si intende che si tratta di una funzione generatrice ordinaria.

Se la successione a_n è una funzione di massa di probabilità di una variabile casuale discreta, allora la sua funzione generatrice ordinaria viene chiamata funzione generatrice di probabilità.

La funzione generatrice ordinaria può essere generalizzata a successioni relative a indici multipli. Ad esempio, la funzione generatrice ordinaria di una successione a_m,n (con n ed m numeri naturali) ha la forma

${\displaystyle G(a_{m,n};x,y)=\sum _{m,n=0}^{\infty }a_{m,n}x^{m}y^{n}.}$

La funzione generatrice esponenziale di una successione a_n è

${\displaystyle EG(a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}.}$

La serie di Lambert di una successione a_n è

${\displaystyle LG(a_{n};x)=\sum _{n=1}^{\infty }a_{n}{\frac {x^{n}}{1-x^{n}}}.}$

Si noti che in una serie di Lambert l'indice n ha come primo valore 1, non 0.

La serie di Bell associata ad una funzione aritmetica f(n) e ad un numero primo p è

${\displaystyle f_{p}(x):=\sum _{n=0}^{\infty }f(p^{n})x^{n}.}$

Le serie di Dirichlet sono in genere classificate come funzioni generatrici, anche se a rigore non sono serie formali di potenze. La funzione generatrice serie di Dirichlet di una successione a_n è

${\displaystyle DG(a_{n};s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}.}$

La funzione generatrice serie di Dirichlet è specialmente utile quando a_n è una funzione moltiplicativa, cioè quando possiede una espressione prodotto di Eulero in termini della serie di Bell della funzione

${\displaystyle DG(a_{n};s)=\prod _{p}f_{p}(p^{-s}).}$

Se a_n è un carattere di Dirichlet, allora la funzione generatrice con serie di Dirichlet viene chiamata serie L di Dirichlet.

La nozione di funzione generatrice può essere estesa a successioni di oggetti che non sono semplici numeri. Così, ad esempio, le sequenze polinomiali di tipo binomiale sono generate da

${\displaystyle e^{xf(t)}=\sum _{n=0}^{\infty }{p_{n}(x) \over n!}t^{n},}$

dove p_n(x) è una sequenza polinomiale e f(t) una funzione di una determinata forma. Le sequenza di Sheffer sono generate in un modo simile. Per maggiori informazioni su questo argomento, vedi la voce principale polinomi generalizzati di Appell.

Passiamo in rassegna le funzioni generatrici per la successione dei quadrati perfetti a_n = n².

Funzione generatrice ordinaria

${\displaystyle G(n^{2};x)=\sum _{n=0}^{\infty }n^{2}x^{n}={\frac {x(x+1)}{(1-x)^{3}}}.}$

Funzione generatrice esponenziale

${\displaystyle EG(n^{2};x)=\sum _{n=0}^{\infty }{\frac {n^{2}x^{n}}{n!}}=x(x+1)e^{x}.}$

Serie di Bell

${\displaystyle f_{p}(x)=\sum _{n=0}^{\infty }p^{2n}x^{n}={\frac {1}{1-p^{2}x}}.}$

Funzione generatrice con serie di Dirichlet

${\displaystyle DG(n^{2};s)=\sum _{n=1}^{\infty }{\frac {n^{2}}{n^{s}}}=\zeta (s-2).}$

Nell'informatica le funzioni generatrici sono molto utilizzate soprattutto per quanto concerne l'analisi degli algoritmi. Ad esempio si vuole determinare il numero di volte che un blocco di istruzioni all'interno di un costrutto iterativo viene eseguito.

CASO A

...
for (i=1; i<=n; i++)
{printf("ciao");}
...

In questo caso stampiamo la stringa ciao per iterazioni che vanno da 1 a n. Otteniamo così

${\displaystyle \sum _{i=1}^{n}1=n,}$

ipotizzando che la stampa della stringa ciao abbia costo uniforme.

CASO B

...
for (i=1; i<=n; i++)
for (j=1; j<=i; j++)
{printf("ciao");}
...

la stringa ciao viene stampata una volta ad ogni iterazione del ciclo più interno (j) ed i volte ad ogni iterazione del ciclo esterno (i). Complessivamente:

${\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{i}1=\sum _{i=1}^{n}i={\frac {n(n+1)}{2}},}$

ricordando la formula di Gauss.

In generale, avendo k cicli innestati ci si riconduce a calcolare una sommatoria della forma

${\displaystyle \sum _{i_{1}=1}^{n}\sum _{i_{2}=1}^{i_{1}}...\sum _{i_{k}=1}^{i_{k-1}}1.}$

CASO C

for (i=1; i<=n; i++)
for (j=1; j<=i; j++)
for (k=1; k<=j; k++)
{printf("ciao");}

${\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{i}\sum _{k=1}^{j}1=\sum _{i=1}^{n}\sum _{j=1}^{i}j=\sum _{i=1}^{n}{\frac {i(i+1)}{2}}.}$

Bisogna calcolare quest'ultima. Quindi:

${\displaystyle \sum _{i=1}^{n}{\frac {i(i+1)}{2}}={\frac {1}{2}}\left(\sum _{i=1}^{n}i^{2}+\sum _{i=1}^{n}i\right)={\frac {n(n+1)(2n+1)}{2\cdot 6}}+{\frac {n(n+1)}{2\cdot 2}}={\frac {n^{3}}{6}}+{\frac {n^{2}}{2}}+{\frac {n}{3}}.}$

Si possono costruire funzioni generatrici arricchendo la forma di funzioni generatrici più semplici. Ad esempio, iniziamo con

${\displaystyle G(1;x)=\sum _{n=0}^{\infty }x^{n}={\frac {1}{1-x}}}$

e sostituiamo ${\displaystyle x}$ con ${\displaystyle 2x}$; otteniamo

${\displaystyle G(1;2x)={\frac {1}{1-2x}}=1+(2x)+(2x)^{2}+\ldots +(2x)^{n}+\ldots =G(2^{n};x).}$

Lo stesso argomento in dettaglio: Numeri di Fibonacci.

Consideriamo il problema di trovare una formula chiusa per i numeri di Fibonacci f_n definiti da f₀ := 0, f₁ := 1 e f_n := f_n−1 + f_n−2 per n ≥ 2. Componiamo la funzione generatrice ordinaria

${\displaystyle f=\sum _{n\geq 0}f_{n}X^{n}}$

per questa successione. La funzione generatrice per la successione (f_n−1) è Xf e quella di (f_n−2) è X²f. Dalla relazione di ricorrenza si ricava quindi che la serie di potenze Xf + X²f ha gli stessi coefficienti della f ad esclusione dei primi due. Tenendo conto di questi si trova che

${\displaystyle f=Xf+X^{2}f+X.}$

Questo è il passo cruciale; Le relazioni di ricorrenza possono quasi sempre essere tradotte in equazioni per le funzioni generatrici. Risolvendo questa equazione per f otteniamo

${\displaystyle f={\frac {X}{1-X-X^{2}}}.}$

Il denominatore si può fattorizzare usando la sezione aurea φ₁ = (1 + √5)/2 e φ₂ = (1 − √5)/2; la tecnica della decomposizione in frazioni parziali porta a

${\displaystyle f={\frac {1/{\sqrt {5}}}{1-\varphi _{1}X}}-{\frac {1/{\sqrt {5}}}{1-\varphi _{2}X}}.}$

I due termini a destra sono la somma di due serie geometriche; confrontando i coefficienti dei termini di uguale grado si trova la formula esplicita

${\displaystyle f_{n}={\frac {1}{\sqrt {5}}}(\varphi _{1}^{n}-\varphi _{2}^{n}).}$

Le funzioni generatrici sono utilizzate per vari procedimenti.

• Trovare relazioni di ricorrenza per i componenti di successioni: la forma di una funzioni generatrice può suggerire una formula di ricorrenza.
• Trovare relazioni tra successioni: se le funzioni generatrici di due successioni hanno forme simili, probabilmente le stesse successioni sono in qualche relazione significativa.
• Esplorare il comportamento asintotico di successioni.
• Dimostrare identità concernenti successioni.
• Risolvere problemi di enumerazione in combinatoria.
• Valutare valori cui convergono date serie.

• Herbert S. Wilf (1994): generatingfunctionology (Second Edition). Academic Press. ISBN 0127519564. Per una versione liberamente scaricabile offerta da Herbert Wilf e dalla Academic Press, vedi la pagina web Download the book Generatingfunctionology

• Funzione generatrice dei momenti
• Funzione generatrice di probabilità
• Teorema di reciprocità di Stanley

• Funzione generatrice, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) Opere riguardanti Generating functions, su Open Library, Internet Archive.
• (EN) Eric W. Weisstein, Generating Function, su MathWorld, Wolfram Research.
• (EN) Generating function, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• Generating Functions, Power Indices and Coin Change, su cut-the-knot.org.
• Generatingfunctionology (PDF) (PDF), su math.upenn.edu.

V · D · M Successioni e Serie
Successioni di interi	Base Progressione aritmetica · Progressione geometrica · Progressione armonica · Progressione aritmetica · Numeri quadrati · Numeri cubici · Fattoriale · Potenze di 2 · Potenze di 3 · Potenze di 10 Avanzate Successione completa · Numeri di Fibonacci · Numeri figurati · Numeri ettagonali · Numeri esagonali · Numeri di Lucas · Numeri di Pell · Numeri pentagonali · Numero poligonale · Numero triangolare
Proprietà delle successioni	Successione di Cauchy · Successione monotona · Successione alternata
Proprietà delle serie	Tendenza Serie alternata · Serie convergente · Serie divergente · Serie telescopica Convergenza Convergenza incondizionata · Convergenza assoluta · Convergenza uniforme
Serie esplicite	Convergenti 1/2 − 1/4 + 1/8 − 1/16 + ⋯ · 1/2 + 1/4 + 1/8 + 1/16 + ⋯ · 1/4 + 1/16 + 1/64 + 1/256 + ⋯ · 1 + 1/2s+ 1/3s + ... (Riemann zeta) Divergenti 1 + 1 + 1 + 1 + ⋯ · 1 + 2 + 3 + 4 + ⋯ · 1 + 2 + 4 + 8 + ⋯ · 1 − 1 + 1 − 1 + ⋯ (Grandi) · a1 + (a1+d) + ⋯ · 1 − 2 + 3 − 4 + ⋯ · 1 − 2 + 4 − 8 + ⋯ · 1 + 1/2 + 1/3 + 1/4 + ⋯ (armonica) · 1 − 1 + 2 − 6 + 24 − 120 + ⋯ (fattoriale alternata) · 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ⋯ (inversi dei primi)
Tipi di serie	Serie di Taylor · Serie di potenze · Serie formale di potenze · Serie di Laurent · Serie di Puiseux · Serie di Dirichlet · Serie trigonometrica · Serie di Fourier · Serie generatrice
Serie Ipergeometrica	Serie ipergeometrica generalizzata · Funzione ipergeometrica di un argomento di matrice · Serie di Lauricella · Serie modulare · Serie ipergeometrica confluente · Serie theta

V · D · M Combinatoria
Orientamento generale	Combinatoria · Storia della combinatoria · Matematica discreta · Sezione 05-XX di MSC
Nozioni introduttive	Permutazioni · Disposizioni · Combinazioni · Coefficienti binomiali · Partizioni di interi · Partizioni di insiemi finiti - Identità combinatorie e biiezioni · Principio dei cassetti
Configurazioni	Quadrati latini · Quadrati magici · Disegni a blocchi · Geometrie finite · Matroidi - Tassellazioni · Polimini
Teoria dei grafi	Alberi · Cammini sui grafi (euleriani, hamiltoniani) · Connessione nei grafi - Grafi planari · Colorazione dei grafi e teorema dei quattro colori) · Ipergrafi · Grafi e gruppi · Digrafo · Flussi su grafi · Passeggiate aleatorie su grafi · Omomorfismo fra grafi · Algoritmi sui grafi
Combinatoria algebrica	Tavola di Young · Funzioni simmetriche - Serie formale di potenze · Funzioni generatrici · Polinomi ortogonali · Azioni di un gruppo su strutture combinatorie - Aspetti combinatorici dell'algebra commutativa
Altre aree	Calcolo umbrale (sequenze polinomiali di tipo binomiale · sequenze di Sheffer) - Combinatoria estremale

Portale Matematica: accedi alle voci di Teknopedia che trattano di matematica