Fonction génératrice
Une fonction génératrice est une expression mathématique permettant de représenter une suite de nombres sous la forme d'une série de puissances. Chaque terme de la suite est associé au coefficient d'une puissance d'une variable formelle, généralement notée x. Cette représentation transforme ainsi une suite discrète en un objet algébrique sur lequel il devient possible d'effectuer des additions, des multiplications, des dérivations, des intégrations et diverses transformations.
Les fonctions génératrices occupent une place importante en combinatoire, en théorie des nombres, en probabilités, dans l'étude des relations de récurrence et dans l'analyse des algorithmes. Elles permettent notamment de rechercher une formule explicite pour une suite, de résoudre des problèmes de dénombrement, de calculer des sommes et d'étudier le comportement asymptotique de coefficients.
En informatique, elles sont particulièrement utiles lorsqu'un problème peut être décrit par une suite de valeurs dépendant d'un indice. Une fonction génératrice peut alors regrouper toutes ces valeurs dans une seule expression. Elle constitue un pont entre les structures discrètes, comme les suites et les objets combinatoires, et les outils de l'algèbre ou de l'analyse mathématique.
Définition générale
Soit une suite de nombres :
| a0, a1, a2, a3, ... |
La fonction génératrice ordinaire associée à cette suite est définie par :
|
A(x) = a0 + a1x + a2x2 + a3x3 + ... |
En notation de sommation :
|
A(x) = ∑n=0∞ anxn |
Le coefficient de la puissance xn correspond exactement au terme a? de la suite.
On peut donc écrire :
| [xn]A(x) = an |
La notation :
| [xn]A(x) |
désigne le coefficient de xn dans la fonction génératrice A(x).
Exemple simple
Considérons la suite constante :
| 1, 1, 1, 1, ... |
Sa fonction génératrice est :
|
A(x) = 1 + x + x2 + x3 + ... |
Cette expression correspond à une série géométrique de premier terme 1 et de raison x.
Pour :
| |x| < 1 |
on obtient :
| A(x) = 1 / (1-x) |
Ainsi :
|
1 / (1-x) = 1 + x + x2 + x3 + ... |
Le coefficient de chaque puissance de x vaut 1.
Variable formelle
Dans le contexte des fonctions génératrices, la variable x est souvent considérée comme une variable formelle.
Cela signifie que l'expression :
|
A(x) = ∑n=0∞ anxn |
est principalement utilisée pour manipuler les coefficients a?, sans nécessairement attribuer une valeur numérique à x.
Dans cette interprétation, les questions de convergence peuvent être temporairement ignorées. La fonction génératrice est traitée comme une série formelle dont les opérations sont définies directement sur les coefficients.
Cette approche est particulièrement courante en combinatoire et en informatique théorique.
Série formelle et fonction analytique
Une fonction génératrice peut être interprétée de deux manières.
| Interprétation | Description |
|---|---|
| Série formelle | La variable x sert uniquement à repérer les coefficients. La convergence n'est pas nécessaire. |
| Fonction analytique | La série est évaluée pour certaines valeurs de x et doit converger. |
Par exemple :
| 1 + x + x2 + x3 + ... |
est une série formelle bien définie.
Comme fonction numérique, elle ne correspond à :
| 1 / (1-x) |
que dans le domaine :
| |x| < 1 |
Le contexte détermine donc si les questions de convergence doivent être prises en considération.
Fonction génératrice d'une suite finie
Une suite finie peut être représentée par un polynôme.
Considérons la suite :
| 2, 3, 5, 7 |
Sa fonction génératrice est :
|
A(x) = 2 + 3x + 5x2 + 7x3 |
On obtient :
|
[x0]A(x) = 2 [x1]A(x) = 3 [x2]A(x) = 5 [x3]A(x) = 7 |
Les coefficients des puissances supérieures sont considérés comme nuls.
Fonction génératrice de la suite des entiers naturels
Considérons la suite :
| 0, 1, 2, 3, 4, ... |
Sa fonction génératrice est :
|
A(x) = x + 2x2 + 3x3 + 4x4 + ... |
On part de la série géométrique :
|
1 / (1-x) = 1 + x + x2 + x3 + ... |
En la dérivant par rapport à x, on obtient :
|
1 / (1-x)2 = 1 + 2x + 3x2 + 4x3 + ... |
Puis, en multipliant par x :
|
x / (1-x)2 = x + 2x2 + 3x3 + 4x4 + ... |
La fonction génératrice de la suite des entiers naturels est donc :
| A(x) = x / (1-x)2 |
Fonction génératrice des carrés
Considérons la suite :
| 0, 1, 4, 9, 16, 25, ... |
dont le terme général est :
| an = n2 |
Sa fonction génératrice ordinaire est :
|
∑n=0∞ n2xn = x(1+x) / (1-x)3 |
On obtient donc :
|
A(x) = x(1+x) / (1-x)3 |
Cette formule peut être construite à partir de la série géométrique en appliquant plusieurs dérivations et multiplications par x.
Tableau de fonctions génératrices courantes
| Suite an | Fonction génératrice A(x) |
|---|---|
| 1 | 1 / (1-x) |
| c | c / (1-x) |
| n | x / (1-x)2 |
| n+1 | 1 / (1-x)2 |
| n2 | x(1+x) / (1-x)3 |
| rn | 1 / (1-rx) |
| C(n,k), avec k fixé | xk / (1-x)k+1 |
| Fn | x / (1-x-x2) |
Ces expressions servent fréquemment de modèles lors de la résolution de problèmes plus complexes.
Addition de fonctions génératrices
Soient deux suites :
| a0, a1, a2, ... |
et :
| b0, b1, b2, ... |
dont les fonctions génératrices sont respectivement :
|
A(x) = ∑n=0∞ anxn |
et :
|
B(x) = ∑n=0∞ bnxn |
La fonction génératrice de la suite :
| an + bn |
est :
| A(x) + B(x) |
En effet :
|
A(x) + B(x) = ∑n=0∞ (an+bn)xn |
L'addition des fonctions génératrices correspond donc à une addition terme par terme des suites.
Multiplication par une constante
La fonction génératrice de la suite :
| ca0, ca1, ca2, ... |
est :
| cA(x) |
On a :
|
cA(x) = ∑n=0∞ canxn |
Cette propriété permet de combiner facilement plusieurs suites par des opérations linéaires.
Décalage des indices
La multiplication d'une fonction génératrice par x déplace les coefficients d'une position vers les puissances supérieures.
Si :
|
A(x) = a0 + a1x + a2x2 + ... |
alors :
|
xA(x) = a0x + a1x2 + a2x3 + ... |
Le coefficient constant devient nul et chaque terme a? est associé à la puissance :
| xn+1 |
Plus généralement :
| xkA(x) |
décale la suite de k positions.
Exemple de décalage
Soit la suite :
| 1, 2, 3, 4, ... |
dont la fonction génératrice est :
|
A(x) = 1 + 2x + 3x2 + 4x3 + ... |
En multipliant par x², on obtient :
|
x2A(x) = x2 + 2x3 + 3x4 + 4x5 + ... |
Cette nouvelle expression représente la suite :
| 0, 0, 1, 2, 3, 4, ... |
Produit de Cauchy
La multiplication de deux fonctions génératrices correspond à une convolution de leurs coefficients.
Si :
|
A(x) = ∑n=0∞ anxn |
et :
|
B(x) = ∑n=0∞ bnxn |
alors :
|
A(x)B(x) = ∑n=0∞ cnxn |
où :
|
cn = ∑k=0n akbn-k |
Cette opération est appelée produit de Cauchy ou convolution discrète.
Exemple de produit
Considérons :
| A(x) = 1 + x + x2 + ... |
et :
| B(x) = 1 + x + x2 + ... |
Leur produit est :
|
A(x)B(x) = 1 + 2x + 3x2 + 4x3 + ... |
En effet, le coefficient de x2 correspond au nombre de couples d'entiers naturels :
| (i,j) |
tels que :
| i + j = n |
Il existe exactement :
| n + 1 |
couples de ce type.
On retrouve ainsi :
|
1 / (1-x)2 = 1 + 2x + 3x2 + 4x3 + ... |
Interprétation combinatoire du produit
Le produit de fonctions génératrices est particulièrement utile pour combiner des choix indépendants.
Supposons qu'un premier objet puisse contribuer une taille appartenant à la suite représentée par A(x) et qu'un second objet puisse contribuer une taille représentée par B(x).
Le coefficient de xn dans :
| A(x)B(x) |
compte alors le nombre de façons d'obtenir une taille totale égale à n en combinant les contributions des deux objets.
Cette propriété constitue l'un des fondements de l'utilisation des fonctions génératrices en combinatoire.
Dérivation d'une fonction génératrice
Si :
|
A(x) = ∑n=0∞ anxn |
alors sa dérivée est :
|
A'(x) = ∑n=1∞ nanxn-1 |
En multipliant par x, on obtient :
|
xA'(x) = ∑n=0∞ nanxn |
L'opération :
| x d/dx |
transforme donc la suite :
| an |
en :
| nan |
Cette propriété permet notamment de construire les fonctions génératrices de suites contenant des facteurs comme n, n2 ou des polynômes en n.
Intégration d'une fonction génératrice
L'intégration produit l'effet inverse de la dérivation.
Si :
|
A(x) = ∑n=0∞ anxn |
alors :
|
∫A(x)dx = C + ∑n=0∞ anxn+1/(n+1) |
Cette transformation introduit un décalage d'indice et divise chaque coefficient par son nouvel exposant.
L'intégration peut être utilisée pour obtenir la fonction génératrice d'une suite comportant des facteurs comme :
| 1/(n+1) |
Sommes partielles
Supposons que :
|
sn = a0 + a1 + ... + an |
représente la suite des sommes partielles de an.
Si A(x) est la fonction génératrice de an, alors la fonction génératrice de sn est :
| S(x) = A(x) / (1-x) |
Cette propriété vient du produit :
| A(x)(1+x+x2+x3+...) |
Chaque coefficient de la nouvelle série correspond à la somme de tous les coefficients précédents.
Exemple de sommes partielles
La suite constante :
| 1, 1, 1, 1, ... |
possède la fonction génératrice :
| A(x) = 1/(1-x) |
Ses sommes partielles sont :
| 1, 2, 3, 4, ... |
La fonction génératrice de ces sommes est :
|
S(x) = A(x)/(1-x) |
donc :
|
S(x) = 1/(1-x)2 |
On retrouve bien :
|
1/(1-x)2 = 1 + 2x + 3x2 + 4x3 + ... |
Résolution de relations de récurrence
Les fonctions génératrices permettent de résoudre certaines relations de récurrence linéaires.
La méthode générale consiste à :
- définir une fonction génératrice pour la suite ;
- multiplier la relation de récurrence par une puissance de x ;
- sommer les équations obtenues ;
- exprimer les sommes à l'aide de la fonction génératrice ;
- isoler cette fonction ;
- développer ou décomposer l'expression obtenue ;
- extraire le coefficient de xn.
Cette méthode transforme une relation entre plusieurs termes d'une suite en une équation algébrique portant sur une seule fonction.
Exemple avec une suite géométrique
Considérons la relation :
| a0 = 1 |
et :
| an = ran-1 |
pour :
| n ≥ 1 |
Définissons :
|
A(x) = ∑n=0∞ anxn |
En multipliant la récurrence par xn et en sommant pour n ≥ 1, on obtient :
|
A(x) - 1 = rxA(x) |
Ainsi :
| A(x)(1-rx) = 1 |
et donc :
|
A(x) = 1/(1-rx) |
Le développement donne :
|
A(x) = 1 + rx + r2x2 + r3x3 + ... |
On en déduit :
| an = rn |
Fonction génératrice de Fibonacci
Considérons la suite de Fibonacci :
|
F0 = 0 F1 = 1 |
et :
| Fn = Fn-1 + Fn-2 |
pour :
| n ≥ 2 |
Définissons sa fonction génératrice :
|
F(x) = F0 + F1x + F2x2 + F3x3 + ... |
Comme :
| F0 = 0 |
et :
| F1 = 1 |
on obtient :
|
F(x) = x + x2 + 2x3 + 3x4 + 5x5 + ... |
Déduction de la fonction génératrice de Fibonacci
On considère :
|
F(x) = F0 + F1x + F2x2 + F3x3 + ... |
Puis :
|
xF(x) = F0x + F1x2 + F2x3 + ... |
et :
|
x2F(x) = F0x2 + F1x3 + F2x4 + ... |
En raison de la relation :
| Fn = Fn-1 + Fn-2 |
les coefficients des puissances supérieures ou égales à x2 s'annulent dans :
| F(x) - xF(x) - x2F(x) |
Il reste :
| F(x)(1-x-x2) = x |
Ainsi :
|
F(x) = x/(1-x-x2) |
Cette expression compacte contient tous les nombres de Fibonacci dans ses coefficients.
Extraction des coefficients de Fibonacci
Le dénominateur :
| 1-x-x2 |
peut être factorisé à l'aide des racines associées au nombre d'or.
Une décomposition en fractions partielles permet alors d'obtenir une expression de la forme :
|
F(x) = A/(1-φx) + B/(1-ψx) |
où :
| φ = (1+√5)/2 |
et :
| Ψ = (1-√5)/2 |
En utilisant le développement :
|
1/(1-rx) = ∑n=0∞ rnxn |
on retrouve la formule de Binet :
|
Fn = (φn-ψn)/√5 |
La fonction génératrice permet donc de passer d'une relation récursive à une formule explicite.
Décomposition en fractions partielles
Lorsqu'une fonction génératrice est une fraction rationnelle, il est souvent utile de la décomposer en fractions plus simples.
Par exemple :
|
A(x) = 1/((1-2x)(1-3x)) |
peut être écrit sous la forme :
|
A(x) = C/(1-2x) + D/(1-3x) |
Après détermination des constantes, chaque fraction peut être développée comme une série géométrique.
On obtient alors une formule pour le coefficient a?, généralement composée de puissances comme :
| 2n |
et :
| 3n |
Cette méthode est particulièrement efficace pour les récurrences linéaires à coefficients constants.
Fonctions génératrices rationnelles
Une fonction génératrice est dite rationnelle lorsqu'elle peut être écrite comme le quotient de deux polynômes :
|
A(x) = P(x)/Q(x) |
Les suites possédant une fonction génératrice rationnelle satisfont généralement une relation de récurrence linéaire à coefficients constants.
Réciproquement, une suite définie par une telle récurrence possède une fonction génératrice rationnelle.
Cette correspondance relie étroitement :
- les récurrences linéaires ;
- les fractions rationnelles ;
- les équations caractéristiques ;
- les formules explicites.
- Fonction génératrice exponentielle
La fonction génératrice exponentielle d'une suite an est définie par :
|
E(x) = ∑n=0∞ an xn/n! |
Elle diffère de la fonction génératrice ordinaire par le facteur :
| 1/n! |
La fonction génératrice exponentielle est particulièrement adaptée aux structures combinatoires dans lesquelles les éléments sont étiquetés.
Par exemple, la suite constante :
| 1, 1, 1, 1, ... |
possède pour fonction génératrice exponentielle :
|
E(x) = 1 + x + x2/2! + x3/3! + ... |
soit :
| E(x) = ex |
Fonction génératrice ordinaire et exponentielle
| Type | Définition | Usage courant |
|---|---|---|
| Ordinaire | ∑ anxn | Objets non étiquetés, suites et récurrences |
| Exponentielle | ∑ anxn/n! | Objets étiquetés, permutations et partitions |
| De probabilité | ∑ P(X=n)xn | Variables aléatoires entières |
| De Dirichlet | ∑ an/ns | Théorie des nombres |
Le type de fonction génératrice choisi dépend de la structure du problème.
Fonction génératrice de probabilité
Pour une variable aléatoire discrète X prenant des valeurs entières naturelles, la fonction génératrice de probabilité est définie par :
|
Gx(s) = E[sx] |
soit :
|
Gx(s) = ∑n=0∞ P(X=n)sn |
Les coefficients correspondent aux probabilités :
| P(X=n) |
Cette fonction permet notamment de calculer :
- la somme des probabilités ;
- l'espérance ;
- la variance ;
- la distribution d'une somme de variables indépendantes.
Espérance à partir de la fonction génératrice
Si la fonction génératrice de probabilité est dérivable, alors :
| Gx'(1) = E[X] |
La seconde dérivée fournit :
|
Gx''(1) = E[X(X-1)] |
Ces relations permettent de calculer les moments d'une distribution sans effectuer directement toutes les sommes.
Lorsque deux variables aléatoires indépendantes sont additionnées, la fonction génératrice de leur somme est le produit de leurs fonctions génératrices respectives.
Fonctions génératrices de Dirichlet
Une fonction génératrice de Dirichlet est une série de la forme :
|
D(s) = ∑n=1∞ an/ns |
Elle est principalement utilisée en théorie analytique des nombres.
Par exemple, pour la suite constante :
| an = 1 |
on obtient la fonction zêta de Riemann :
|
ζ(s) = ∑n=1∞ 1/ns |
Les séries de Dirichlet permettent d'étudier les propriétés multiplicatives des entiers, les nombres premiers et diverses fonctions arithmétiques.
Dénombrement avec des pièces de monnaie
Les fonctions génératrices peuvent servir à compter les façons de former une somme avec des pièces de différentes valeurs.
Supposons que l'on dispose d'un nombre illimité de pièces de valeurs :
| 1, 2 et 5 |
Pour les pièces de valeur 1, la fonction génératrice est :
|
1 + x + x2 + x3 + ... = 1/(1-x) |
Pour celles de valeur 2 :
|
1 + x2 + x4 + x6 + ... = 1/(1-x2) |
Pour celles de valeur 5 :
|
1 + x5 + x10 + x15 + ... = 1/(1-x5) |
La fonction génératrice totale est donc :
|
A(x) = 1/((1-x)(1-x2)(1-x5)) |
Le coefficient de xn indique le nombre de façons de former la somme n.
Exemple de somme monétaire
Pour rechercher le nombre de façons de former la valeur 5, on examine :
| [x5]A(x) |
avec :
|
A(x) = 1/((1-x)(1-x2)(1-x5)) |
Les possibilités sont :
|
1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 2 + 2 + 1 5 |
Il existe donc quatre façons de former la somme 5 lorsque l'ordre des pièces n'est pas pris en compte.
Restrictions sur le nombre d'objets
Les fonctions génératrices permettent de représenter facilement des restrictions.
Supposons qu'un objet de poids 3 puisse être sélectionné :
- zéro fois ;
- une fois ;
- deux fois.
La fonction génératrice correspondante est :
| 1 + x3 + x6 |
S'il peut être sélectionné un nombre illimité de fois, on utilise :
| 1 + x3 + x6 + x9 + ... |
soit :
| 1/(1-x3) |
S'il doit être sélectionné exactement une fois, la contribution est simplement :
| x3 |
Génération des combinaisons
Supposons que plusieurs catégories d'objets possèdent différentes tailles ou valeurs.
Chaque catégorie peut être représentée par une fonction génératrice indiquant les contributions possibles.
Le produit des fonctions génératrices représente alors toutes les combinaisons possibles.
Le coefficient d'une puissance donnée indique le nombre de combinaisons produisant la valeur totale correspondante.
Cette méthode permet de transformer un problème combinatoire en une multiplication de polynômes ou de séries.
Convolution et programmation
La multiplication des fonctions génératrices correspond à une convolution des suites.
Pour deux tableaux :
| a[0..n] |
et :
| b[0..m] |
la convolution est définie par :
|
c[k] = ∑i a[i] × b[k-i] |
pour tous les indices valides.
Un algorithme direct peut être écrit ainsi :
|
MODULE Convolution(a,b) Créer tableau c de longueur longueur(a) + longueur(b) - 1 Initialiser tous les éléments de c à 0 POUR i ← 0 JUSQU'A longueur(a)-1 POUR j ← 0 JUSQU'A longueur(b)-1 c[i+j] ← c[i+j] + a[i] × b[j] FIN POUR FIN POUR RETOURNER c |
Les tableaux a, b et c représentent les coefficients des polynômes ou des fonctions génératrices tronquées.
Complexité de la convolution directe
Si les deux suites contiennent respectivement n et m coefficients, l'algorithme direct effectue environ :
| n × m |
multiplications.
Sa complexité temporelle est donc :
| O(nm) |
Lorsque :
| n = m |
elle devient :
| O(n2) |
La mémoire nécessaire pour le résultat est :
| O(n+m) |
Pour des polynômes très grands, des méthodes plus rapides peuvent être utilisées.
Transformée de Fourier rapide
La transformée de Fourier rapide, ou FFT, permet de multiplier de grands polynômes plus efficacement.
Le principe général consiste à :
- évaluer les polynômes en plusieurs points ;
- multiplier les valeurs correspondantes ;
- reconstruire les coefficients du produit.
La complexité peut être réduite à environ :
| O(n log n) |
au lieu de :
| O(n2) |
Cette technique est utilisée dans :
- la multiplication de polynômes ;
- les convolutions ;
- le traitement du signal ;
- les grands entiers ;
- certains problèmes combinatoires.
Exemple en Java
L'exemple suivant effectue la convolution directe de deux tableaux représentant des polynômes :
- import java.util.Arrays;
-
- public class FonctionGeneratriceSample {
-
- public static long[] convolution(
- long[] a,
- long[] b
- ) {
- if (a == null || b == null) {
- throw new IllegalArgumentException(
- "Les tableaux ne doivent pas être nuls."
- );
- }
-
- if (a.length == 0 || b.length == 0) {
- return new long[0];
- }
-
- long[] resultat =
- new long[a.length + b.length - 1];
-
- for (int i = 0; i < a.length; i++) {
- for (int j = 0; j < b.length; j++) {
- resultat[i + j] += a[i] * b[j];
- }
- }
-
- return resultat;
- }
-
- public static void main(String[] args) {
- long[] a = {1, 1, 1};
- long[] b = {1, 1};
-
- long[] produit = convolution(a, b);
-
- System.out.println(
- Arrays.toString(produit)
- );
- }
- }
Les tableaux représentent :
| A(x) = 1 + x + x2 |
et :
| B(x) = 1 + x |
Résultat du produit
Le programme retourne :
| [1, 2, 2, 1] |
Ce tableau représente le polynôme :
| 1 + 2x + 2x2 + x3 |
En effet :
|
(1+x+x2)(1+x) = 1 + 2x + 2x2 + x3 |
Chaque coefficient est obtenu par convolution des deux suites d'origine.
Extraction d'un coefficient par programmation dynamique
Dans certains problèmes, il n'est pas nécessaire de calculer toute la fonction génératrice jusqu'à l'infini.
Il suffit de conserver les coefficients jusqu'à une puissance maximale N.
Par exemple, pour compter les façons de produire une somme avec différentes pièces :
|
MODULE CompterCombinaisons(pièces,N) Créer tableau façons[0..N] façons[0] ← 1 POUR CHAQUE pièce DANS pièces POUR somme ← pièce JUSQU'A N façons[somme] ← façons[somme] + façons[somme-pièce] FIN POUR FIN POUR RETOURNER façons |
Le tableau obtenu représente les coefficients d'une fonction génératrice tronquée.
Lien avec la programmation dynamique
De nombreux algorithmes de programmation dynamique peuvent être interprétés comme des opérations sur des fonctions génératrices.
Par exemple :
- le problème du rendu de monnaie correspond à un produit de séries géométriques ;
- le problème du sous-ensemble de somme donnée correspond à un produit de polynômes ;
- certains problèmes de partitions correspondent à des produits infinis ;
- les convolutions correspondent à des combinaisons de sous-problèmes.
L'interprétation par fonction génératrice fournit souvent une justification mathématique à une récurrence de programmation dynamique.
Problème du sous-ensemble
Supposons que l'on possède des objets de poids :
| w1, w2, ..., wn |
Chaque objet peut être sélectionné ou non.
L'objet de poids wi est représenté par :
| 1 + xwi |
Le produit :
| ∏i=1n (1+xwi) |
représente tous les sous-ensembles possibles.
Le coefficient de xs indique le nombre de sous-ensembles dont la somme des poids vaut s.
Si ce coefficient est supérieur à zéro, il existe au moins un sous-ensemble produisant cette somme.
Partitions d'un entier
Une partition d'un entier n est une façon d'écrire n comme une somme d'entiers positifs, sans tenir compte de l'ordre.
La fonction génératrice des nombres de partitions est :
|
P(x) = ∏k=1∞ 1/(1-xk) |
Chaque facteur :
| 1/(1-xk) |
représente la possibilité d'utiliser l'entier k zéro, une ou plusieurs fois.
Le coefficient de xn dans P(x) correspond au nombre de partitions de n.
Exemple de partitions
Les partitions de 4 sont :
|
4 3 + 1 2 + 2 2 + 1 + 1 1 + 1 + 1 + 1 |
Il existe donc :
| p(4) = 5 |
Le coefficient de x4 dans :
| ∏k=1∞ 1/(1-xk) |
est donc égal à 5.
Fonctions génératrices multivariées
Une fonction génératrice peut utiliser plusieurs variables.
Par exemple :
|
A(x,y) = ∑n=0∞ ∑k=0∞ an,kxnyk |
Le coefficient :
| [xnyk]A(x,y) |
correspond à la valeur an,k.
Une variable peut représenter la taille d'un objet, tandis qu'une autre représente son nombre de composantes, son coût, sa couleur ou une autre caractéristique.
Ces fonctions sont utiles pour étudier simultanément plusieurs paramètres combinatoires.
Exemple bivarié
Supposons que l'on veuille compter des chaînes selon :
- leur longueur ;
- leur nombre de caractères particuliers.
La puissance de x peut représenter la longueur totale, tandis que la puissance de y représente le nombre de caractères particuliers.
Un terme :
| 5x8y3 |
indiquerait alors qu'il existe cinq objets :
- de taille 8 ;
- contenant trois éléments particuliers.
Les fonctions génératrices multivariées permettent ainsi de conserver plusieurs informations dans une seule expression.
Composition de fonctions génératrices
La composition :
| A(B(x)) |
peut représenter la substitution d'une structure combinatoire dans une autre.
Cette opération doit être utilisée avec certaines conditions, notamment lorsque le terme constant de B(x) est nul dans le contexte des séries formelles.
La composition apparaît dans :
- les structures récursives ;
- les arbres ;
- les partitions ;
- les objets construits à partir d'autres objets ;
- les équations fonctionnelles.
Elle peut produire des relations implicites dont les coefficients sont calculés récursivement.
Équations fonctionnelles
Certaines structures récursives conduisent à une équation portant directement sur leur fonction génératrice.
Par exemple, une famille d'arbres peut être décrite par une relation comme :
|
T(x) = x(1+T(x))2 |
L'expression indique qu'un arbre est constitué :
- d'une racine représentée par x ;
- de deux sous-structures possibles représentées par 1+T(x).
La résolution ou le développement de cette équation permet de déterminer le nombre d'arbres de chaque taille.
Nombres de Catalan
Les nombres de Catalan apparaissent dans le dénombrement de nombreuses structures, notamment :
- les parenthésages corrects ;
- certains arbres binaires ;
- les triangulations d'un polygone ;
- les chemins ne franchissant pas une diagonale.
Leur fonction génératrice C(x) satisfait :
|
C(x) = 1 + xC(x)2 |
La résolution de cette équation quadratique donne :
|
C(x) = (1-√(1-4x))/(2x) |
Le développement en série produit les nombres :
| 1, 1, 2, 5, 14, 42, 132, ... |
Extraction de coefficients
Le but principal d'une fonction génératrice est souvent de déterminer :
| [xn]A(x) |
Plusieurs méthodes peuvent être utilisées :
- développement direct en série ;
- identité connue ;
- produit de Cauchy ;
- décomposition en fractions partielles ;
- dérivation ou intégration ;
- récurrence sur les coefficients ;
- formule binomiale ;
- calcul symbolique ;
- analyse asymptotique.
Le choix dépend de la forme de la fonction génératrice.
Développement binomial généralisé
Le développement suivant est particulièrement utile :
|
1/(1-x)m = ∑n=0 ∞ C(n+m-1,m-1)xn |
Par conséquent :
|
[xn] 1/(1-x)m = C(n+m-1,m-1) |
Par exemple :
|
1/(1-x)3 = 1 + 3x + 6x2 + 10x3 + ... |
Le coefficient de xn est :
| C(n+2,2) |
Cette identité apparaît souvent dans les problèmes de sélection avec répétition.
Analyse asymptotique
La position et la nature des singularités d'une fonction génératrice peuvent fournir des renseignements sur la croissance de ses coefficients.
Par exemple, une fonction contenant :
| 1/(1-rx) |
possède des coefficients :
| rn |
La singularité située en :
| x = 1/r |
est directement liée à cette croissance exponentielle.
De manière générale, la singularité la plus proche de l'origine joue souvent un rôle déterminant dans le comportement asymptotique des coefficients.
Rayon de convergence
Lorsqu'une fonction génératrice est considérée comme une fonction analytique, sa série possède un rayon de convergence.
La série :
| ∑n=0∞ anxn |
converge généralement pour :
| |x| < R |
où R est le rayon de convergence.
La formule de Cauchy-Hadamard donne :
|
1/R = lim sup |an|1/n |
La croissance des coefficients et le rayon de convergence sont donc étroitement liés.
Avantages des fonctions génératrices
Les fonctions génératrices présentent plusieurs avantages :
- elles regroupent une suite complète dans une seule expression ;
- elles transforment les récurrences en équations algébriques ;
- elles simplifient certains problèmes de dénombrement ;
- elles relient les convolutions à la multiplication ;
- elles permettent d'obtenir des formules explicites ;
- elles facilitent l'étude des sommes partielles ;
- elles fournissent des méthodes d'analyse asymptotique ;
- elles offrent une interprétation mathématique à certains algorithmes de programmation dynamique.
Limites et précautions
Plusieurs précautions doivent être prises :
- la manipulation formelle ne doit pas être confondue avec l'évaluation numérique ;
- les questions de convergence sont importantes dans un contexte analytique ;
- l'extraction des coefficients peut être difficile ;
- les expressions intermédiaires peuvent devenir complexes ;
- les coefficients peuvent dépasser rapidement les types numériques ordinaires ;
- une convolution directe peut être coûteuse ;
- certaines compositions exigent un terme constant nul ;
- une fonction génératrice ne fournit pas toujours immédiatement une formule simple ;
- les approximations asymptotiques peuvent ne pas convenir aux petits indices.
Applications
Les fonctions génératrices sont utilisées dans de nombreux domaines :
- combinatoire ;
- théorie des nombres ;
- probabilités ;
- statistiques ;
- résolution de récurrences ;
- analyse des algorithmes ;
- programmation dynamique ;
- dénombrement de chemins ;
- partitions d'entiers ;
- arbres et graphes ;
- traitement du signal ;
- multiplication de polynômes ;
- calcul symbolique ;
- analyse asymptotique ;
- théorie des langages formels.
Elles interviennent également dans l'étude des suites spéciales, comme les nombres de Fibonacci, les nombres de Catalan et les nombres de Bell.
Comparaison avec un tableau informatique
Une fonction génératrice peut être comparée à un tableau indexé.
La suite :
| a0, a1, a2, ... |
est représentée en programmation par :
| a[0], a[1], a[2], ... |
Dans la fonction génératrice :
|
A(x) = a0 + a1x + a2x2 + ... |
l'exposant de x joue le rôle de l'indice du tableau.
Les opérations algébriques sur A(x) correspondent alors à certaines opérations globales sur les données :
| Opération algébrique | Effet sur la suite |
|---|---|
| Addition | Addition terme par terme |
| Multiplication par x | Décalage d'un indice |
| Multiplication | Convolution |
| Dérivation | Multiplication du terme par son indice |
| Division par 1-x | Calcul des sommes partielles |
| Composition | Substitution de structures |
Cette analogie facilite la compréhension de leur utilité en programmation.
Complexité des calculs
La complexité dépend de l'opération effectuée et du nombre de coefficients conservés.
| Opération sur N coefficients | Complexité courante |
|---|---|
| Addition | O(N) |
| Multiplication par un scalaire | O(N) |
| Décalage | O(N) ou O(1) selon la représentation |
| Dérivation | O(N) |
| Intégration | O(N) |
| Convolution directe | O(N2) |
| Convolution par FFT | O(N log N) |
| Extraction directe d'un coefficient | Variable |
Pour les séries infinies, les programmes utilisent généralement une troncature à un degré maximal.
Représentation informatique
Une fonction génératrice tronquée peut être représentée par un tableau :
| coefficients[n] = [xn]A(x) |
Par exemple, le polynôme :
| 3 + 2x + 5x2 |
peut être représenté par :
| [3, 2, 5] |
Cette représentation permet d'utiliser les algorithmes classiques sur les polynômes.
Pour les séries très clairsemées, une table associative peut être utilisée afin de conserver uniquement les coefficients non nuls.
Calcul exact et calcul approché
Les coefficients d'une fonction génératrice peuvent être calculés avec différents types numériques :
- entiers ordinaires ;
- entiers multiprécision ;
- nombres rationnels ;
- valeurs modulaires ;
- nombres à virgule flottante ;
- nombres complexes.
Le choix dépend du problème.
Les problèmes de dénombrement exigent généralement des entiers exacts, tandis que l'analyse asymptotique ou numérique peut utiliser des approximations en virgule flottante.
Remarque
Les fonctions génératrices permettent de traiter une suite entière comme une seule expression algébrique. Cette transformation rend possibles des opérations qui seraient difficiles à appliquer directement terme par terme. Une relation de récurrence devient une équation, une convolution devient un produit et un problème de dénombrement devient une extraction de coefficient.
En programmation, elles fournissent également une interprétation théorique à plusieurs techniques pratiques, notamment la programmation dynamique, la multiplication de polynômes, le rendu de monnaie et le calcul de sous-ensembles. Leur étude constitue une transition naturelle vers des sujets comme les relations de récurrence, les nombres de Catalan, les probabilités discrètes, l'analyse asymptotique et les méthodes de convolution rapide.