Série génératrice

Modèle:Voir homonymes En mathématiques, et notamment en analyse et en combinatoire, une série génératrice (appelée autrefois fonction génératrice, terminologie encore utilisée en particulier dans le contexte de la théorie des probabilités) est une série formelle dont les coefficients codent une suite $(a_n)$ de nombres (ou plus généralement de polynômesModèle:Etc.) ; on dit que la série est associée à la suite. Ces séries furent introduites par Abraham de Moivre en 1730, pour obtenir des formules explicites pour des suites définies par récurrence linéaire.

C'est une notion distincte de l'interpolation polynomiale, où l'on cherche à déterminer un polynôme dont les valeurs (et non plus les coefficients) coïncident avec une suite donnée.

En fait, il existe plusieurs sortes de séries génératrices, comme les séries génératrices exponentielles, les séries de Lambert, les séries de DirichletModèle:Etc. On peut associer à toute suite une série génératrice de chaque type, mais la facilité de manipulation de la série dépend considérablement de la nature de la suite associée : par exemple l'arithmétique des séries de Dirichlet reflète assez naturellement les propriétés de suites en théorie des nombres, tandis que les séries génératrices exponentielles seront quant à elles idéales pour encoder des problèmes liés aux permutationsModèle:Etc.

Il est souvent possible d'étudier une suite donnée à l'aide de manipulations formelles de la série génératrice associée, ainsi qu'en utilisant les propriétés analytiques de la fonction somme de la série, du moins si celle-ci converge pour un ensemble assez grand de valeurs. Ce dernier cas, assez fréquent en pratique, justifie la dénomination de fonction génératrice et constitue le socle de la combinatoire analytique (l'énumération et l'asymptotique d'objets combinatoires via des séries génératrices). Notons de plus que des séries divergentes, telles que $\sum _{n\ge 0}n!x^n$ ou $\sum _{n\ge 0}{2}^n{x}^n$, sont parfaitement et rigoureusement manipulables : elles convergent dans l'anneau des séries formelles, muni de sa topologie idoine, et peuvent aussi être étudiées asymptotiquement (via d'éventuelles transformations).

Définitions

Les séries définies ci-dessous sont des séries formelles, c'est-à-dire qu'on ne se préoccupe a priori pas de leur domaine de convergence.

Série génératrice ordinaire

La série génératrice ordinaire d'une suite Modèle:Mvar (souvent simplement appelée série génératrice de la suite) est la série entière

$G(a_n;x)=\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n$.

Cette définition se généralise aisément à des suites à plusieurs indices. Par exemple, pour une suite Modèle:Math (où n et k sont des entiers naturels), la série génératrice est

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

Modèle:AncreSérie génératrice exponentielle

La série génératrice exponentielle associée à une suite Modèle:Mvar est

$\mathrm{EG}(a_n;x)=\sum _{n=0}^{\mathrm{\infty }}{a}_n\frac{x^n}{n!}$.

Série génératrice de Poisson

La série génératrice de Poisson d'une suite Modèle:Mvar est

$\mathrm{PG}(a_n;x)=\sum _{n=0}^{\mathrm{\infty }}{a}_n{\mathrm{e}}^{-x}\frac{x^n}{n!}={\mathrm{e}}^{-x}\mathrm{EG}(a_n;x)$.

Série génératrice de Lambert

Modèle:Article détaillé La série de Lambert d'une suite Modèle:Mvar est

$\mathrm{LG}(a_n;x)=\sum _{n=1}^{\mathrm{\infty }}{a}_n\frac{x^n}{1-x^n}$.

Dans ce cas, pour des problèmes de définition, la suite doit commencer à Modèle:Math et non à Modèle:Math.

Série génératrice de Bell

Modèle:Article détaillé La série de Bell d'une suite Modèle:Mvar, pour un nombre premier Modèle:Mvar donné, est la série formelle

${\mathrm{BG}}_p(a_n;x)=\sum _{n=0}^{\mathrm{\infty }}{a}_{p^n}{x}^n=G(a_{p^n};x)$.

Série génératrice de Dirichlet

Modèle:Article détaillé Les séries de Dirichlet sont souvent classées parmi les séries génératrices, bien qu'elles ne soient pas à proprement parler des séries formelles (de puissances entières de l'indéterminée). La série génératrice de Dirichlet d'une suite Modèle:Mvar est

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

La série de Dirichlet est particulièrement utile lorsque Modèle:Mvar est une fonction multiplicative, car elle possède alors un produit eulérien donné par les séries de Bell :

$\mathrm{DG}(a_n;s)=\prod _p{\mathrm{BG}}_p(a_n;p^{-s})$.

Si Modèle:Mvar est un caractère de Dirichlet, la série de Dirichlet correspondante s'appelle une série L de Dirichlet.

Séries génératrices de suites de polynômes

La notion de série génératrice s'étend à d'autres suites d'objets. Ainsi, les séries génératrices (ordinaires) des polynômes de Tchebychev de première et de seconde espèce sont :

$\sum _{n=0}^{\mathrm{\infty }}{T}_n(X)t^n=\frac{1-tX}{1-2tX+t^2},\sum _{n=0}^{\mathrm{\infty }}{U}_n(X)t^n=\frac{1}{1-2tX+t^2}$.

La série génératrice (exponentielle) des polynômes de Bernoulli est

$\sum _{n=0}^{\mathrm{\infty }}{B}_n(X)\frac{t^n}{n!}=\frac{t{\mathrm{e}}^{Xt}}{{\mathrm{e}}^t-1}$ ;

Plus généralement, les suites de polynômes de type binomial sont associées à la série

${\mathrm{e}}^{Xf(t)}=\sum _{n=0}^{\mathrm{\infty }}\frac{p_n(X)}{n!}{t}^n$,

où Modèle:Math est une suite de polynômes et Modèle:Math une fonction (d'une forme particulière) ; les suites de Sheffer possèdent des séries génératrices similaires. On trouvera plus de détails à l'article « Polynôme d'Appell généralisé ».

Dérivées itérées en 0

Les dérivées des séries génératrices sont définies formellement comme les séries des dérivées de chaque terme ; par exemple, pour une série génératrice ordinaire $\mathrm{G}(a_n;x)=\sum a_n{x}^n$, on a ${\mathrm{G}}^{\prime }(a_n;x)=\mathrm{G}((n+1)a_{n+1};x)$. En particulier, en 0, on a :

Série génératrice ordinaire

Les dérivées itérées en 0 de la série génératrice ordinaire de la suite Modèle:Mvar valent :

${\mathrm{G}}^{(k)}(a_n;0)=k!a_k$

Série génératrice exponentielle

Les dérivées itérées en 0 de la série génératrice exponentielle de la suite Modèle:Mvar valent :

${\mathrm{EG}}^{(k)}(a_n;0)=a_k$

Série génératrice de Poisson

Les dérivées itérées en 0 de la série génératrice de Poisson de la suite Modèle:Mvar valent :

${\mathrm{PG}}^{(k)}(a_n;0)=\sum _{i=0}^k(-1{)}^i{C}_k^i{a}_{k-i}=\sum _{i=0}^k(-1{)}^{k-i}{C}_k^i{a}_i$

Série de Lambert

Les dérivées itérées en 0 de la série de Lambert de la suite Modèle:Mvar (n à partir de 1) valent :

${\mathrm{LG}}^{(k)}(a_n;0)=k!\sum _{\stackrel{i=1}{i|k}}^k{a}_i$

Seuls les termes de la suite dont l’indice i divise k apparaissent dans la somme.

Exemple : séries génératrices de la suite des carrés

Les séries génératrices de différents types correspondant à la suite des carrés Modèle:Math sont :

Série génératrice ordinaire

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

Série génératrice exponentielle

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

Série de Bell

${\mathrm{BG}}_p(a_n;x)=\sum _{n=0}^{\mathrm{\infty }}(p^n{)}^2{x}^n=\frac{1}{1-p^{2}x}$

Série de Dirichlet

$\mathrm{DG}(n^2;s)=\sum _{n=1}^{\mathrm{\infty }}\frac{n^2}{n^s}=\zeta (s-2)$ (où ζ est la fonction zêta de Riemann).

Plus généralement, si la suite Modèle:Mvar a une série de Dirichlet correspondant à

$\mathrm{DG}(a_n;s)=\zeta (s{)}^m$,

cette suite a pour série génératrice ordinaire

$\begin{array}{cc}G(a_n;x)=\sum _{n=1}^{\mathrm{\infty }}{a}_n{x}^n=x& +(\genfrac{}{}{0ex}{}{m}{1})\sum _{a=2}^{\mathrm{\infty }}{x}^a+(\genfrac{}{}{0ex}{}{m}{2})\sum _{a=2}^{\mathrm{\infty }}\sum _{b=2}^{\mathrm{\infty }}{x}^{ab}\\ & +(\genfrac{}{}{0ex}{}{m}{3})\sum _{a=2}^{\mathrm{\infty }}\sum _{b=2}^{\mathrm{\infty }}\sum _{c=2}^{\mathrm{\infty }}{x}^{abc}+(\genfrac{}{}{0ex}{}{m}{4})\sum _{a=2}^{\mathrm{\infty }}\sum _{b=2}^{\mathrm{\infty }}\sum _{c=2}^{\mathrm{\infty }}\sum _{d=2}^{\mathrm{\infty }}{x}^{abcd}+...\end{array}$

Séries génératrices ordinaires

Polynômes

Les polynômes sont un cas particulier de séries génératrices ordinaires, correspondant aux suites finies (ou aux suites s'annulant à partir d'un certain rang). Cette interprétation est importante, par exemple, dans le cas des polynômes de Poincaré, correspondant à la suite des nombres de Betti d'une variété donnée, ou pour les Modèle:Lien pour les algèbres graduées.

Série génératrice d'une suite géométrique

La suite constante dont tous les termes valent 1 joue un rôle important dans les applications ; sa série génératrice est

$\sum _{n=0}^{\mathrm{\infty }}{x}^n=\frac{1}{1-x}$,

comme on le vérifie aisément en multipliant formellement cette série par Modèle:Math, et en remarquant que tous les termes s'annulent 2 à 2 sauf le premier.

On en déduit l'expression des séries génératrices de nombreuses autres suites : ainsi, la substitution Modèle:Math donne la série génératrice d'une suite géométrique Modèle:Math :

$\sum _{n=0}^{\mathrm{\infty }}(ax{)}^n=\frac{1}{1-ax}$ et en particulier $\sum _{n=0}^{\mathrm{\infty }}(-1{)}^n{x}^n=\frac{1}{1+x}$.

Remplaçant Modèle:Mvar par Modèle:Math par exemple, on obtient la série associée à la suite 1, 0, 1, 0, 1, 0, 1, 0, ... : $\sum _{n=0}^{\mathrm{\infty }}{x}^{2n}=\frac{1}{1-x^2}$.

Dérivant par rapport à Modèle:Mvar, on obtient la série associée à la suite des entiers 1, 2, 3, 4, 5, ... :

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

de même, la suite des nombres triangulaires 1, 3, 6, 10, 15, 21, ... dont le n-ième terme est le coefficient binomial $(\genfrac{}{}{0ex}{}{n+2}{2})$ correspond à

$\sum _{n=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{n+2}{2})x^n=\frac{1}{(1-x{)}^3}$.

Plus généralement, pour tout entier positif k, on a la formule du binôme négatif :

$\sum _{n=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{n+k}{k})x^n=\frac{1}{(1-x{)}^{k+1}}$.

Comme $(\genfrac{}{}{0ex}{}{n+2}{2})=\frac{1}{2}(n+1)(n+2)=\frac{1}{2}(n^2+3n+2)$, on en déduit (par combinaison linéaire des séries génératrices précédentes) la série génératrice de la suite des carrés 0, 1, 4, 9, 16, ... :

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

Fractions rationnelles

Modèle:Article détaillé La série génératrice d'une suite peut être exprimée comme un quotient de deux polynômes si et seulement si la suite est une suite récurrente linéaire. En effet, une suite Modèle:Math vérifie une récurrence de la forme Modèle:Retrait (où Modèle:Math sont des constantes) si et seulement si sa série génératrice Modèle:Math, multipliée par le polynôme Modèle:Retrait est une série formelle dont tous les termes sont nuls à partir du degré Modèle:Mvar, c'est-à-dire si Modèle:Retrait où Modèle:Mvar est un polynôme de degré strictement inférieur à Modèle:Mvar (dont les coefficients dépendent alors des Modèle:Mvar premiers termes de la suite).

On peut alors calculer cette fraction rationnelle Modèle:Math en la décomposant en éléments simples puis en développant chacun de ces éléments comme dans les exemples précédents.

Modèle:Démonstration/début Cette suite (FModèle:Ind) est définie par FModèle:Ind = 0, FModèle:Ind = 1 et FModèle:Ind = FModèle:Ind + FModèle:Ind pour n ≥ 2. Sa série génératrice est donc Modèle:Retrait Les racines du dénominateur sont les inverses du nombre d'or et de son conjugué : Modèle:Retrait si bien que Modèle:Retrait On en déduit la formule de Binet : Modèle:Retrait Modèle:Démonstration/fin

Le produit de Hadamard $(A\odot B)(X):=\sum a_n{b}_n{X}^n$ de deux séries $A(X)=\sum a_n{X}^n$ et $B(X)=\sum b_n{X}^n$ rationnelles est rationnel.

Multiplication et convolution

Modèle:Article détaillé Le produit des séries génératrices de deux suites correspond à la convolution discrète des suites (à leur produit de Cauchy). Ainsi, la suite des sommes cumulées : Modèle:Math, d'une suite de série génératrice Modèle:Math a pour série génératrice Modèle:Math, ces sommes correspondant au produit de Cauchy de la suite des Modèle:Mvar par la suite constante (1, 1, ...).

Transformée de Fourier discrète

Modèle:Article détaillé Si la série génératrice est absolument convergente, $G(a_n;e^{-i\omega })=\sum _{n=0}^{\mathrm{\infty }}{a}_n{e}^{-i\omega n}$ est la transformée de Fourier discrète de la suite Modèle:Math.

Séries génératrices à plusieurs variables

On a défini de même Modèle:Supra la série génératrice (à plusieurs variables) associée à une suite à plusieurs indices.

Par exemple, la série génératrice $G((\genfrac{}{}{0ex}{}{n}{k});x,y)$ de la suite à deux indices des coefficients binomiaux se déduit facilement de la série génératrice d'une suite géométrique vue précédemment :

$\sum _{n,k\ge 0}(\genfrac{}{}{0ex}{}{n}{k})y^k{x}^n=\sum _{n\ge 0}{(1+y)}^n{x}^n=\frac{1}{1-x(1+y)}$.

Comportement asymptotique

L'étude de la vitesse de croissance des coefficients d'une série entière permet en général de déterminer le rayon de convergence de cette série (voir l'article règle de d'Alembert). Réciproquement, il est souvent possible d'utiliser la connaissance du rayon de convergence d'une série génératrice pour en déduire le comportement asymptotique de la suite associée.

On peut fréquemment déterminer ce comportement asymptotique en utilisant les singularités de la fonction holomorphe somme de la série génératrice, comme on le verra plus précisément dans l'exemple 3 ci-dessous ; en effet, on sait que le rayon de convergence de la série, r, est égal à la distance de la singularité la plus proche de l'origine, et qu'alors, pour tout Modèle:Math, on a Modèle:Math. Si par exemple cette singularité est un pôle, il est alors possible de construire une série à rayon de convergence plus grand en soustrayant une fonction appropriée, obtenant un équivalent asymptotique exact des coefficients de la suite associée. Plus généralement, si la série génératrice Modèle:Math a un rayon de convergence égal à r, et peut être écrite

$G(a_n;x)=\frac{A(x)+B(x)(1-x/r{)}^{-\beta }}{x^{\alpha }}$,

où Modèle:Math et Modèle:Math sont des fonctions analytiques dans un disque de rayon supérieur à r, et où Modèle:Math, alors

$a_n\sim \frac{B(r)}{r^{\alpha }\mathrm{\Gamma }(\beta )}{n}^{\beta -1}(1/r{)}^n$ (où Γ désigne la fonction gamma).

La combinatoire analytique fait un riche usage de ce lien entre le comportement de la série génératrice au voisinage de ses singularités et la croissance de ses coefficients.

Exemple 1 : la suite des carrés

Comme on l'a montré plus haut, la série génératrice de la suite des carrés est $\frac{x(x+1)}{(1-x{)}^3}$. Avec r = 1, α = 0, β = 3, A(x) = 0, et B(x) = x(x+1), on vérifie que les carrés croissent en effet comme nModèle:Exp :

$a_n\sim \frac{B(r)}{r^{\alpha }\mathrm{\Gamma }(\beta )}{n}^{\beta -1}(1/r{)}^n=\frac{1(1+1)}{1^0\mathrm{\Gamma }(3)}{n}^{3-1}(1/1{)}^n=n^2$.

Exemple 2 : les nombres de Catalan

La série génératrice de la suite des nombres de Catalan est

$\frac{1-\sqrt{1-4x}}{2x}$.

Avec r = 1/4, α = 1, β = −1/2, A(x) = 1/2, et B(x) = −1/2, on en conclut que le n-ième nombre de Catalan, C_n, vérifie

$C_n\sim \frac{B(r)}{r^{\alpha }\mathrm{\Gamma }(\beta )}{n}^{\beta -1}(1/r{)}^n=\frac{-1/2}{(1/4{)}^1\mathrm{\Gamma }(-1/2)}{n}^{-1/2-1}{\left(\frac{1}{1/4}\right)}^n=\frac{n^{-3/2}{4}^n}{\sqrt{\pi }}$.

Exemple 3 : les nombres de Bernoulli

La série génératrice exponentielle de la suite des nombres de Bernoulli est

$\frac{x}{{\mathrm{e}}^x-1}=\sum _{k=0}^{\mathrm{\infty }}{B}_k\frac{x^k}{k!}$.

Il n'est pas possible d'appliquer directement le résultat précédent, parce que cette suite est trop souvent nulle (il faudrait s'intéresser à la suite des Modèle:Math), mais on vérifie aisément que le rayon de convergence est Modèle:Math, puisque les pôles de la fonction Modèle:Math sont les Modèle:Math (avec k entier relatif non nul), d'où l'on déduit que $B_n/n!=o((2\pi -\epsilon {)}^{-n})$ pour tout $\epsilon >0$ ; remarquant alors que la fonction $z/(e^z-1)-2i\pi /(z-2\mathrm{i}\pi )+2\mathrm{i}\pi /(z+2\mathrm{i}\pi )$ n'a plus les deux premiers pôles, et donc un rayon de convergence de Modèle:Math, on en déduit un équivalent précis de $B_{2n}/(2n)!$, puis, grâce à la formule de Stirling,

$|B_{2n}|\sim 4\sqrt{\pi n}{\left(\frac{n}{\pi e}\right)}^{2n}$.

Applications

Les séries génératrices sont utilisées pour :

• déterminer une formule explicite pour des suites récurrentes linéaires ;
• réciproquement, la forme d'une série génératrice peut amener à déterminer (ou du moins à deviner) une relation de récurrence satisfaite par une suite. De même, des relations entre séries génératrices permettent de déterminer des relations entre les suites associées ;
• étudier le comportement asymptotique des suites.

Combinatoire analytique

En combinatoire analytique, on étudie une suite de dénombrements Modèle:Mvar, représentant le nombre d'objets de taille n vérifiant telle ou telle condition (par exemple le nombre de permutations d'un ensemble de n lettres, ou le nombre des polyominos de n carrés) à l'aide de la série génératrice (le plus souvent ordinaire ou exponentielle) associée ; Philippe Flajolet et Robert Sedgewick ont développé une méthode systématique (la méthode symbolique) de détermination de cette série génératrice à partir des contraintes sur les objets étudiés.

Un exemple de la méthode symbolique : les nombres de Catalan

Les nombres de Catalan (parmi bien d'autres définitions combinatoires) comptent les triangulations des polygones convexes. On peut considérer une triangulation comme composée de deux triangulations (éventuellement vides) de polygones plus petits de chaque côté d'un triangle convenablement choisi. La méthode symbolique représente alors la suite $𝒯$ de ces triangulations par la « formule » $𝒯=\{ϵ\}+𝒯\times \mathrm{\Delta }\times 𝒯$, d'où on déduit mécaniquement la relation Modèle:Math (où $T(x)=\sum _{n=0}^{\mathrm{\infty }}{T}_n{x}^n$ est la série génératrice des Modèle:Mvar, nombre des triangulations d'un polygone à n + 2 sommets). La résolution de cette équation amène à la formule explicite $T(x)=\frac{1-\sqrt{1-4x}}{2x}$, d'où la formule de Taylor permet de déduire que le n-ième nombre de Catalan est $T_n=\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})=\frac{(2n)!}{(n+1)!n!}$.

Application des séries génératrices à plusieurs variables au dénombrement

Le calcul du nombre de tableaux de contingence, c'est-à-dire de matrices d'entiers naturels dont les totaux des lignes et des colonnes sont spécifiés, peut s'obtenir à l'aide d'une série génératrice à plusieurs variables. Pour des tables ayant r lignes et c colonnes, pour totaux des lignes Modèle:Math, et pour ceux des colonnes Modèle:Math, Irving John Good a montré que leur nombre est le coefficient de $x_1^{t_1}\dots x_r^{t_r}{y}_1^{s_1}\dots y_c^{s_c}$ dans

$\prod _{i=1}^r\prod _{j=1}^c\frac{1}{1-x_i{y}_j}$.

Probabilités

Modèle:Article détaillé Les séries génératrices d'une suite de probabilités ayant un rayon de convergence nécessairement supérieur à 1, elles sont généralement confondues avec la fonction somme de la série, d'où le nom de fonction génératrice utilisé dans ce cas. On parle en particulier de fonction génératrice des probabilités et de fonction génératrice des moments.

Voir aussi

Bibliographie

• Modèle:Article
• Modèle:Analytic Combinatorics
• Modèle:Ouvrage
• Modèle:Ouvrage

Articles connexes

• Fonction génératrice des probabilités
• Fonction génératrice des moments
• Transformation binomiale

Liens externes

• Modèle:En Generating Functions, Power Indices and Coin Change, sur Cut The Knot
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, mémoire de maîtrise, 1992
• Modèle:Es Ignacio Larrosa Cañestro, León-Sotelo, Marko Riedel, Georges Zeller, Suma de números equilibrados, newsgroup es.ciencia.matematicas
• Modèle:En Generating Functions par Modèle:Lien, Wolfram Demonstrations Project, 2007
• Modèle:Chapitre