Série génératrice

Pour les articles homonymes, voir Génératrice.

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ômes, 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.

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 Dirichlet, 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, et du problème qu'on cherche à étudier.

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 ; c'est ce dernier cas, assez fréquent en pratique, qui justifie la dénomination de fonction génératrice.

Définitions

Série génératrice ordinaire

La série génératrice ordinaire d'une suite a_n (souvent simplement appelée série génératrice de la suite) est

$G(a_n;x)=\sum_{n=0}^\infty a_nx^n.$

Cette définition se généralise aisément à des suites à plusieurs indices. Par exemple, pour la suite a_{m, n} (où n et m sont des entiers naturels), la série génératrice est

$G(a_{m,n};x,y)=\sum_{m,n=0}^\infty a_{m,n}x^my^n.$

Série génératrice exponentielle

La série génératrice exponentielle associée à une suite a_n est

$\operatorname{EG}(a_n;x)=\sum _{n=0}^{\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 a_n est

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

Série de Lambert

La série de Lambert d'une suite a_n est

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

Dans ce cas, pour des problèmes de définition, la suite doit commencer à a₁ et non à a₀.

Série de Bell

La série de Bell d'une suite a_n, pour un nombre premier p donné, est la série formelle

$\operatorname{BG}_p(a_n;x)=\sum_{n=0}^\infty a_{p^n}x^n.$

Série de Dirichlet

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 a_n est

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

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

$\operatorname{DG}(a_n;s)=\prod_{p} \operatorname{BG}_p(a_n;p^{-s})\,.$

Si a_n 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, la série génératrice (exponentielle) des polynômes de Bernoulli est

$\sum_{n=0}^\infty B_n(x) \frac{t^n}{n!}=\frac{t e^{xt}}{e^t-1}\,$ ;

la série génératrice (ordinaire) des polynômes de Tchebychev de première espèce est

$\sum_{n=0}^{\infty}T_n(x) t^n = \frac{1-tx}{1-2tx+t^2}.$

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

$e^{xf(t)}=\sum_{n=0}^\infty {p_n(x) \over n!}t^n$,

où p_n(x) est la suite des polynômes et f(t) 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étaile à 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 $\operatorname{G}(a_n;x) = \sum a_nx^n$, on a $\operatorname{G}'(a_n;x) = \operatorname{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 a_n valent :

$\operatorname{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 a_n valent :

$\operatorname{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 a_n valent :

$\operatorname{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 a_n (n à partir de 1) valent :

$\operatorname{LG}^{(k)}(a_n;0) = k! \, \sum _\overset{i=1}{i|k}^k a_i$

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

Séries génératrices ordinaires

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.

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

$\sum_{n=0}^{\infty}x^n={1\over1-x}.$

(comme on le vérifie aisément en multipliant (formellement) cette série par 1-x, 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 x → ax donne la série génératrice d'une suite géométrique 1,a, a², a³, ... :

$\sum_{n=0}^{\infty}(ax)^n={1\over1-ax}\,.$ et en particulier $\sum_{n=0}^{\infty}(-1)^nx^n={1\over1+x}\,.$

Remplaçant x par x² par exemple, on obtient la série associée à la suite 1, 0, 1, 0, 1, 0, 1, 0, ... : $\sum_{n=0}^{\infty}x^{2n}={1\over1-x^2}.$

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

$\sum_{n=0}^{\infty}(n+1)x^n={1\over(1-x)^2},$

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

$\sum_{n=0}^{\infty}\tbinom{n+2}2 x^n={1\over(1-x)^3}.$

Plus généralement, pour tout entier positif k, on a

$\sum_{n=0}^{\infty}\binom{n+k}k x^n={1\over(1-x)^{k+1}}.$

Comme $\binom{n+2}2=\frac12{(n+1)(n+2)} =\frac12(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}^{\infty}n^2x^n={2\over(1-x)^3}-{3\over(1-x)^2}+{1\over1-x}=\frac{x(x+1)}{(1-x)^3}.$

Fractions rationnelles

Article détaillé : Suite récurrente linéaire.

La série génératrice d'une suite peut être exprimée comme un quotient de deux polynômes (une fraction rationnelle) si et seulement si la suite est une suite récurrente linéaire ; cela généralise les exemples précédents.

Multiplication et convolution

Article détaillé : Produit de Cauchy.

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 : $(a_0, a_0 + a_1, a_0 + a_1 + a_2, \ldots)$, d'une suite de série génératrice G(a_n; x) a pour série génératrice $G(a_n; x) \frac{1}{1-x}$, ces sommes correspondant au produit de Cauchy de la suite des a_n par la suite constante (1, 1, ...).

Transformée de Fourier discrète

Article détaillé : Transformée de Fourier discrète.

Si la série génératrice est absolument convergente, $G\left(a_n; e^{-i \omega}\right) = \sum_{n=0}^\infty a_n e^{-i \omega n}$ est la transformée de Fourier discrète de la suite a₀,  a₁,  ....

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 x>r, on a $a_n=o(x^n)$. 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 G(a_n; x) 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ù A(x) et B(x) sont des fonctions analytiques dans un disque de rayon supérieur à r, et où B(r) ≠ 0, alors

$a_n \sim \frac{B(r)}{r^{\alpha} \Gamma(\beta)} \, n^{\beta-1}(1/r)^{n}\,,$ expression utilisant la fonction gamma^{[réf. nécessaire]}.

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 n² :

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

Exemple 2 : les nombres de Catalan

Article détaillé : nombre 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-ème nombre de Catalan, C_n, vérifie

$C_n \sim \frac{B(r)}{r^{\alpha} \Gamma(\beta)} \, n^{\beta-1}(1/r)^{n} = \frac{-1/2}{(1/4)^1 \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

Article détaillé : nombre de Bernoulli.

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

$\frac{x}{e^x-1}=\sum_{k=0}^{\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 B_2k), mais on vérifie aisément que le rayon de convergence est $r=2\pi$, puisque les pôles de la fonction $z/(e^z-1)$ sont les $z_k=2ik \pi$ (avec k entier relatif non nul), d'où l'on déduit que $B_{n}/n!=o((2\pi-\varepsilon)^{-n})$ pour tout $\varepsilon>0$ ; remarquant alors que la fonction $z/(e^z-1)-2i\pi/(z-2i\pi)+2i\pi/(z+2i\pi)$ n'a plus les deux premiers pôles, et donc un rayon de convergence de $r'=4\pi$, on en déduit un équivalent précis de $B_{2n}/(2n)!$, puis, grâce à la formule de Stirling,

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

Séries génératrices à plusieurs variables

Il est possible de même de définir des séries génératrices associées à des suites à plusieurs indices. Elles sont connues sous le nom de séries génératrices à plusieurs variables.

Par exemple, partant de $(1+x)^n$, la série génératrice des coefficients binomiaux pour un n fixé (série réduite ici à un polynôme), on peut construire une série génératrice des coefficients binomiaux $\binom{n}{k}$ pour tous k et n : il suffit de considérer $(1+x)^n$ comme une suite en n, et de déterminer la série génératrice (de variable y) qui lui est associée. Appliquant les résultats précédents déterminés pour les suites géométriques, on obtient :

$\sum_{n,k} \binom n k x^k y^n = \frac{1}{1-(1+x)y}=\frac{1}{1-y-xy}\,.$

Exemples

Les séries génératrices de différents types correspondant à la suite des carrés a_n = n² sont :

Série génératrice ordinaire

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

Série génératrice exponentielle

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

Série de Bell

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

Série de Dirichlet

$\operatorname{DG}(n^2;s)=\sum_{n=1}^{\infty} \frac{n^2}{n^s}=\zeta(s-2)\,,$ exprimée à l'aide de la fonction zêta de Riemann.

Plus généralement, si la suite $a_n$ a une série de Dirichlet correspondant à

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

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

$\begin{align} G(a_n;x)=\sum \limits_{n=1}^{\infty} a_nx^n = x &+ {m \choose 1}\sum \limits_{a=2}^{\infty} x^{a} + {m \choose 2}\sum \limits_{a=2}^{\infty} \sum \limits_{b=2}^{\infty} x^{ab} \\ &+ {m \choose 3}\sum \limits_{a=2}^{\infty} \sum \limits_{b=2}^{\infty} \sum \limits_{c=2}^{\infty} x^{abc} + {m \choose 4}\sum \limits_{a=2}^{\infty} \sum \limits_{b=2}^{\infty} \sum \limits_{c=2}^{\infty} \sum \limits_{d=2}^{\infty} x^{abcd} +... \end{align}$

Séries génératrices à plusieurs variables

Le calcul du nombre de tables de contingence (en), 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 $t_1,\ldots t_r$, et pour ceux des colonnes $s_1,\ldots s_c$, Irving John Good a montré que leur nombre est le coefficient de $x_1^{t_1}\ldots x_r^{t_r}y_1^{s_1}\ldots y_c^{s_c}$ dans

$\prod_{i=1}^{r}\prod_{j=1}^c\frac{1}{1-x_iy_j}.$

Applications

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

• Déterminer une formule explicite pour des suites récurrentes linéaires, comme par exemple pour la suite de Fibonacci, dont la série génératrice (ordinaire) est $x/(1-x-x^2)$, de laquelle on déduit (par décomposition en éléments simples) la formule de Binet.
• 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

Article connexe : Combinatoire analytique.

En combinatoire analytique, on étudie une suite de dénombrements a_n, 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 $\mathcal T$ de ces triangulations par la « formule » ${\mathcal T}=\{\epsilon \}+{\mathcal T}\times\Delta\times{\mathcal T}$, d'où on déduit mécaniquement la relation $T(x)=1+xT(x)^2$ (où $T(x)=\sum_{n=0}^\infty T_nx^n$ est la série génératrice des $T_n$, nombre des triangulations d'un polygone à n sommets). La résolution de cette équation amène à la formule explicite $T(x)=\frac{1-\sqrt {1-4x}}2$, d'où la formule de Taylor permet de déduire que le n-ème nombre de Catalan est $T_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!}$.

Probabilités

Article détaillé : Fonction génératrice des probabilités.

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.

Concepts similaires

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue !

L'interpolation polynomiale consiste à déterminer un polynôme dont les valeurs (et non plus les coefficients) coïncident avec une suite donnée ; le polynôme de Hilbert (en) en est une abstraction en algèbre commutative.

Voir aussi

Bibliographie

• (en) Peter Doubilet, Gian-Carlo Rota et Richard Stanley, « On the foundations of combinatorial theory. VI. The idea of generating function », Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, vol. 2, 1972, p. 267–318 [texte intégral] 
• (en) Philippe Flajolet et Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009, 810 p. (ISBN 978-0-521-89806-5) [lire en ligne]  (14 Mo) [PDF]
• (en) Ronald L. Graham, Donald E. Knuth et Oren Patashnik (en), Concrete Mathematics. A foundation for computer science, Addison-Wesley, 1994, 2^e éd. (ISBN 0-201-55802-5)  (chapitre 7 : Generating Functions, p. 320-380)
• (en) Herbert S. Wilf, Generatingfunctionology, Boston, Academic Press, 1994, 2^e éd., 228 p. (ISBN 978-0-12-751956-2) [lire en ligne] 

Articles connexes

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

Liens externes

• (en) Generating Functions, Power Indices and Coin Change, sur Cut The Knot
• Simon Plouffe, Fonctions génératrices
• (es) Ignacio Larrosa Cañestro, León-Sotelo, Marko Riedel, Georges Zeller, Suma de números equilibrados, newsgroup es.ciencia.matematicas
• (en) Generating Functions par Ed Pegg, Jr. (en), Wolfram Demonstrations Project, 2007