Dopo aver introdotto le funzioni generatrici ordinarie in un precedente articolo (link), studiamo ora le proprietà delle funzioni generatrici esponenziali e presentiamo alcune applicazioni importanti.
1) Le funzioni generatrici esponenziali
Definizione 1.1
Data una successione di numeri reali \(\{a_{0},a_{1},a_{2}, \cdots \}\), si chiama funzione generatrice esponenziale (EGF – exponential generating function) la seguente serie:
È utile ricordare lo sviluppo in serie di Taylor-McLaurin di alcune funzioni importanti in questo contesto:
\[ \begin{split} e^{x}&=1+x+ \frac{x^{2}}{2!}+ \frac{x^{3}}{3!}+ \cdots \\ \sin(x)&= x-\frac{x^{3}}{3!}+\frac{x^{5}}{5!}- \cdots \\ \cos(x)&=1- \frac{x^{2}}{2!}+\frac{x^{4}}{4!}- \cdots \\ \sinh(x)&=\frac{e^{x}-e^{-x}}{2} = x+\frac{x^{3}}{3!}+\frac{x^{5}}{5!}+ \cdots \\ \cosh(x)&=\frac{e^{x}+e^{-x}}{2} = 1+ \frac{x^{2}}{2!}+\frac{x^{4}}{4!}+ \cdots \\ \end{split} \]La costante \(e=2,718 \cdots\) è la costante di Eulero-Mascheroni, base dei logaritmi naturali.
Esempio 1.1
La funzione generatrice esponenziale della successione \(\{1,1,1, \cdots \}\) è la funzione \(e^{x}\).
Esercizio 1.1
Trovare la funzione generatrice della successione \(\{1,2,4,8, \cdots \}\).
Risposta: [\(e^{2x}\)]
Esercizio 1.2
Trovare la funzione generatrice per la successione \(a_{n}=n!\), che come è noto rappresenta il numero delle permutazioni di \(n\) oggetti.
Risposta: [\((1-x)^{-1}\)]
Esercizio 1.3
Data la successione \(a_{n}=3n\) trovare la funzione generatrice ordinaria \(F(x)\) e la funzione generatrice esponenziale \(E(x)\).
Risposta: \(F(x) = \frac{3x}{(1-x)^{2}}, E(x)=3x e^{x}\)
Esercizio 1.4
Trovare la funzione generatrice esponenziale per la successione \(a_{n}=k^{n}\), con \(k\) fissato.
R:[\(F(x)=e^{kx}\)]
2) Operazioni con le funzioni generatrici esponenziali
Siano date due funzioni generatrici esponenziali: \(F(x)= \sum_{k=0}^{\infty}a_{n}\frac{x^{n}}{n!}\) e \(G(x)= \sum_{k=0}^{\infty}b_{n}\frac{x^{n}}{n!}\). Possiamo definire le seguenti operazioni:
2.1) Addizione
\[ F(x) + G(x) = \sum_{k=0}^{\infty}(a_{n}+b_{n})\frac{x^{n}}{n!} \]2.2) Moltiplicazione per un numero reale
\[ \alpha F(x) = \sum_{k=0}^{\infty}\alpha a_{n}\frac{x^{n}}{n!} \]2.3) Derivata
\[ \frac{d F(x)}{dx} = \sum_{k=1}^{\infty}a_{k}\frac{x^{k-1}}{(k-1)!} \]Quindi la derivata è la funzione generatrice esponenziale della successione \(\{a_{1},a_{2}, \cdots \}\), cioè equivale ad uno shift a sinistra.
2.4) Integrazione
\[ \int_{0}^{x} F(t) dt = \sum_{k=0}^{\infty}a_{k}\frac{x^{k+1}}{(k+1)!} \]Quindi l’integrale è la funzione generatrice esponenziale della successione \(\{0,a_{0},a_{1},a_{2}, \cdots \}\), cioè equivale ad uno shift a destra.
2.5) Moltiplicazione
\[ \begin{split} F(x) \cdot G(x) = \sum_{k=0}^{\infty}c_{n}\frac{x^{n}}{n!} \\ c_{n}= \sum_{k=0}^{n}\binom{n}{k}a_{k}b_{n-k} \end{split} \]Ricordiamo che nel caso del prodotto di due funzioni generatrici ordinarie il coefficiente vale \(c_{k}=\sum_{k=0}^{n}a_{k}b_{n-k}\).
3) Alcuni esempi
Le funzioni generatrici esponenziali sono utilizzate nei problemi equivalenti al calcolo delle distribuzioni di oggetti etichettati (leveled sets) in un insieme di scatole. La proprietà che le rende utili è la seguente:
\[ \frac{x^{m}}{m!} \frac{x^{n}}{n!} = \binom{n+m}{m}\frac{x^{m+n}}{(m+n)!} \]Ad esempio sono utilizzate nello studio delle partizioni di un insieme, in cui dato un insieme di \(n\) elementi si deve determinare il numero dei possibili modi di strutturare l’insieme disponendo gli elementi in blocchi opportuni. Nei problemi di permutazioni si deve disporre gli elementi in un dato ordine.
Il coefficiente \(a_{n}\) della serie può essere considerato come il numero di strutture presenti in un insieme di \(n\) elementi. È utile individuare le funzioni generatrici esponenziali relative a strutture base; queste soluzioni sono i blocchi per costruire le soluzioni dei problemi più complessi.
La struttura base più semplice su un insieme di \(n\) elementi è quella di essere un insieme. In questo caso \(a_{n}=1\) per ogni valore di \(n\), in quanto su un insieme di \(n\) elementi esiste solo una struttura di questo tipo. La funzione generatrice esponenziale in questo caso è:
Possiamo ottenere altre funzioni generatrici esponenziali imponendo dei vincoli sulla dimensione dell’insieme:
- insieme vuoto: \(F(x)=1\)
- insieme non vuoto: \(F(x)= e^{x}-1\)
- insieme con numero pari di elementi: \(F(x)=\frac{e^{x}+e^{-x}}{2}\)
- insieme con numero dispari di elementi: \(F(x)=\frac{e^{x}-e^{-x}}{2}\)
Esercizio 3.1 – Conteggio di parole
Calcolare quante parole di \(n\) lettere possono essere formate utilizzando le tre lettere dell’insieme \(\{a,b,c\}\), con un numero dispari sia di \(a\) sia di \(b\).
Soluzione
Naturalmente le parole cambiano in funzione delle diverse posizioni delle lettere. In questo caso quindi gli oggetti etichettati sono le diverse posizioni nella sequenza di lettere. Ogni parola può essere rappresentata con una partizione ordinata composta da tre insiemi: \(P_{a},P_{b},P_{c}\), ognuno dei quali contiene le posizioni nelle quali si trova la parola corrispondente. Le condizioni dell’esercizio in esame impongono che il numero degli elementi dell’insieme \(P_{a}\) sia dispari. La funzione generatrice per la lettera \(a\) è quindi
La stessa formula vale per la lettera \(b\). La lettera \(c\) non ha vincoli e quindi la sua funzione generatrice esponenziale è semplicemente \(e^{x}\). La funzione generatrice per il numero delle parole compatibili con i vincoli del problema si ottiene moltiplicando le singole funzioni generatrici:
\[ \begin{split} \left(\frac{e^{x}- e^{-x}}{2}\right)^{2} e^{x}= \frac{e^{3x}-2e^{x}+e^{-x}}{4}= \\ = \sum_{n=0}^{\infty}\left(\frac{3^{n}-2 +(-1)^{n}}{4}\right)\frac{x^{n}}{n!} \end{split} \]Esercizio 3.2
Calcolare il numero delle diverse parole di \(n\) lettere, utilizzando le lettere dell’insieme \(\{a,b,c,d\}\), con il vincolo che ogni parola deve contenere almeno due lettere \(a\).
Soluzione
In questo caso la funzione generatrice è la seguente:
Il numero cercato è quindi il coefficiente di \(\frac{x^{n}}{n!}\) nello sviluppo della funzione \(F(x)\).
Esercizio 3.3
Calcolare il quanti modi è possibile mettere 10 persone in tre stanze, con almeno una persona in ogni stanza.
Soluzione
La funzione generatrice del problema è \((e^{x}-1)^{3}\). Dobbiamo trovare il coefficiente di \(\frac{x^{10}}{10!}\). Per questo prima svolgiamo il cubo del binomio:
Quindi utilizziamo le espansioni in serie dei singoli termini e sommiamo i coefficienti relativi ad ogni esponente. Il coefficiente relativo a \(\frac{x^{10}}{10!}\) risulta \((3^{10}- 3(2^{10}) +3)\).
Esercizio 3.4
Calcolare il numero di modi, indicato con \(a(n,m)\), in cui è possibile distribuire \(n\) palline in \(m\) scatole diverse, con almeno una pallina in ogni scatola.
Soluzione
In modo simile agli esercizi precedenti, la funzione generatrice esponenziale è la seguente:
Utilizzando il teorema del binomio di Newton abbiamo:
\[ F(x)=(e^{x}-1)^{m}=e^{mx}-\binom{m}{1}e^{(m-1)x}+ \cdots + (-1)^{m} \]Quindi la soluzione è:
\[ a(n,m)= m^{n}-\binom{m}{1}(m-1)^{n}+ \cdots + (-1)^{m-1}\binom{m}{m-1} \]4) Conteggio dei derangement
Un derangement è una permutazione di \(\{1,2, \cdots ,n\}\) senza alcun punto fisso. Il numero dei derangement viene chiamato anche sottofattoriale (subfactorial) e indicato con !n.
Il problema del calcolo del numero dei derangement venne proposto da Pierre de Montmort nel 1708 e risolto dallo stesso nel 1713.
Ad esempio i derangement dell’insieme \(\{1,2,3\}\) sono:
Mentre i derangement dell’insieme \(\{1,2,3,4\}\) sono:
\[ \begin{gathered} (2,1,4,3), (2,3,4,1), (2,4,1,3), (3,1,4,2), (3,4,1,2), \\ (3,4,2,1), (4,1,2,3), (4,3,1,2), (4,3,2,1) \end{gathered} \]Esercizio 4.1
Calcolare il numero totale dei derangement nel gruppo simmetrico \(S_{n}\) che contiene il totale delle \(n!\) permutazioni.
Soluzione
Il numero di permutazioni che fissano \(k\) punti è \((n-k)!\). Quindi per il principio di inclusione-esclusione (vedi link) abbiamo:
La sommatoria è lo sviluppo iniziale di McLaurin-Taylor della funzione esponenziale \(e^{x}\) calcolata nel punto \(x=-1\). Si tratta di una serie alternante e quindi si ha la seguente stima dell’errore:
\[ D(n) – \frac{n!}{e} Esercizio 4.2Dimostrare le seguenti equazioni di ricorrenza: \[ \begin{split} D_{n}=(n-1) (D_{n-1}+ D_{n-2}) \\ D_{n}=nD_{n-1}+ (-1)^{n} \quad \text{\( n\ge 2 \)} \\ \end{split} \]
dove \(D(1)=0,D(2)=1\).
Esercizio 4.3
Trovare la funzione generatrice per il numero di permutazioni di \(n\) oggetti senza punti fissi, indicato con \(D_{n}\).
Soluzione
Ogni permutazione può essere vista come il prodotto di un derangement e di una permutazione identica. Consideriamo queste funzioni generatrici:
Applicando il teorema del prodotto del paragrafo precedente abbiamo \( P(x)=I(x)D(X)\) e quindi
\[ D(X) = \frac{e^{-x}}{1-x} \]5) I numeri di Bernoulli
La definizione dei numeri di Bernoulli può essere data direttamente mediante la funzione generatrice esponenziale:
\[ F(x)=\sum_{k=0}^{\infty}B_{n}\frac{x^{n}}{n!}= \frac {x}{e^{x}-1} \]Esercizio 5.1
Dimostrare la seguente relazione:
Esercizio 5.2
Utilizzando l’esercizio precedente dimostrare:
Esercizio 5.3
Dimostrare la seguente formula:
Suggerimento
Partire dalla seguente identità \(x = (e^{x}-1)F(x)\).
La formula dell’esercizio precedente può anche essere scritta nel seguente modo:
\[ \sum_{k=0}^{n-1}\binom{n}{k}B_{k}=[n=1] \]Dove \([n=1]\) è la parentesi di Iverson, che vale \(1\) se la condizione dentro le parentesi quadrata è vera, e vale \(0\) altrimenti.
5.1) Applicazione alla somma di potenze
I numeri di Bernoulli hanno importanti applicazioni nella teoria dei numeri. Introduciamo la seguente definizione:
\[ S_{m}(n)= 1^{m}+2^{m}+ \cdots + (n-1)^{m} \]Vale il seguente teorema.
Teorema 5.1
\[ S_{m}(n)=\sum_{k=0}^{m}\binom{m}{k}B_{m-k}\frac{n^{k+1}}{k+1} \]Ad esempio:
\[ \begin{split} 1+2+ \cdots + (n-1)&=\frac{1}{2}n(n-1) \\ 1^{2} + 2^{2}+ \cdots + (n-1)^{2}&= \frac{1}{6}n(n-1)(2n-1) \\ 1^{3} + 2^{3}+ \cdots + (n-1)^{3}&= \frac{1}{4}(n^{4}-2n^{3}+n^{2}) \\ \end{split} \]Dimostrazione
Definiamo \(G(t)=\sum_{k=0}^{n-1}e^{kt}\). Tenendo conto dello sviluppo in serie della funzione \(e^{kt}=\sum_{m=0}^{\infty} k^{m}\frac{ t^{m}}{m!}\), e invertendo l’ordine delle somme, otteniamo la seguente formula:
D’altra parte utilizzando la somma geometrica:
\[ G(t)= \frac{e^{nt}-1}{e^{t}-1}=\frac{e^{nt-1}}{t}F(t) \]dove \(F(t)\) è la funzione generatrice dei numeri di Bernoulli. Infine possiamo scrivere la seguente relazione, che ci permette di dimostrare il teorema, confrontando i coefficienti delle stesse potenze:
\[ G(t)= \left(\sum_{k=0}^{\infty}n^{k+1}\frac{t^{k}}{(k+1)!}\right) \left(\sum_{i=0}^{\infty}B_{i} \frac{t^{i}}{i!}\right) \]6) I numeri di Stirling
In questo paragrafo introduciamo i numeri di Stirling, che hanno applicazioni in molti settori della matematica. Per uno studio approfondito vedere l’ottimo testo [1].
6.1) Numeri di Stirling di prima specie
Il numero di Stirling di prima specie con segno \(s(n,m)\) è il coefficiente di \(x^{m}\) nel polinomio seguente \((x)_{n}\), definito per \(n \ge 1\):
\[ (x)_{n}=x(x-1) \cdots (x-n+1) \]Nel caso \(n=0\) si pone \((x)_{0}=1\). Il polinomio \((x)_{n}\) viene chiamato il fattoriale decrescente (falling factorial). Il simbolo \((x)_{n}\) è stato introdotto da Leo August Pochhammer (1841-1920). È molto comune anche la notazione di Donald Knuth \(x^ {\underset{-}{n}}\).
Quindi i numeri di Stirling di prima specie sono generati dalla seguente funzione generatrice ordinaria:
Naturalmente \(s(n,k)=0\) se \(k >n\). Per convenzione si pone \(s(0,0)=1\).
Dato un insieme \(X=\{1,2,3, \cdots,n\}\), ricordiamo che una permutazione è una funzione biunivoca dell’insieme in se stesso. Ovviamente il numero delle distinte permutazioni è \(n!\). Ogni permutazione può essere scritta come il prodotto di cicli distinti. Per un ripasso di questi concetti vedere [2], oppure vedi articolo in questo blog (link).
I numeri \(s(n,m)\) possono essere sia positivi sia negativi, e sono anche chiamati numeri di Stirling di prima specie con segno.
Il valore assoluto di \(s(n,m)\), indicato con il simbolo \(\displaystyle{n\brack m}\), ha un importante significato combinatorio: rappresenta il numero di permutazioni di \(n\) lettere con esattamente \(m\) cicli.
Ad esempio \(\displaystyle{ 3 \brack 2}=3\) poiché le permutazioni con \(2\) cicli sono le seguenti:
Esercizio 6.1
Dimostrare che \(\displaystyle{ 4 \brack 2}=11\).
Esercizio 6.2
Dimostrare la seguente relazione:
Esercizio 6.3
Dimostrare la seguente formula:
Suggerimento
Inoltre ricordare che vale il seguente sviluppo in serie della funzione logaritmo naturale, valido per \( -1 <x \le 1\):
La funzione \(\ln (\frac{1}{1-x})\) è la generatrice esponenziale del numero dei cicli di lunghezza \(n\). Infatti il numero dei cicli di lunghezza \(n\) è uguale a \((n-1)!\).
Esercizio 6.4
Dimostrare che la funzione generatrice esponenziale \(G(x,k)\) dei numeri di Stirling di prima specie senza segno è:
Suggerimento
Poniamo \(G(x,k)= \sum_{n=0}^{\infty}\displaystyle{ n\brack k} \frac{x^{n}}{n!}\). Moltiplicando la relazione dell’esercizio 6.2 per \(\frac{x^{n}}{n!}\) otteniamo la seguente relazione:
Osserviamo che \(G(x,0)=1\). Quindi otteniamo il risultato voluto per induzione, ricordando la seguente formula:
\[ \frac{d \ln^{k+1}(\frac{1}{1-x}) }{dx}= (k+1) \frac{\ln^{k}(\frac{1}{1-x})}{1-x} \]6.2) Numeri di Stirling di seconda specie
Il numero di Stirling di seconda specie \({n \brace m}\) è il coefficiente di \((x)_{m}\) nel monomio \(x^{n}\):
\[ x^{n}= \sum_{m=0}^{n}{n\brace m}(x)_{m} \]Viene indicato con \(S(n,m)\) oppure con il simbolo \({n \brace m}\).
Esempio 6.2
\[ x^{4}= (x)_{4}+ 6(x)_{3}+ 7(x)_{2}+ (x)_{1} \]Dal punto di vista combinatorio si può dimostrare che il numero di Stirling \({n \brace k}\) rappresenta il numero di partizioni dell’insieme \(\{1,2, \cdots,n\}\) in \(k\) sottoinsiemi disgiunti non vuoti.
Esercizio 6.5
Calcolare il numero di Stirling \(\displaystyle{4 \brace 2}\).
Soluzione
Dall’esempio 6.2 già sappiamo che il valore è uguale a \(7\). Tuttavia calcoliamolo nuovamente in base al significato combinatorio. Le partizioni dell’insieme \(\{a,b,c,d\}\) in sottoinsiemi non vuoti sono le seguenti:
({a, b, c}, {d}), ({a, b, d}, {c}), ({a, c, d}, {b}), ({b, c, d}, {a}),({a, b}, {c, d}), ({a, c}, {b, d}), ({a, d}, {b, c}).
Quindi come previsto \({4 \brace 2}=7\).
Esercizio 6.6
\[ {n+1 \brace k}= {n \brace k-1} + k{n \brace k} \]dove abbiamo posto \({n \brace n}=1\),\({n \brace k}=0\) se \(k \le 0, k \ge n+1\).
Esercizio 6.7
Dimostrare che la funzione generatrice dei numeri di Stirling di seconda specie è la seguente:
Soluzione
In base alla definizione il numero dei modi in cui si possono mettere \(n\) palline distinte in \(r\) scatole distinte è \(N(n,r)= r!{n \brace r}\), poiché ad ogni disposizione in scatole non distinte, corrispondono \(r!\) disposizioni in scatole distinte. La funzione generatrice associata è
Ora nel caso \(r=1\) c’è una sola partizione in una sola scatola e quindi
\[ G_{1}(x)=\sum_{n=1}^{\infty}\frac{x^{n}}{n!}=e^{x}-1 \]Possiamo utilizzare la formula ricorsiva \(G_{r}(x)=G_{1}(x) G_{r-1}(x)\) e quindi
\[ G_{r}(x)=(e^{x}-1)^{r} \]La funzione generatrice esponenziale dei numeri di Stirling di seconda specie è quindi:
\[ F(x,r)= \sum_{n=0}^{\infty}{n \brace r} \frac{x^{n}}{n!}=\frac {(e^{x}-1)^{r}}{r!} \]Esercizio 6.8
Dimostrare le seguenti relazioni:
dove il simbolo \(\delta_{m,n}\) indica la funzione delta di Kronecker:
\[ \delta_{m,n} = \begin{cases} 0 \text{ se \(n \neq m\)} \\ 1 \text{ se \(n=m\)} \\ \end{cases} \]Suggerimento
Utilizzare le definizioni di \(s(n,m)\) e \(S(n,m)\) espandendo il fattoriale decrescente e uguagliando i coefficienti delle potenze.
Conclusione
Le funzioni generatrici hanno un ruolo importante, in quanto combinano insieme la matematica discreta e quella continua. I potenti metodi dell’analisi matematica costituiscono uno strumento fondamentale per risolvere molti problemi di natura combinatoria, che altrimenti sarebbero molto difficili da risolvere.
Bibliografia
[1]Graham, Knuth, Patashnik – Concrete Mathematics: A Foundation for Computer Science (Addison-Wesley)
[2]Harris – Combinatorics and Graph Theory (Springer)
3 commenti
Pietro · 17 Marzo 2024 alle 3:54 PM
Ciao,
grazie per questo articolo che ho trovato molto interessante.
Non capisco un passaggio: nella soluzione all’esercizio 6.7 da dove ricavi la formula ricorsiva?
Grazie.
Saluti
Pietro
gameludere · 29 Marzo 2024 alle 7:38 PM
Ciao Pietro! Perdonami se ti rispondo solo ora, ma mi capita di stare lontano dal sito per parecchio tempo a volte. Se dovessi aver già trovato la risposta, le informazioni che seguono saranno comunque utili a chi si porrà la stessa domanda.
L’equazione ricorsiva deriva dal seguente principio di moltiplicazione: se \(G(x)\) e \(H(x)\) sono funzioni generatrici esponenziali di due strutture \(g\) e \(h\), allora la funzione generatrice della struttura \(g \times h\) è data dal prodotto \(G(x)H(x)\). Naturalmente il principio si può estendere ad un numero finito \(n \gt 2\) di strutture.
Per approfondire questo teorema puoi consultare ad esempio il capitolo 4 del libro di Bruce Sagan, Combinatorics: The Art of Counting (AMS). Il libro è facilmente reperibile come pdf online.
In alternativa la formula della funzione generatrice può essere dimostrata utilizzando la seguente identità:
\[
r! {n \brace r} = \sum\limits_{s_{1}, \cdots,s_{r} \ge 1 \\ s_{1} + \cdots + s_{r}=n}\frac{n!}{s_{1}! \cdots s_{r}!}
\]
Da questa formula abbiamo
\[
\sum\limits_{n =0}^{\infty}r! {n \brace r} \frac{x^{n}}{n!}= \sum\limits_{s_{1}=1}^{\infty}\frac{x^{s_{1}}}{s_{1}!}
\cdots \sum\limits_{s_{r}=1}^{\infty}\frac{x^{s_{r}}}{s_{r}!} = (e^{x}-1)^{r}
\]
Pietro · 3 Aprile 2024 alle 7:46 AM
Ciao GameLudere (scusa se ti chiamo così ma non so il tuo nome :)).
Ti ringrazio molto per la risposta. In verità la volta scorsa non riuscivo neanche a visualizzare il commento inviato per cui pensavo di non averlo inviato.
Avevo anche inviato un post su math.stackexchange sulla questione, ma non ho avuto risposte concrete ed inoltre mi hanno anche penalizzato la domanda per un non ben precisato motivo.
Poco male, la tua risposta è completa.
Da poco mi son messo a studiare le funzioni generatrici, per cui il consiglio del libro di Sagan è quanto mai gradito. Vado subito a “cercarlo”.
Non conoscevo ovviamente questo pricincipio, direi molto potente.
Io avevo provato a cercare la soluzione nel libro di Wilf, Generating Functionology, ma lui usa un’altra identità per risolvere il problema, mentre io ero interessato a questa tua, molto più semplice.
Va bene, grazie ancora e complimenti per il sito.
Molto interessante e con argomenti di “frontiera”.