Funzioni Generatrici: Guida Completa con Esercizi Risolti, Fibonacci e Applicazioni

 

Esercizio 1 (Livello: Facile) | La Sequenza di Fibonacci

Il Problema

In una popolazione ideale, il numero di coppie di conigli al mese [math]n[/math] segue la celebre successione di Fibonacci: [math]F_0 = 0[/math], [math]F_1 = 1[/math], e per ogni [math]n \ge 2[/math]:

[math]\displaystyle F_n = F_{n-1} + F_{n-2}[/math]

Determina la funzione generatrice ordinaria (FGO) definita come:

[math]\displaystyle G(x) = \sum_{n=0}^{\infty} F_n x^n[/math]

Utilizza la relazione di ricorrenza per ricavare l’espressione in forma chiusa di [math]G(x)[/math].

Risoluzione

Scriviamo esplicitamente la nostra funzione generatrice “srotolando” i primi termini della serie:

[math]\displaystyle G(x) = F_0 + F_1 x + F_2 x^2 + F_3 x^3 + \dots = \sum_{n=0}^{\infty} F_n x^n[/math]

Sappiamo che [math]F_0 = 0[/math] e [math]F_1 = 1[/math]. Sfruttiamo la relazione di ricorrenza per [math]n \ge 2[/math]. Moltiplichiamo l’intera equazione ricorrente per [math]x^n[/math] e sommiamo da [math]n = 2[/math] a [math]\infty[/math]:

[math]\displaystyle \sum_{n=2}^{\infty} F_n x^n = \sum_{n=2}^{\infty} F_{n-1} x^n + \sum_{n=2}^{\infty} F_{n-2} x^n[/math]

Ora dobbiamo ricondurre ciascuna di queste sommatorie a espressioni che contengano la nostra [math]G(x)[/math]:

Membro sinistro:

La somma parte da [math]n=2[/math], quindi mancano i primi due termini della serie completa:

[math]\displaystyle \sum_{n=2}^{\infty} F_n x^n = G(x) – F_0 – F_1 x = G(x) – x[/math]

Primo termine a destra:

Raccogliamo una [math]x[/math] per allineare l’indice della successione all’esponente della variabile:

[math]\displaystyle \sum_{n=2}^{\infty} F_{n-1} x^n = x \sum_{n=2}^{\infty} F_{n-1} x^{n-1} = x(G(x) – F_0) = x G(x)[/math]

Secondo termine a destra:

Raccogliamo [math]x^2[/math] per lo stesso motivo:

[math]\displaystyle \sum_{n=2}^{\infty} F_{n-2} x^n = x^2 \sum_{n=2}^{\infty} F_{n-2} x^{n-2} = x^2 G(x)[/math]

Sostituendo queste identità nell’equazione di partenza otteniamo:

[math]\displaystyle G(x) – x = x G(x) + x^2 G(x)[/math]

Isoliamo [math]G(x)[/math] raccogliendo i termini simili:

[math]\displaystyle G(x)(1 – x – x^2) = x[/math]

La forma chiusa della funzione generatrice ordinaria dei numeri di Fibonacci è dunque:

[math]\displaystyle G(x) = \frac{x}{1 – x – x^2}[/math]

 

Osservazione strategica:

Abbiamo trasformato una ricorrenza dinamica in una semplice equazione algebrica di primo grado. Notate come il denominatore [math]1 – x – x^2[/math] rifletta esattamente il polinomio caratteristico della ricorrenza, con i segni invertiti.

Dalla Formula alla Geometria

A prima vista questa figura sembra appartenere esclusivamente alla geometria.

In realtà nasce dalla stessa successione studiata poco fa mediante la funzione generatrice.

Ogni quadrato ha lato uguale a un numero di Fibonacci; la successione determina quindi l’intera costruzione geometrica.

La funzione generatrice

[math]\displaystyle G(x) = \frac{x}{1 – x – x^2}[/math]

rappresenta invece la “versione algebrica” della stessa informazione.

In altre parole, la figura e la funzione raccontano la stessa storia con due linguaggi differenti:

• la geometria mostra come cresce la successione;
• la funzione generatrice spiega perché cresce in quel modo.

Il ponte tra questi due mondi è la potenza delle funzioni generatrici: ciò che è visibile nello spazio può essere compreso nel tempo, e viceversa.

La spirale dei quadrati di Fibonacci è solo l’immagine più celebre di un principio universale: le strutture matematiche più profonde si manifestano simultaneamente in algebra, geometria e natura.

Mini-quiz

Quale proprietà delle funzioni generatrici abbiamo utilizzato per passare dalla sommatoria di [math]F_{n-1} x^n[/math] a [math]x G(x)[/math]?

Risposta:

Abbiamo applicato la proprietà di traslazione (o shift dell’indice). In termini formali, se [math]G(x) = \sum_{n=0}^{\infty} a_n x^n[/math], allora lo shift a destra di [math]k[/math] posizioni corrisponde a moltiplicare per [math]x^k[/math]: [math]\sum_{n=k}^{\infty} a_{n-k} x^n = x^k G(x)[/math]. Questo ci permette di “assorbire” i disallineamenti degli indici generati dalle equazioni alle differenze.

Esercizio 2 (Livello: Medio-Facile) | Distribuzione di Caramelle

Il Problema

In un negozio ci sono [math]n[/math] tipi di caramelle disponibili in quantità illimitata. Vuoi comporre un sacchetto che contenga esattamente [math]k[/math] caramelle. In quanti modi diversi puoi farlo, supponendo che l’ordine con cui inserisci le caramelle nel sacchetto non conti?

Trova il numero di soluzioni intere non negative dell’equazione:

[math]\displaystyle a_1 + a_2 + \dots + a_n = k \quad \text{con } a_i \ge 0[/math]

Risoluzione

Ogni singola variabile [math]a_i[/math] rappresenta il numero di caramelle del tipo [math]i[/math]-esimo che inseriamo nel sacchetto. Poiché non ci sono vincoli sulla quantità di ciascun tipo, la scelta per la singola variabile [math]a_i[/math] può essere rappresentata dalla funzione generatrice:

[math]\displaystyle \sum_{a_i=0}^{\infty} x^{a_i} = 1 + x + x^2 + x^3 + \dots = \frac{1}{1 – x}[/math]

Poiché le scelte per i diversi tipi di caramelle sono indipendenti, la funzione generatrice complessiva per l’intero vettore [math](a_1, \dots, a_n)[/math] è semplicemente il prodotto delle funzioni generatrici delle singole variabili:

[math]\displaystyle F(x) = \left( \frac{1}{1 – x} \right)^n = (1 – x)^{-n}[/math]

Il numero di modi per ottenere esattamente [math]k[/math] caramelle corrisponde al coefficiente del termine [math]x^k[/math] nello sviluppo in serie di Taylor di [math]F(x)[/math]. Usando il teorema del binomio generalizzato di Newton:

[math]\displaystyle (1 – x)^{-n} = \sum_{k=0}^{\infty} \binom{-n}{k} (-1)^k x^k = \sum_{k=0}^{\infty} \binom{n + k – 1}{k} x^k[/math]

Di conseguenza, estraendo il coefficiente [math][x^k][/math], troviamo la formula chiusa:

[math]\displaystyle \text{Numero di modi} = \binom{n + k – 1}{k} = \binom{n + k – 1}{n – 1}[/math]

Verifica con casi limite

• Per [math]n = 2, k = 3[/math]: [math]\binom{4}{3} = 4[/math]. Le soluzioni effettive sono: [math](0,3), (1,2), (2,1), (3,0)[/math]. Corretto.
• Per [math]n = 3, k = 2[/math]: [math]\binom{4}{2} = 6[/math]. Le soluzioni corrispondono alle combinazioni con ripetizione di 3 elementi presi a gruppi di 2. Corretto.

Osservazione strategica:

Il prodotto di funzioni generatrici equivale alla convoluzione delle rispettive successioni. Quando combiniamo oggetti indipendenti sommandone i pesi, l’algebra delle funzioni generatrici fa tutto il lavoro di calcolo combinatorio per noi tramite una semplice moltiplicazione di serie.

Mini-quiz

Perché la funzione generatrice di una singola variabile è [math]1/(1 – x)[/math] e non, ad esempio, un polinomio o una serie limitata?

Risposta:

La serie è infinita perché le variabili [math]a_i[/math] non hanno un limite superiore specificato nel testo del problema (quantità “illimitate”). Se il problema avesse imposto un limite massimo di caramelle per tipo (es. al massimo 2 caramelle per tipo), la funzione generatrice della singola variabile sarebbe stata un polinomio troncato: [math]1 + x + x^2[/math]. L’infinito della serie cattura l’assenza di vincoli superiori.

Esercizio 3 (Livello: Medio) | Successioni a Crescita Rapida e Fattoriali

Il Problema

Considera la successione [math]a_n = n![/math] per [math]n \ge 0[/math].

La funzione generatrice ordinaria [math]\sum_{n=0}^{\infty} n! x^n[/math] ha raggio di convergenza pari a zero (diverge ovunque tranne che in [math]x = 0[/math]). Per trattare successioni a crescita super-esponenziale si introduce la Funzione Generatrice Esponenziale (FGE):

[math]\displaystyle E(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}[/math]

Calcola la FGE della successione [math]a_n = n![/math].

Usa il risultato per calcolare la FGE della successione [math]b_n = n \cdot n![/math].

Risoluzione

1. FGE di [math]a_n = n![/math]

Sostituiamo direttamente il termine [math]a_n[/math] nella definizione di FGE:

[math]\displaystyle E(x) = \sum_{n=0}^{\infty} n! \frac{x^n}{n!} = \sum_{n=0}^{\infty} x^n = \frac{1}{1 – x}[/math]

La FGE della successione dei fattoriali è la classica serie geometrica, che converge assolutamente per [math]|x| < 1[/math].

2. FGE di [math]b_n = n \cdot n![/math]

Notiamo che la presenza del fattore [math]n[/math] davanti alla successione suggerisce l’uso dell’operatore di derivazione. Infatti, applicando l’operatore [math]x \frac{d}{dx}[/math] a una generica FGE:

[math]\displaystyle x \frac{d}{dx} E(x) = x \sum_{n=0}^{\infty} a_n \frac{n x^{n-1}}{n!} = \sum_{n=0}^{\infty} (n a_n) \frac{x^n}{n!}[/math]

Questo significa che moltiplicare il termine generale di una successione per [math]n[/math] equivale ad applicare l’operatore [math]x \frac{d}{dx}[/math] alla sua FGE. Ponendo [math]a_n = n![/math], abbiamo [math]b_n = n a_n[/math]. Calcoliamo quindi la derivata:

[math]\displaystyle E_b(x) = x \frac{d}{dx} \left( \frac{1}{1 – x} \right) = x \cdot \frac{1}{(1 – x)^2} = \frac{x}{(1 – x)^2}[/math]

Verifica di coerenza

Sviluppiamo in serie la funzione ottenuta per verificare se i coefficienti coincidono con quelli attesi:

[math]\displaystyle \frac{x}{(1 – x)^2} = x \sum_{n=1}^{\infty} n x^{n-1} = \sum_{n=0}^{\infty} n x^n[/math]

Nella definizione di FGE, il coefficiente di [math]\frac{x^n}{n!}[/math] deve essere [math]b_n[/math]. Riscriviamo la serie evidenziando questo termine:

[math]\displaystyle \sum_{n=0}^{\infty} n x^n = \sum_{n=0}^{\infty} (n \cdot n!) \frac{x^n}{n!}[/math]

Il coefficiente estratto è esattamente [math]b_n = n \cdot n![/math]. La soluzione è impeccabile.

Osservazione strategica:

Le funzioni generatrici esponenziali sono lo strumento d’elezione per problemi di combinatoria etichettata (strutture in cui l’ordine conta) e per domare successioni con crescite vertiginose. L’operatore [math]x \frac{d}{dx}[/math] è l’equivalente algebrico dell’azione combinatoria di “marcare” o “scegliere” un elemento distinto.

Mini-quiz

Qual è la differenza fondamentale, in termini di significato combinatorio, tra una FGO e una FGE? In quali contesti pratici l’una surclassa l’altra?

Risposta: La FGO (Ordinaria) associa la successione alla serie [math]\sum a_n x^n[/math]. È ideale per strutture non etichettate (oggetti indistinguibili, come le caramelle dell’Esercizio 2) e per combinazioni semplici. La FGE (Esponenziale) associa la successione alla serie [math]\sum a_n \frac{x^n}{n!}[/math]. È lo strumento principe per strutture etichettate (grafi orientati, permutazioni, parole) dove l’ordine e l’identità dei singoli elementi contano. Dal punto di vista analitico, il fattoriale a denominatore garantisce la convergenza anche per successioni a crescita esplosiva.

---

Analisi Applicativa

Per comprendere a fondo perché questi tre esercizi rappresentino pietre miliari nello studio delle funzioni generatrici, analizziamoli da una prospettiva applicativa avanzata.

Esercizio 1: Il legame tra Singolarità e Comportamento Asintotico

L’aspetto più straordinario dell’Esercizio 1 non è la frazione [math]G(x) = \frac{x}{1-x-x^2}[/math] in sé, ma ciò che essa rivela sulla crescita a lungo termine dei numeri di Fibonacci.

In analisi complessa, il comportamento asintotico dei coefficienti di una serie di potenze è interamente governato dalle singolarità (i poli) della sua funzione generatrice che si trovano più vicine all’origine.

Se calcoliamo le radici del denominatore [math]1 – x – x^2 = 0[/math], otteniamo due poli semplici:

[math]\displaystyle x_1 = \frac{-1 + \sqrt{5}}{2} = \frac{1}{\phi} \approx 0.618, \quad x_2 = \frac{-1 – \sqrt{5}}{2} = -\phi \approx -1.618[/math]

Dove [math]\phi[/math] è la sezione aurea. Poiché [math]x_1[/math] è il polo più vicino all’origine, esso domina lo sviluppo asintotico. Applicando la decomposizione in fratti semplici a [math]G(x)[/math], possiamo estrarre direttamente la Formula di Binet:

[math]\displaystyle F_n = \frac{1}{\sqrt{5}} \left( \phi^n – \psi^n \right)[/math]

Questo esercizio ci insegna che per conoscere il comportamento all’infinito di una successione discreta non serve calcolare miliardi di termini: basta mappare i poli della sua funzione generatrice sul piano complesso.

Esercizio 2: Dalla Combinatoria alla Meccanica Statistica

Il problema della distribuzione delle caramelle è formalmente noto in combinatoria come metodo Stars and Bars (stelle e barre). Tuttavia, ha un’applicazione fisica di importanza colossale: la statistica di Bose-Einstein.

In fisica quantistica, i bosoni (come i fotoni) sono particelle indistinguibili che possono occupare diversi stati energetici (che sono invece distinguibili). Se abbiamo [math]k[/math] bosoni da distribuire in [math]n[/math] livelli energetici senza alcun limite di occupazione per livello, il numero di microstati possibili è calcolato esattamente dalla nostra funzione generatrice:

[math]\displaystyle \binom{n + k – 1}{k}[/math]

Moltiplicare le funzioni generatrici delle singole variabili equivale a imporre la conservazione del numero totale di particelle nel sistema, un concetto cardine della fisica dei sistemi a molti corpi.

Esercizio 3: L’Operatore di Puntamento e la Combinatoria Analitica

L’Esercizio 3 ci introduce alla bellezza della Combinatoria Analitica.

L’operatore [math]x \frac{d}{dx}[/math] non è semplicemente un trucco algebrico per far comparire una [math]n[/math] davanti ai coefficienti; ha un significato combinatorio profondo chiamato puntamento (pointing o marking).

Se abbiamo una classe combinatoria di strutture etichettate di dimensione [math]n[/math], applicare l’operatore [math]x \frac{d}{dx}[/math] alla sua funzione generatrice esponenziale equivale a creare una nuova classe di strutture in cui uno degli [math]n[/math] elementi viene “scelto” o “evidenziato” come speciale. Poiché ci sono esattamente [math]n[/math] modi per scegliere l’elemento speciale, la nuova successione avrà come termine generale [math]b_n = n \cdot a_n[/math].

Questo esercizio mostra come le operazioni di calcolo infinitesimale (derivazione) corrispondano in modo biunivoco a trasformazioni strutturali sui dati reali.

---

Il Gran Finale: Il Problema del Resto (L’effetto “Wow”)

Per chiudere in bellezza, mettiamo da parte le successioni teoriche e affrontiamo un problema pratico che apparentemente sembra un incubo combinatorio.

La sfida: In quanti modi diversi possiamo ottenere esattamente 100 € utilizzando esclusivamente tagli da 1 €, 2 €, 5 €, 10 €, 20 € e 50 €?

Se provassi a risolverlo a mano, ti ritroveresti intrappolato in un labirinto di ramificazioni. Potresti usare due banconote da 50 €, oppure una da 50 €, due da 20 € e una da 10 €, oppure cento monete da 1 €… Elencare tutte le possibilità senza dimenticarne nessuna o senza fare doppi conteggi è un compito titanico.

La magia algebrica

Le funzioni generatrici risolvono questo problema con una naturalezza disarmante.

Costruiamo una funzione generatrice per ogni singolo taglio:

I tagli da 1 € possono contribuire con [math]0, 1, 2, 3, \dots[/math] euro.

La loro funzione è:

[math]\displaystyle 1 + x + x^2 + x^3 + \cdots = \frac{1}{1 – x}[/math]

I tagli da 2 € possono contribuire solo con multipli di 2 ([math]0, 2, 4, 6, \dots[/math] euro).

La loro funzione è:

[math]\displaystyle 1 + x^2 + x^4 + x^6 + \cdots = \frac{1}{1 – x^2}[/math]

I tagli da 5 € contribuiscono con multipli di 5 ([math]0, 5, 10, 15, \dots[/math] euro):

[math]\displaystyle 1 + x^5 + x^{10} + x^{15} + \cdots = \frac{1}{1 – x^5}[/math]

E così via per tutti gli altri tagli (10, 20, 50).

Ora, per lo stesso principio di indipendenza che abbiamo visto nell’Esercizio 2 (la moltiplicazione delle scelte equivale al prodotto delle serie), ci basta moltiplicare tutte queste frazioni insieme.

La funzione generatrice dell’intero sistema è:

[math]\displaystyle G(x) = \frac{1}{(1 – x)(1 – x^2)(1 – x^5)(1 – x^{10})(1 – x^{20})(1 – x^{50})}[/math]

La risposta in un coefficiente

Perché questa formula apparentemente astratta risolve il problema?

Perché quando andiamo a sviluppare questo prodotto di serie infinite, ogni singolo termine che otteniamo è della forma [math]x^{\text{somma}}[/math].

L’esponente della [math]x[/math] rappresenta il valore totale del resto, mentre il coefficiente davanti alla [math]x^{100}[/math] rappresenterà esattamente il numero di modi possibili per combinare i diversi tagli e ottenere 100 €.

Se chiediamo a un software di calcolo simbolico (o a un semplice script Python) di estrarre il coefficiente di [math]x^{100}[/math] nello sviluppo di Taylor di [math]G(x)[/math], otteniamo istantaneamente la risposta:

[math]\displaystyle \text{Numero di modi} = [x^{100}] G(x) = 4562[/math]

Esistono esattamente 4.562 modi diversi per cambiare una banconota da 100 € con quei tagli.

Questo è il vero potere delle funzioni generatrici:

non abbiamo dovuto contare nulla manualmente. Abbiamo semplicemente tradotto le regole del mondo reale (i valori delle monete) in una struttura algebrica, e lasciato che le leggi formali dell’algebra facessero tutto il lavoro pesante per noi.

Dalla Teoria al Codice: Estrazione in Python

Perché questa formula apparentemente astratta risolve il problema?

Perché quando andiamo a sviluppare questo prodotto di serie infinite, ogni singolo termine che otteniamo è della forma [math]x^{\text{somma}}[/math]. L’esponente della [math]x[/math] rappresenta il valore totale del resto, mentre il coefficiente davanti alla [math]x^{100}[/math] rappresenterà esattamente il numero di modi possibili per combinare i diversi tagli e ottenere 100 €.

Non dobbiamo calcolarlo a mano. Possiamo sfruttare Python e la libreria sympy per espandere questa funzione e farci restituire proprio il coefficiente che cerchiamo.

Python

import sympy as sp

# Definiamo la variabile simbolica
x = sp.Symbol('x')

# Tagli delle monete/banconote in euro
tagli = [1, 2, 5, 10, 20, 50]
obiettivo = 100

# Costruiamo la funzione generatrice troncando lo sviluppo
# all'esponente dell'obiettivo per ottimizzare il calcolo
G = 1
for t in tagli:
    # Usiamo lo sviluppo in serie troncato per (1 - x^t)^(-1)
    # limitando i termini al valore obiettivo + 1
    serie_taglio = sum(x**(i*t) for i in range(obiettivo // t + 1))
    G = (G * serie_taglio).expand()

# Estraiamo il coefficiente di x^100
modi = G.coeff(x, obiettivo)

print(f"Esistono esattamente {modi} modi per ottenere {obiettivo} €")

Output:

Esistono esattamente 4562 modi per ottenere 100 €

Esistono esattamente 4.562 modi diversi per cambiare una banconota da 100 € con quei tagli.

Questo è il vero potere delle funzioni generatrici: non abbiamo dovuto contare nulla manualmente né scrivere complicati algoritmi ricorsivi. Abbiamo semplicemente tradotto le regole del mondo reale in una struttura algebrica, e lasciato che la matematica facesse il resto.