3.1 Les fonctions génératrices ordinaires

Les fonctions génératrices sont un outil particulièrement utile dans l’étude de la combinatoire. Elles nous permettent en particulier d’appliquer les techniques de l’analyse et de l’algèbre aux problèmes de combinatoire, notamment dans le contexte des récurrences.

L’idée est de transformer une suite (qui décrit la solution d’un problème) sous forme de série. Par exemple, la solution du problème des chaînes binaires du chapitre précédent nous a permis d’obtenir la suite

an=(2,3,5,8,13,21,34,55,89,144,…)\displaystyle a_{n}=(2,3,5,8,13,21,34,55,89,144,...)

Nous pouvons alors penser à ces nombres comme les coefficients d’un polynôme de degré infini (i.e. une série). On obtient donc la série:

2⁢x+3⁢x2+5⁢x3+8⁢x4+13⁢x5+21⁢x6+34⁢x7+55⁢x8+89⁢x9+144⁢x10+…\displaystyle 2x+3x^{2}+5x^{3}+8x^{4}+13x^{5}+21x^{6}+34x^{7}+55x^{8}+89x^{9}+% 144x^{10}+...

Notez que les exposants dans notre série représentent la position du coefficient dans notre suite. L’intérêt des fonctions (séries) génératrices vient du fait qu’il est souvent possible de trouver une forme condensée avec laquelle il est plus facile de travailler. Dans le contexte des fonctions génératrices ordinaires, c’est la série géométrique qui joue un rôle particulièrement important. Il s’agit de la fonction génératrice de la suite (1,1,1,1,…..)\displaystyle(1,1,1,1,.....).

Théorème 3.1.1:

Somme et série géométrique. On a les deux sommes suivantes:

∑k=0nxk=1−xn+11−x et ∑k=0∞xk=11−x\displaystyle\sum_{k=0}^{n}x^{k}=\frac{1-x^{n+1}}{1-x}\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \textrm{ et }\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \sum_{k=0}^{\infty}x^{k}=% \frac{1}{1-x}

Approche analytique

Il est facile de voir que la fonction génératrice de la suite (1,1,1,1,…..)\displaystyle(1,1,1,1,.....) est tout simplement 1+x+x2+x3+x4+…=∑k=0∞xk\displaystyle 1+x+x^{2}+x^{3}+x^{4}+...=\sum_{k=0}^{\infty}x^{k}. Nous voulons maintenant chercher une forme condensé de notre fonction génératrice. Pour ce faire, posons Sn=∑k=0nxk\displaystyle S_{n}=\sum_{k=0}^{n}x^{k}. On a donc:

Sn\displaystyle\displaystyle S_{n} =\displaystyle\displaystyle= 1+x+x2+x3+x4+…+xn\displaystyle\displaystyle 1+x+x^{2}+x^{3}+x^{4}+...+x^{n}
x⁢Sn\displaystyle\displaystyle xS_{n} =\displaystyle\displaystyle= x+x2+x3+x4+…+xn+xn+1\displaystyle\displaystyle x+x^{2}+x^{3}+x^{4}+...+x^{n}+x^{n+1}

Ceci nous permet donc d’obtenir x⁢Sn−Sn=xn+1−1\displaystyle xS_{n}-S_{n}=x^{n+1}-1. En isolant le Sn\displaystyle S_{n}, on obtient donc:

Sn=xn+1−1x−1=1−xn+11−x\displaystyle S_{n}=\frac{x^{n+1}-1}{x-1}=\frac{1-x^{n+1}}{1-x}

Finalement, pour trouver la fonction génératrice, il ne nous reste plus qu’à prendre la limite quand n\displaystyle n tend vers l’infini, ce qui nous donne:

limn→∞Sn=limn→∞1−xn+11−x=11−x si ⁢|x|<1\displaystyle\lim_{n\rightarrow\infty}S_{n}=\lim_{n\rightarrow\infty}\frac{1-x% ^{n+1}}{1-x}=\frac{1}{1-x}\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \textrm{ si }|x|<1

La fonction génératrice de la suite (1,1,1,1,…)\displaystyle(1,1,1,1,...) est donc 11−x\displaystyle\frac{1}{1-x}. Remarquez cependant qu’en prenant la limite, nous avons du ajouter la condition |x|<1\displaystyle|x|<1. Cette condition est nécessaire avec une approche analytique, car autrement la série est divergente. Remarquez cependant que dans le contexte des séries génératrices, il est possible d’ignorer complètement cette condition. Ceci est possible grâce à une approche algébrique.

Approche algébrique

Bien que l’approche analytique que nous venons de voir nous permette de traiter une fonction génératrice comme une véritable fonction et d’appliquer les techniques du calcul différentiel et intégral, telles que le calcul des limites, des dérivées et des intégrales d’une fonction génératrice, le rayon de convergence qui apparaît peut sembler un peu étrange. La raison vient du fait qu’en réalité, une fonction génératrice n’est pas une série au sens analytique, mais plutôt une série formelle. C’est l’algèbre moderne, et en particulier la théorie des espaces vectoriels et la théorie des anneaux, qui nous permet de leur donner un sens précis.

L’idée d’une série formelle est de définir un nouvel objet, muni d’opérations d’addition et de multiplication, et d’en étudier les propriétés. Ceci est fait sans donner un sens aux x\displaystyle x. Il n’est donc pas possible de remplacer x\displaystyle x par une valeur, car il ne s’agit pas d’une variable, mais d’un objet abstrait. L’avantage de cette approche est qu’elle nous permet d’éviter complètement la question de convergence.

Nous voulons maintenant utiliser une approche algébrique pour retrouver la fonction génératrice de la suite (1,1,1,1,…)\displaystyle(1,1,1,1,...). Pour ce faire, remarquons que si l’on pose

S=∑k=0∞xk=1+x+x2+x3+…\displaystyle S=\sum_{k=0}^{\infty}x^{k}=1+x+x^{2}+x^{3}+...

alors on obtient:

S−x⁢S=(1+x+x2+x3+…)−x⁢(1+x+x2+x3+…)=1\displaystyle S-xS=(1+x+x^{2}+x^{3}+...)-x(1+x+x^{2}+x^{3}+...)=1

En isolant le S\displaystyle S, on obtient donc le même résultat que précédemment:

∑k=0∞xk=11−x\displaystyle\sum_{k=0}^{\infty}x^{k}=\frac{1}{1-x}

Remarquez que, bien que ces deux approches soient tout à fait interchangeables dans le contexte de la combinatoire, il existe tout de même des différences importantes dans leur interprétation. Ceci signifie, entre autres, que ces deux approches ne doivent pas être confondues dans les cours d’analyse et d’algèbre. En analyse, la valeur du x\displaystyle x joue un rôle important, ce qui rend la seconde approche incorrecte. Par contre, la seconde approche ne permet techniquement pas de calculer la dérivée ou l’intégrale, ce qui nous sera essentiel. En combinatoire, c’est théoriquement la seconde approche qui est correcte, mais nous allons librement combiner ces deux techniques pour éviter de devoir définir une dérivée et une intégrale formelles. De manière concrète, les deux résultats seraient les mêmes de toute façon ; c’est au niveau des démonstrations que se trouvent les difficultés.