Fonction génératrice/Fonction génératrice d'une suite numérique

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Définition

Définition

Soit une suite numérique (u_n)_n∈ℕ. On appelle :

• série génératrice (autrefois : fonction génératrice, et parfois qualifiée d'« ordinaire » par opposition à la série génératrice exponentielle ci-dessous) associée à (u_n)_n∈ℕ la série formelle

  $\sum _{k=0}^{\infty }u_{k}X^{k}$ ;

• série génératrice exponentielle associée à (u_n)_n∈ℕ la série formelle

  $F_{u}(X)=\sum _{k=0}^{\infty }{\frac {u_{k}}{k!}}X^{k}$.

Le k! présent dans la seconde définition a été introduit pour les raisons suivantes :

• il augmente considérablement les chances de voir la série converger sur un domaine plus important. Sans le k!, beaucoup de suites numériques auraient une série génératrice dont le domaine de convergence serait réduit à {0} ;
• les calculs de la somme se trouvent simplifiés. Pour s’en convaincre, le lecteur est invité à essayer de recalculer la fonction génératrice ordinaire des déplacements et des surjections dans les deux applications données ci-dessous ;
• l’équivalent de la propriété 3 des fonctions génératrices associées aux variables aléatoires se trouve simplifié. En effet, nous avons la propriété suivante :

Propriété

Soit (u_n)_n∈ℕ, une suite numérique et soit F_u sa série génératrice exponentielle. On a alors :

$u_{n}=F_{u}^{(n)}(0)$.

Le i! (qui serait devenu ici n!) présent dans la propriété 3 de la fonction génératrice des variables aléatoires a disparu.

La démonstration est similaire à celle donnée pour les variables aléatoires.

Nous avons énoncé cette propriété car c’est celle qui va servir dans ce chapitre.

Pour mieux comprendre l’intérêt de la série génératrice exponentielle, nous allons donner quelques applications où elle intervient. (Les deux exemples qui suivent peuvent être considérés comme un complément d’étude sur les dérangements et les surjections abordés dans les leçons sur la formule du crible et sur la formule d'inversion de Pascal.)

Application 1 : complément sur les dérangements

Nous rappelons qu’un dérangement d’un ensemble E est une permutation sans points fixes.

Nous rappelons aussi que le nombre N_n de dérangements d’un ensemble de cardinal n est donné par la formule :

$\forall n\in \mathbb {N} \qquad N_{n}=n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}$

Nous allons essayer de donner une autre formule pour N_n sans sommation.

Pour cela, posons :

$u_{n}=n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}$

et calculons la série génératrice exponentielle associée à la suite (u_n)_n∈ℕ.

Nous avons :

${\begin{aligned}F_{u}(X)&=\sum _{k=0}^{\infty }{\frac {u_{k}}{k!}}X^{k}=\sum _{k=0}^{\infty }\sum _{i=0}^{k}\left({\frac {(-1)^{i}}{i!}}\right)X^{k}=\sum _{i=0}^{\infty }\sum _{k=i}^{\infty }\left({\frac {(-1)^{i}}{i!}}\right)X^{k}\\&=\sum _{i=0}^{\infty }\left({\frac {(-1)^{i}}{i!}}\right)\sum _{k=i}^{\infty }X^{k}=\sum _{i=0}^{\infty }\left({\frac {(-1)^{i}}{i!}}\right){\frac {X^{i}}{1-X}}={\frac {1}{1-X}}\sum _{i=0}^{\infty }\left({\frac {(-X)^{i}}{i!}}\right)\\&={\frac {\mathrm {e} ^{-X}}{1-X}},\end{aligned}}$

où $\mathrm {e} ^{X}$ est la série formelle $\sum _{i=0}^{\infty }{\frac {X^{i}}{i!}}$.

De plus, en utilisant la propriété du paragraphe précédent, nous avons :

$u_{n}=F_{u}^{(n)}(0)$,

ce qui donne pour les dérangements :

$N_{n}=F_{u}^{(n)}(0)$.

Nous avons donc obtenu le résultat suivant :

Début d’un théorème

Théorème

Soit $f$ la série formelle définie par :

$f(X)={\frac {\mathrm {e} ^{-X}}{1-X}}$.

Le nombre de dérangements N_n d’un ensemble de cardinal n est donné par :

$N_{n}=f^{(n)}(0)$.

Fin du théorème

Remarquons que le rayon de convergence de la série entière associée à $f$ est $1$, si bien que $f^{(n)}(0)$ (terme constant de la $n$-ième dérivée formelle d'une série formelle, qui généralise la notion de dérivée formelle d'un polynôme) est égal à la dérivée $n$-ième en 0 de cette série entière.

Application 2 : complément sur les surjections

Rappelons que le nombre de surjections d’un ensemble de cardinal p vers un ensemble de cardinal n est donné par la formule :

$S_{p,n}=\sum _{k=0}^{n}(-1)^{n-k}{n \choose k}k^{p}$.

Nous allons essayer, là aussi, de donner pour S_p,n une formule sans sommation.

Pour cela, posons :

$u_{p}=\sum _{k=0}^{n}(-1)^{n-k}{n \choose k}k^{p}$

et calculons la série génératrice exponentielle F_u associée à la suite (u_p)_p∈ℕ. Nous avons :

${\begin{aligned}F_{u}(X)&=\sum _{p=0}^{\infty }{\frac {u_{p}}{p!}}X^{p}=\sum _{p=0}^{\infty }{\frac {1}{p!}}\sum _{k=0}^{n}(-1)^{n-k}{\binom {n}{k}}k^{p}X^{p}=\sum _{p=0}^{\infty }\sum _{k=0}^{n}(-1)^{n-k}{\binom {n}{k}}k^{p}{\frac {X^{p}}{p!}}\\&=\sum _{k=0}^{n}\sum _{p=0}^{\infty }(-1)^{n-k}{\binom {n}{k}}k^{p}{\frac {X^{p}}{p!}}=\sum _{k=0}^{n}(-1)^{n-k}{\binom {n}{k}}\sum _{p=0}^{\infty }{\frac {(kX)^{p}}{p!}}=\sum _{k=0}^{n}{\binom {n}{k}}(-1)^{n-k}\mathrm {e} ^{kX}\\&=(\mathrm {e} ^{X}-1)^{n}.\end{aligned}}$

De plus, en utilisant la propriété du premier paragraphe, nous avons :

$\forall n\in \mathbb {N} \qquad u_{p}=F_{u}^{(p)}(0)$

et donc :

$S_{p,n}=F_{u}^{(p)}(0)$.

Nous avons donc obtenu le résultat suivant :

Début d’un théorème

Théorème

Soit $f$ la série formelle définie par :

$f(X)=(\mathrm {e} ^{X}-1)^{n}$.

Le nombre de surjections S_p,n d’un ensemble de cardinal p vers un ensemble de cardinal n est donné par :

$S_{p,n}=f^{(p)}(0)$.

Fin du théorème

Là encore, $f^{(p)}(0)$, défini formellement, peut s'interpréter analytiquement (ici, le rayon de convergence est même infini).

Nous pouvons même aller un peu plus loin.

Calculons la série formelle F_u modulo $X^{n+6}$, ou encore — en identifiant désormais les séries formelles aux séries entières associées — le développement limité en 0 de la fonction F_u à l’ordre n + 5.

Le développement limité à l’ordre 6 de x ↦ e^x – 1 est :

$e^{x}-1=x+{\frac {x^{2}}{2}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+{\frac {x^{5}}{5!}}+{\frac {x^{6}}{6!}}+x^{6}\epsilon (x)$

avec, bien sûr :

$\lim _{n\to \infty }\epsilon (x)=0$

Nous obtiendrons le développement limité de F_u à l’ordre n + 5 en élevant à la puissance n l’expression précédente et en ne conservant que les termes de degré inférieur ou égal à n + 5.

(Si, dans l’expression précédente, nous avions pris un développement limité à l’ordre 7, le terme x⁷/7! n’aurait donné que des termes de degré supérieur ou égal à n + 6 donc inutiles.)

Nous avons :

${\begin{aligned}\left(x+{\frac {x^{2}}{2}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+{\frac {x^{5}}{5!}}+{\frac {x^{6}}{6!}}\right)^{n}&=x^{n}\left(1+{\frac {x}{2}}+{\frac {x^{2}}{3!}}+{\frac {x^{3}}{4!}}+{\frac {x^{4}}{5!}}+{\frac {x^{5}}{6!}}\right)^{n}\\&=x^{n}\sum _{i=0}^{n}{n \choose i}\left({\frac {x}{2}}+{\frac {x^{2}}{3!}}+{\frac {x^{3}}{4!}}+{\frac {x^{4}}{5!}}+{\frac {x^{5}}{6!}}\right)^{i}\\&=x^{n}\sum _{i=0}^{n}{n \choose i}\left({\frac {x}{2}}\right)^{i}\left(1+{\frac {x}{3}}+{\frac {x^{2}}{12}}+{\frac {x^{3}}{60}}+{\frac {x^{4}}{360}}\right)^{i}\\&=x^{n}\sum _{i=0}^{n}{n \choose i}\left({\frac {x}{2}}\right)^{i}\sum _{j=0}^{i}{i \choose j}\left({\frac {x}{3}}+{\frac {x^{2}}{12}}+{\frac {x^{3}}{60}}+{\frac {x^{4}}{360}}\right)^{j}\\&=x^{n}\sum _{i=0}^{n}{n \choose i}\left({\frac {x}{2}}\right)^{i}\sum _{j=0}^{i}{i \choose j}\left({\frac {x}{3}}\right)^{j}\left(1+{\frac {x}{4}}+{\frac {x^{2}}{20}}+{\frac {x^{3}}{120}}\right)^{j}\\&=x^{n}\sum _{i=0}^{n}{n \choose i}\left({\frac {x}{2}}\right)^{i}\sum _{j=0}^{i}{i \choose j}\left({\frac {x}{3}}\right)^{j}\sum _{k=0}^{j}{j \choose k}\left({\frac {x}{4}}+{\frac {x^{2}}{20}}+{\frac {x^{3}}{120}}\right)^{k}\\&=x^{n}\sum _{i=0}^{n}{n \choose i}\left({\frac {x}{2}}\right)^{i}\sum _{j=0}^{i}{i \choose j}\left({\frac {x}{3}}\right)^{j}\sum _{k=0}^{j}{j \choose k}\left({\frac {x}{4}}\right)^{k}\left(1+{\frac {x}{5}}+{\frac {x^{2}}{30}}\right)^{k}\\&=x^{n}\sum _{i=0}^{n}{n \choose i}\left({\frac {x}{2}}\right)^{i}\sum _{j=0}^{i}{i \choose j}\left({\frac {x}{3}}\right)^{j}\sum _{k=0}^{j}{j \choose k}\left({\frac {x}{4}}\right)^{k}\sum _{l=0}^{k}{k \choose l}\left({\frac {x}{5}}+{\frac {x^{2}}{30}}\right)^{l}\\&=x^{n}\sum _{i=0}^{n}{n \choose i}\left({\frac {x}{2}}\right)^{i}\sum _{j=0}^{i}{i \choose j}\left({\frac {x}{3}}\right)^{j}\sum _{k=0}^{j}{j \choose k}\left({\frac {x}{4}}\right)^{k}\sum _{l=0}^{k}{k \choose l}\left({\frac {x}{5}}\right)^{l}\left(1+{\frac {x}{6}}\right)^{l}\\&=x^{n}\sum _{i=0}^{n}{n \choose i}\left({\frac {x}{2}}\right)^{i}\sum _{j=0}^{i}{i \choose j}\left({\frac {x}{3}}\right)^{j}\sum _{k=0}^{j}{j \choose k}\left({\frac {x}{4}}\right)^{k}\sum _{l=0}^{k}{k \choose l}\left({\frac {x}{5}}\right)^{l}\sum _{m=0}^{l}{l \choose m}\left({\frac {x}{6}}\right)^{m}.\end{aligned}}$

Sous cette forme, nous voyons que pour conserver les termes de degré inférieur ou égal à n+5, il suffit de choisir les termes dont les puissances i, j, k, l, m vérifient : i + j + k + l + m ≤ 5 avec m ≤ l ≤ k ≤ j ≤ i, c’est-à-dire :

i = 0, j = 0, k = 0, l = 0, m = 0 ;

i = 1, j = 0, k = 0, l = 0, m = 0 ;

i = 1, j = 1, k = 0, l = 0, m = 0 ;

i = 1, j = 1, k = 1, l = 0, m = 0 ;

i = 1, j = 1, k = 1, l = 1, m = 0 ;

i = 1, j = 1, k = 1, l = 1, m = 1 ;

i = 2, j = 0, k = 0, l = 0, m = 0 ;

i = 2, j = 1, k = 0, l = 0, m = 0 ;

i = 2, j = 1, k = 1, l = 0, m = 0 ;

i = 2, j = 1, k = 1, l = 1, m = 0 ;

i = 2, j = 2, k = 0, l = 0, m = 0 ;

i = 2, j = 2, k = 1, l = 0, m = 0 ;

i = 3, j = 0, k = 0, l = 0, m = 0 ;

i = 3, j = 1, k = 0, l = 0, m = 0 ;

i = 3, j = 1, k = 1, l = 0, m = 0 ;

i = 3, j = 2, k = 0, l = 0, m = 0.

Tous calculs faits, après simplifications et factorisations, nous obtenons :

$(e^{x}-1)^{n}=x^{n}+{\frac {n}{2}}x^{n+1}+{\frac {n(3n+1)}{24}}x^{n+2}+{\frac {n^{2}(n+1)}{48}}x^{n+3}+{\frac {n(15n^{3}+30n^{2}+5n-2)}{5760}}x^{n+4}+{\frac {n^{2}(n+1)(3n^{2}+7n-2)}{11520}}x^{n+5}+x^{n+5}\epsilon _{1}(x)$.

Nous connaissons un autre moyen de trouver un développement limité. C’est la formule de Taylor-Young, que nous pouvons utiliser à l’ordre n + 5. Nous avons :

$F_{u}(x)=\sum _{k=0}^{n+5}{\frac {F_{u}^{(k)}(0)}{k!}}x^{k}+x^{n+5}\epsilon _{1}(x)$.

Nous avons gardé la même notation pour ε₁(x) car un développement limité est unique.

Nous obtenons donc par identification :

${\frac {F_{u}^{(n)}(0)}{n!}}=1$

${\frac {F_{u}^{(n+1)}(0)}{(n+1)!}}={\frac {n}{2}}$

${\frac {F_{u}^{(n+2)}(0)}{(n+2)!}}={\frac {n(3n+1)}{24}}$

${\frac {F_{u}^{(n+3)}(0)}{(n+3)!}}={\frac {n^{2}(n+1)}{48}}$

${\frac {F_{u}^{(n+4)}(0)}{(n+4)!}}={\frac {n(15n^{3}+30n^{2}+5n-2)}{5760}}$

${\frac {F_{u}^{(n+5)}(0)}{(n+5)!}}={\frac {n^{2}(n+1)(n^{2}+7n-2)}{11520}}$.

Compte tenu du fait que :

$S_{p,n}=F_{u}^{(p)}(0)$,

nous obtenons finalement :

${\begin{array}{cccc}&\forall n\in \mathbb {N} &&\\S_{n,n}=n!&&&S_{n+1,n}={\frac {n(n+1)!}{2}}\\&&&\\&&&\\S_{n+2,n}={\frac {n(3n+1)(n+2)!}{24}}&&&S_{n+3,n}={\frac {n^{2}(n+1)(n+3)!}{48}}\\&&&\\&&&\\S_{n+4,n}={\frac {n(15n^{3}+30n^{2}+5n-2)(n+4)!}{5760}}&&&S_{n+5,n}={\frac {n^{2}(n+1)(n^{2}+7n-2)(n+5)!}{11520}}\\\end{array}}$

Remarque : compte tenu, aussi, du fait que :

$S_{n+q,n}=\sum _{k=0}^{n}(-1)^{n-k}{n \choose k}k^{n+q}$,

nous en déduisons aussi les formules sommatoires suivantes :

${\begin{array}{cccc}&\forall n\in \mathbb {N} &&\\\sum _{k=0}^{n}(-1)^{n-k}{n \choose k}k^{n}=n!&&&\sum _{k=0}^{n}(-1)^{n-k}{n \choose k}k^{n+1}={\frac {n(n+1)!}{2}}\\&&&\\&&&\\\sum _{k=0}^{n}(-1)^{n-k}{n \choose k}k^{n+2}={\frac {n(3n+1)(n+2)!}{24}}&&&\sum _{k=0}^{n}(-1)^{n-k}{n \choose k}k^{n+3}={\frac {n^{2}(n+1)(n+3)!}{48}}\\&&&\\&&&\\\sum _{k=0}^{n}(-1)^{n-k}{n \choose k}k^{n+4}={\frac {n(15n^{3}+30n^{2}+5n-2)(n+4)!}{5760}}&&&\sum _{k=0}^{n}(-1)^{n-k}{n \choose k}k^{n+5}={\frac {n^{2}(n+1)(n^{2}+7n-2)(n+5)!}{11520}}\\\end{array}}$