Les fonctions génératrices peuvent être utilisées pour effectuer un comptage, un dénombrement.
Soit, par exemple, un ensemble de n valeurs réelles :
$$\Omega = \{ a_1 , a_2 , a_3 , ... , a_n \}$$
On désire savoir combien de parties de $\Omega$ ont la somme de leurs éléments égale à un certain nombre $\alpha$. Soit $T(\alpha)$ la fonction qui donne ce résultat.
Pour la plupart des valeurs de $\alpha$, $T(\alpha)$ est nulle. S’il existe une partie de $\Omega$ dont la somme des éléments est égale à $\alpha$, alors $T(\alpha)$ sera égale à $1$. S’il en existe $2$, $T(\alpha)$ sera égale à $2$, etc.
Eh bien la fonction génératrice de $T(\alpha)$ peut être obtenue par :
$$f(x)=(1+x^{a_1})(1+x^{a_2})(1+x^{a_3})...(1+x^{a_n})$$
Ici nous n’obtenons pas un polynôme, mais une combinaison linéaire de puissance de $x$ qui ne sont pas forcément des nombres entiers. Ce sont les résultats des sommes partielles des $a_i$ .
En revanche les coefficients multiplicateurs sont des entiers. Le coefficient multiplicateur de $x^\alpha$ est le nombre de parties de $\Omega$ dont la sommes des éléments est égale à $\alpha$ .
Les valeurs de $\alpha$ qui apparaîtront seront toutes les valeurs possibles des sommes partielles des $a_i$ .
Si ces sommes partielles donnent toutes des sommes différentes, c’est-à-dire, s’il n’y en a pas deux qui donnent la même somme, alors tous les coefficients des $x^\alpha$ seront égaux à 1 .
Cas d'entiers successifs
Considérons le cas où $\Omega= \{ 1 , 2 , 3 , ... , n \}$. Dans ce cas, la fonction génératrice est égale à :
$f(x)=(1+x)(1+x^2)(1+x^3)(1+x^4)...(1+x^n)$ et est un polynôme de degré $\frac {n(n+1)} 2$.
Par exemple, si $\Omega = \{ 1 , 2 , 3 , 4 \}$, la fonction génératrice se développe en :
$f(x)=(1+x)(1+x^2)(1+x^3)(1+x^4)=1+x+x^2+2x^3+2x^4+2x^5+2x^6+2x^7+x^8+x^9+x^{10}$
On voit que les parties de $\Omega$ qui donnent des sommes égales à $3$, $4$, $5$, $6$ ou $7$ sont au nombre de $2$ pour chacune de ces valeurs, les autres étant seules.
Comptage des éléments d'un hyper-cube
On appelle hyper-cube la généralisation en dimension quelconque d'un cube :
- en dimension $3$, c'est ... un cube,
- en dimension $2$, c'est un carré,
- en dimension $1$, c'est un segment de droite,
- en dimension $0$, c'est un point,
- et en dimension $n$ quelconque, c'est ... un hypercube de dimension $n$.
Eh bien la fonction génératrice permettant de compter les éléments d'un hyper-cube est la suivante :
$f(x)=(2+x)^n$ .
Le coefficient de $x^p$ donne le nombre d'éléments de dimension $p$ .
Le carré
Par exemple, pour le carré :
$f(x)=(2+x)^2=4+4x+x^2$ .
Et dans un carré, il y a bien :
- 4 points, les éléments de dimension 0, les sommets,
- 4 cotés, les éléments de dimension 1,
- et un élément de dimension 2, le carré lui-même.
Le cube
Vérifions que cela marche aussi pour un cube :
$f(x)=(2+x)^3=8+12x+6x^2+x^3$ .
Dans un cube il y a bien :
- 8 sommets : dimension 0,
- 12 cotés, les arrêtes : dimension 1,
- 6 faces : dimension 2,
- 1 élément de dimension 3 : le cube lui-même.
