3.4 Les fonctions génératrices exponentielles

Au chapitre précédent, nous avons eu l’occasion d’étudier plusieurs problèmes concernant des récurrences avec un seul paramètre. Ceci est particulièrement utile pour résoudre des problèmes où il y a des contraintes sur la position des objets. D’un autre côté, depuis le début du chapitre, nous avons étudié les fonctions génératrices. Ces dernières sont particulièrement utiles pour résoudre des problèmes où les contraintes portent sur les quantités. Il faut cependant faire attention, car les fonctions génératrices ordinaires ne tiennent pas compte (par défaut) de l’ordre des objets.

La méthode des fonctions génératrices exponentielles que nous allons introduire immédiatement nous permet à nouveau de traiter des problèmes avec des contraintes sur les quantités, mais cette fois en tenant compte de l’ordre des objets. Si $\displaystyle a_{0},a_{1},a_{2},a_{3},...$ est une suite, alors on définit la fonction génératrice exponentielle de cette suite comme étant:

\displaystyle a_{0}+a_{1}\frac{x^{1}}{1!}+a_{2}\frac{x^{2}}{2!}+a_{3}\frac{x^{% 3}}{3!}+...=\sum_{n=0}^{\infty}a_{n}\frac{x^{n}}{n!}

L’intérêt des fonctions génératrices exponentielles vient du fait que le produit fonctionne différemment de celui des fonctions génératrices ordinaires. Pour mieux comprendre, regardons les deux produits suivants. Le premier correspond au produit de deux fonctions génératrices ordinaires, alors que le second correspond au produit de deux fonctions génératrices exponentielles.

Théorème 3.4.1:

Produit des fonctions génératrices.

	$\displaystyle\displaystyle\left(\sum_{n=0}^{\infty}a_{n}x^{n}\right)\left(\sum% _{n=0}^{\infty}b_{n}x^{n}\right)$	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}a_{k}b_{n-k}% \right)x^{n}$
	$\displaystyle\displaystyle\left(\sum_{n=0}^{\infty}a_{n}\frac{x^{n}}{n!}\right% )\left(\sum_{n=0}^{\infty}b_{n}\frac{x^{n}}{n!}\right)$	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}\frac{a_{k}}{% k!}\cdot\frac{b_{n-k}}{(n-k)!}\right)x^{n}=\sum_{n=0}^{\infty}\left(\sum_{k=0}% ^{n}\binom{n}{k}a_{k}b_{n-k}\right)\frac{x^{n}}{n!}$

La seule différence importante entre ces deux produits est la présence du coefficient binomial dans le cas de la fonction génératrice exponentielle. Bien que cette différence puisse sembler mineure, elle est en fait particulièrement importante. Elle sert à choisir la position des éléments provenant de notre première suite. Autrement dit, c’est ce coefficient binomial qui permet de compter le nombre de configurations en tenant compte de l’ordre, ce qui n’était pas le cas pour les fonctions génératrices ordinaires.

Dans le cas des fonctions génératrices ordinaires, la fonction génératrice de la suite $\displaystyle(1,1,1,1,...)$ joue un rôle particulièrement important et porte le nom de série géométrique. Nous allons maintenant considérer à nouveau cette même suite, mais cette fois dans le contexte des fonctions génératrices exponentielles. Nous allons donc poser:

\displaystyle y(x)=\sum_{k=0}^{\infty}\frac{x^{k}}{k!}

En prenant la dérivée, on obtient donc:

\displaystyle y^{\prime}(x)=\sum_{k=1}^{\infty}\frac{kx^{k-1}}{k!}=\sum_{k=1}^% {\infty}\frac{x^{k-1}}{(k-1)!}=\sum_{k=0}^{\infty}\frac{x^{k}}{k!}=y(x)

Ce qui nous permet d’affirmer que $\displaystyle y(x)=Ce^{x}$ , où $\displaystyle C$ est une constante que l’on peut trouver à partir d’une valeur initiale. Il n’est pas très difficile de voir que $\displaystyle y(0)=1$ , ce qui nous donne le théorème suivant.

Théorème 3.4.2:

Série de la fonction exponentielle.

\displaystyle\sum_{k=0}^{\infty}\frac{x^{k}}{k!}=e^{x}

Ce théorème est la raison pour laquelle ces fonctions génératrices portent le nom d’exponentielle.

Exemple 3.4.1.

De combien de façons peut-on choisir un code d’accès de $\displaystyle 5$ caractères qui doivent être choisi parmi les lettres $\displaystyle A,B$ et $\displaystyle C$ . Pour ce faire, remarquons que nous pouvons choisir autant de fois que nous le voulons chacune des trois lettres. Si on dénote par $\displaystyle a_{n}$ le nombre de code d’accès que l’on peut former avec $\displaystyle n$ caractères, alors la fonction génératrice est:

\displaystyle\sum_{n=0}^{\infty}a_{n}\frac{x^{n}}{n!}=\left(1+x+\frac{x^{2}}{2% !}+\frac{x^{3}}{3!}+...\right)^{3}=\left(\sum_{n=0}^{\infty}\frac{x^{n}}{n!}% \right)^{3}=(e^{x})^{3}=e^{3x}=\sum_{n=0}^{\infty}\frac{(3x)^{n}}{n!}=\sum_{n=% 0}^{\infty}3^{n}\frac{x^{n}}{n!}

Il y a donc $\displaystyle 3^{n}$ code d’accès possible de $\displaystyle n$ caractères. En particulier, nous avons $\displaystyle 3^{5}=243$ codes de $\displaystyle 5$ caractères. Ceci correspond à ce que nous aurions pu obtenir directement à l’aide du principe du produit.

Exemple 3.4.2.

De combien de façons peut-on choisir un code d’accès de $\displaystyle 5$ caractères qui doivent être choisi parmi les lettres $\displaystyle A,B$ et $\displaystyle C$ , si le code doit contenir au moins un $\displaystyle A$ et un maximum de trois $\displaystyle B$ . Pour ce faire, nous allons procéder essentiellement de la même façon que dans l’exemple précédent, mais en ajustant le nombre de chaque lettre disponible.

$\displaystyle\displaystyle\sum_{n=0}^{\infty}a_{n}\frac{x^{n}}{n!}$	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle\left(x+\frac{x^{2}}{2}+\frac{x^{3}}{3}+\frac{x^{4}}% {4!}+\frac{x^{5}}{5!}\right)\left(1+x+\frac{x^{2}}{2}+\frac{x^{3}}{3}\right)% \left(1+x+\frac{x^{2}}{2}+\frac{x^{3}}{3}+\frac{x^{4}}{4!}+\frac{x^{5}}{5!}\right)$
	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle\left(\sum_{n=1}^{5}\frac{x^{n}}{n!}\right)\left(% \sum_{n=0}^{3}\frac{x^{n}}{n!}\right)\left(\sum_{n=0}^{5}\frac{x^{n}}{n!}\right)$
	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle\frac{1}{86400}x^{13}+\frac{13}{86400}x^{12}+\frac{1% 01}{86400}x^{11}+\frac{581}{86400}x^{10}+\frac{53}{1728}x^{9}+\frac{65}{576}x^% {8}+\frac{41}{120}x^{7}+\frac{613}{720}x^{6}+...$
		$\displaystyle\displaystyle...+\frac{103}{60}x^{5}+\frac{65}{24}x^{4}+\frac{19}% {6}x^{3}+\frac{5}{2}x^{2}+x$
	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle 72072\frac{x^{13}}{13!}+72072\frac{x^{12}}{12!}+466% 62\frac{x^{11}}{11!}+24402\frac{x^{10}}{10!}+11130\frac{x^{9}}{9!}+4550\frac{x% ^{8}}{8!}+1722\frac{x^{7}}{7!}+613\frac{x^{6}}{6!}+...$
		$\displaystyle\displaystyle...+206\frac{x^{5}}{5!}+65\frac{x^{4}}{4!}+19\frac{x% ^{3}}{3!}+5\frac{x^{2}}{2!}+x$

avec $\displaystyle 5$ caractères, on a donc un total de $\displaystyle 206$ options qui satisfont les conditions. Pour trouver directement cette valeur, on peut utiliser le code Python suivant:

Listing 22: Problème de codes d’accès

⬇


                1
                
                
                
              from sympy import *


                2
                
                
                
              from pandas import *


                3
                
                
                
              init_printing()


                4
                
                
                
              


                5
                
                
                
              x = Symbol(’x’)


                6
                
                
                
              p1 = sum([x**i/factorial(i) for i in range(1,6)])


                7
                
                
                
              p2 = sum([x**i/factorial(i) for i in range(0,4)])


                8
                
                
                
              p3 = sum([x**i/factorial(i) for i in range(0,6)])


                9
                
                
                
              expand(p1*p2*p3).coeff(x**5)*factorial(5)