Série génératrice

Imaginons que l’on compte des objets selon leur taille. Pour les structures comptées par les nombres de Catalan, les cinq premiers totaux sont 1, 1, 2, 5 et 14. Une série génératrice range ces valeurs dans une seule expression : chacune devient le coefficient d’une puissance de x.

La place d’un coefficient garde la mémoire de la taille correspondante. On peut alors manipuler toute la suite en additionnant, multipliant ou dérivant cette expression, au lieu de traiter chaque terme isolément.

Soit une suite de nombres dont le terme de rang n est noté a_n. Sa série génératrice ordinaire associe au rang n la puissance n d’une indéterminée x : $A(x)={\sum }_{n=0}^{\mathrm{\infty }}{a}_n{x}^{n}A(x)=\backslash sum\_\{n=0\}^\{\backslash infty\}\; a\_n\; x^n$. Le coefficient de xⁿ est donc exactement a_n. Cette correspondance entre rang et degré est la propriété qui encode la suite entière.

Dans le cadre formel, x sert seulement à repérer les coefficients : aucune convergence n’est requise. Si x reçoit une valeur réelle et que la série converge sur un intervalle ouvert contenant 0, la même écriture définit une fonction A. Les termes se retrouvent alors par dérivation en 0 : $a_n=\frac{A^{(n)}(0)}{n!}a\_n=\backslash frac\{A^\{(n)\}(0)\}\{n!\}$. Hors de l’intervalle de convergence, l’expression formelle subsiste, mais elle ne fournit pas nécessairement une valeur numérique.

Une série génératrice réunit quatre éléments. La suite fournit les coefficients a₀, a₁, a₂, etc. L’indice n indique leur rang. L’indéterminée x transforme ce rang en degré, de sorte que a_n accompagne xⁿ. Enfin, la somme rassemble tous ces monômes dans un même objet. Le rang détermine donc la puissance, tandis que la valeur du terme détermine son coefficient. Ces données suffisent à reconstruire la suite coefficient par coefficient. Pour l’exemple des nombres de Catalan, une représentation par rang rend visible l’association entre les valeurs 1, 1, 2, 5, 14 et les puissances successives.

On note C_n le nombre de Catalan de rang n. Les données sont le terme initial C₀ = 1 et la règle suivante : chaque nouveau terme est la somme des produits de deux termes dont les rangs totalisent n.

Étape 1 : C₁ = 1 × 1 = 1.
Étape 2 : C₂ = 1 × 1 + 1 × 1 = 2.
Étape 3 : C₃ = 1 × 2 + 1 × 1 + 2 × 1 = 5.
Étape 4 : C₄ = 1 × 5 + 1 × 2 + 2 × 1 + 5 × 1 = 14.

La série commence donc par 1 + x + 2x² + 5x³ + 14x⁴. Elle vérifie $C(x)=1+xC(x{)}^{2}C(x)=1+xC(x)^2$. Pour contrôler le coefficient de x⁴, on additionne 1 × 5, 1 × 2, 2 × 1 et 5 × 1 dans le carré : le total 14 retrouve bien C₄.

En combinatoire, on classe des objets par taille, puis on place leur nombre au coefficient du degré correspondant. Une énumération directe convient à quelques petites tailles ; la série génératrice devient préférable lorsqu’une même règle de construction relie tous les rangs.

Pour calculer plusieurs termes, on traduit une décomposition des objets en une identité entre séries. Les opérations algébriques produisent alors une récurrence sur les coefficients. Si seuls un ou deux termes sont nécessaires, appliquer directement la récurrence demande moins de calculs.

Pour étudier le comportement global d’une suite, on peut traiter la série comme une fonction lorsque sa convergence est établie. Sans cette vérification, on reste dans le cadre formel et l’on raisonne uniquement sur les coefficients.

Série génératrice formelle et fonction définie par une série entière. La première est une suite de coefficients manipulée algébriquement, sans valeur imposée à x. La seconde exige une valeur de x située dans un domaine de convergence. Une série divergente pour x = 2 reste donc un objet formel valide, mais ne définit pas là une valeur de fonction.

Série génératrice ordinaire et série génératrice exponentielle. Dans la première, a_n est le coefficient de xⁿ. Dans la seconde, il accompagne xⁿ/n!. Si le coefficient lu devant xⁿ doit être multiplié par n! pour retrouver a_n, la convention est exponentielle.

Série génératrice et fonction génératrice des probabilités. Cette dernière est un cas spécialisé : ses coefficients sont des probabilités et leur somme vaut 1 lorsque la variable aléatoire prend des valeurs entières naturelles. Une suite de dénombrements comme 1, 1, 2, 5, 14 ne satisfait pas ce critère.

Convergence non automatique. Une identité entre séries formelles ne garantit aucune valeur numérique pour un x donné. La convergence exige que les sommes partielles tendent vers une limite finie ; en l’absence d’une telle limite, la série diverge. Il faut déterminer le domaine de convergence avant toute substitution ; aux bornes de ce domaine, une vérification séparée est nécessaire.

Rang initial déplacé. La convention de cette fiche commence à n = 0. Si une suite commence à n = 1, son premier terme accompagne x et le coefficient constant vaut 0. Il faut annoncer l’indice initial avant de lire les coefficients.

Une valeur ne détermine pas la suite. Deux séries différentes peuvent donner le même nombre pour une valeur particulière de x. Pour identifier une série génératrice, on compare tous les coefficients ou les dérivées en 0, pas une seule évaluation.

Suite finie. Si tous les coefficients sont nuls après un certain rang, la série génératrice est un polynôme. Ce cas n’est pas un échec de la définition : la somme infinie contient simplement une infinité de termes nuls.

La fiche série formelle précise les manipulations algébriques qui ne dépendent pas de la convergence.

La fiche nombre de Catalan prolonge l’exemple conducteur et détaille la suite 1, 1, 2, 5, 14.

La fiche analyse combinatoire replace les séries génératrices parmi les outils de dénombrement des objets structurés.