3.2 Quelques exemples

Les fonctions génératrices peuvent être utilisées pour résoudre une grande variété de problèmes. En fait, la plupart des problèmes de combinatoire peuvent être étudiés d’une manière ou d’une autre en termes de fonction génératrice. C’est ce que nous allons essayer d’illustrer immédiatement à l’aide de quelques exemples.

Exemple 3.2.1.

De combien de façons peut on choisir 5 billes parmi un sac contenant 8 billes, toutes de couleurs différentes. Dans ce cas, pour chacune des $\displaystyle 8$ billes, on peut soit la choisir, soit ne pas la choisir. C’est à dire que pour chacune des billes, la fonction génératrice est donnée par $\displaystyle(1+x)$ . Il faut ensuite multiplier cette fonction génératrice pour chacune des billes. La fonction génératrice décrivant le problème est donc:

\displaystyle(1+x)^{8}

Comme nous devons choisir $\displaystyle 5$ billes, il nous faut maintenant trouver le coefficient de $\displaystyle x^{5}$ dans la fonction génératrice. Pour ce faire, on peut développer l’expression rapidement à l’aide de Python.

Listing 12: Développer le polynome

⬇


                1
                
                
                
              from sympy import *


                2
                
                
                
              from pandas import *


                3
                
                
                
              init_printing()


                4
                
                
                
              


                5
                
                
                
              x = Symbol(’x’)


                6
                
                
                
              expand((1+x)**8)

Ce qui nous donne:

\displaystyle(1+x)^{8}=1+8x+28x^{2}+56x^{3}+70x^{4}+56x^{5}+28x^{6}+8x^{7}+x^{8}

La solution du problème est donc $\displaystyle 56$ . Remarquez que nous pouvons comme dans le chapitre précédent, créer un tableau permettant de représenter les différentes possibilités.

Listing 13: Creation d’un tableau de valeurs

⬇


                1
                
                
                
              from sympy import *


                2
                
                
                
              from pandas import *


                3
                
                
                
              init_printing()


                4
                
                
                
              


                5
                
                
                
              x = Symbol(’x’)


                6
                
                
                
              polynome = Poly((1+x)**8).all_coeffs()


                7
                
                
                
              polynome.reverse()


                8
                
                
                
              tableau = DataFrame([polynome])


                9
                
                
                
              tableau.index = ["Valeurs"]


                10
                
                
                
              tableau

Ce qui nous donne:

$\displaystyle n$	0	1	2	3	4	5	6	7	8
Valeurs	1	8	28	56	70	56	28	8	1

Remarquez que cette même solution aurait pu être obtenu avec les principes de base. En utilisant le principe du produit, nous avons $\displaystyle 8\cdot 7\cdot 6\cdot 5\cdot 4$ façons de choisir les $\displaystyle 5$ billes avec de l’ordre. Pour enlever l’ordre, nous devons ensuite appliquer le principe d’équivalence et diviser par $\displaystyle 5!$ , ce qui nous donne:

\displaystyle\binom{8}{5}=\frac{8!}{3!\cdot 5!}=56

En fait, ce que notre exemple illustre est que si nous voulons choisir $\displaystyle k$ billes, alors en résolvant le problème à l’aide des principes de bases, puis à l’aide des fonctions génératrices, on obtient alors l’égalité suivante:

\displaystyle\sum_{k=0}^{8}\binom{8}{k}x^{k}=(1+x)^{8}

Exemple 3.2.2.

De combien de façon peut on choisir 5 billes qui peuvent être choisi parmi des billes de couleur jaune, rouge et bleue? Dans ce cas, l’idée est similaire à l’exemple précédent, sauf que notre fonction génératrice pour chacune des billes doit tenir compte que l’on peut choisir soit $\displaystyle 0,1,2,3,4$ ou $\displaystyle 5$ billes d’une même couleur. Donc pour chacune des couleurs, la fonction génératrice sera $\displaystyle(1+x+x^{2}+x^{3}+x^{4}+x^{5})$ . Il nous faut ensuite multiplier cette fonction par elle même trois fois pour tenir compte des trois couleurs possible. La fonction génératrice d’écrivant le problème est donc:

\displaystyle(1+x+x^{2}+x^{3}+x^{4}+x^{5})^{3}

En utilisant Python, il nous est maintenant facile de le développer.

Listing 14: Développer le polynôme

⬇


                1
                
                
                
              from sympy import *


                2
                
                
                
              from pandas import *


                3
                
                
                
              init_printing()


                4
                
                
                
              


                5
                
                
                
              x = Symbol(’x’)


                6
                
                
                
              expand((1+x+x**2+x**3+x**4+x**5)**3)

Ce qui nous donne:

\displaystyle 1+3x+6x^{2}+10x^{3}+15x^{4}+21x^{5}+25x^{6}+27x^{7}+27x^{8}+25x^% {9}+21x^{10}+15x^{11}+10x^{12}+6x^{13}+3x^{14}+x^{15}

Comme nous voulons choisir $\displaystyle 5$ billes, c’est le coefficient de $\displaystyle x^{5}$ qui nous intéresse. La solution du problème est donc $\displaystyle 21$ . Il est aussi bien entendu possible de construire à l’aide de Python un tableau de valeur.

Listing 15: Creation d’un tableau de valeurs - Version 1

⬇


                1
                
                
                
              from sympy import *


                2
                
                
                
              from pandas import *


                3
                
                
                
              init_printing()


                4
                
                
                
              


                5
                
                
                
              x = Symbol(’x’)


                6
                
                
                
              polynome = Poly((1+x+x**2+x**3+x**4+x**5)**3).all_coeffs()


                7
                
                
                
              polynome.reverse()


                8
                
                
                
              tableau = DataFrame([polynome])


                9
                
                
                
              tableau.index = ["Valeurs"]


                10
                
                
                
              tableau

Ce qui nous donne:

$\displaystyle n$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Valeurs	1	3	6	10	15	21	25	27	27	25	21	15	10	6	3	1

Il faut cependant faire attention, car les valeurs pour $\displaystyle n>5$ sont potentiellement incorrectes. Ceci vient du fait que, dans notre fonction génératrice, nous avons considéré qu’il était possible de choisir un maximum de $\displaystyle 5$ billes de chaque couleur. Si on souhaite que notre tableau soit correcte pour toutes les valeurs de $\displaystyle n$ , on peut modifier notre fonction génératrice comme suit:

\displaystyle(1+x+x^{2}+x^{3}+x^{4}+...)^{3}=\left(\frac{1}{1-x}\right)^{3}=% \frac{1}{(1-x)^{3}}

Ce qui nous donne en utilisant Python:

Listing 16: Creation d’un tableau de valeurs - Version 2

⬇


                1
                
                
                
              from sympy import *


                2
                
                
                
              from pandas import *


                3
                
                
                
              init_printing()


                4
                
                
                
              


                5
                
                
                
              x = Symbol(’x’)


                6
                
                
                
              polynome = Poly(series(1/(1-x)**3, x, n=16).removeO()).all_coeffs()


                7
                
                
                
              polynome.reverse()


                8
                
                
                
              tableau = DataFrame([polynome])


                9
                
                
                
              tableau.index = ["Valeurs"]


                10
                
                
                
              tableau

$\displaystyle n$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Valeurs	1	3	6	10	15	21	28	36	45	55	66	78	91	105	120	136

Remarquez que, comme pour le problème précédent, ce n’est pas la seule approche possible. Nous aurions très bien pu considérer que le problème consiste à choisir $\displaystyle 5$ billes parmi $\displaystyle 3$ sans ordre et avec remise, ce qui nous donne:

\displaystyle\left\langle 3\atop 5\right\rangle=\frac{(3+5-1)!}{5!(3-1)!}=% \frac{7!}{5!\leavevmode\nobreak\ 2!}=21

En combinant ces deux approches, nous avons en fait montré que:

\displaystyle\sum_{k=0}^{\infty}\left\langle 3\atop k\right\rangle x^{k}=\frac% {1}{(1-x)^{3}}

Exemple 3.2.3.

De combien de façon peut on acheter 10 billes rouge si celle si sont vendu en paquet de 1, 2 et 3? Nous allons traiter séparément les paquets de $\displaystyle 1$ , $\displaystyle 2$ et $\displaystyle 3$ pour ce qui est de leur fonction génératrice. Dans le cas des paquets de $\displaystyle 1$ , nous avons une seule façon d’acheter $\displaystyle 1$ bille, $\displaystyle 2$ billes, $\displaystyle 3$ billes, etc. On a donc la fonction génératrice suivante:

\displaystyle(1+x+x^{2}+x^{3}+...+x^{9}+x^{10})=\sum_{i=0}^{10}x^{i}

Dans le cas des paquets de $\displaystyle 2$ , nous avons une seule possibilité d’en acheter $\displaystyle 0$ , et $\displaystyle 0$ façon d’en acheter $\displaystyle 1$ . Ensuite, nous avons à nouveau $\displaystyle 1$ façon d’en acheter $\displaystyle 2$ et $\displaystyle 0$ façon d’en acheter $\displaystyle 3$ , etc. La fonction génératrice est donc:

\displaystyle(1+0x+x^{2}+0x^{3}+x^{4}+0x^{5}+...+x^{10})=\sum_{i=0}^{5}x^{2i}

De la même manière, la fonction génératrice pour les paquets de $\displaystyle 3$ sera:

\displaystyle(1+x^{3}+x^{6}+x^{9})=\sum_{i=0}^{3}x^{3i}

La fonction génératrice décrivant le problème sera donc:

\displaystyle\left(\sum_{i=0}^{10}x^{i}\right)\left(\sum_{i=0}^{5}x^{2i}\right% )\left(\sum_{i=0}^{3}x^{3i}\right)

C’est le coefficient de $\displaystyle x^{10}$ qui nous intéresse. À l’aide de Python, on obtient facilement le résultat:

Listing 17: Acheter 10 billes - Version 1

⬇


                1
                
                
                
              from sympy import *


                2
                
                
                
              from pandas import *


                3
                
                
                
              init_printing()


                4
                
                
                
              


                5
                
                
                
              x = Symbol(’x’)


                6
                
                
                
              p1 = sum([x**i for i in range(0,11)])


                7
                
                
                
              p2 = sum([x**(2*i) for i in range(0,6)])


                8
                
                
                
              p3 = sum([x**(3*i) for i in range(0,4)])


                9
                
                
                
              expand(p1*p2*p3).coeff(x**10)

La réponse finale est donc $\displaystyle 14$ . Plus généralement, si on souhaite acheter $\displaystyle k$ boules (plutôt que $\displaystyle 10$ ), la fonction génératrice devient alors:

\displaystyle\left(\sum_{i=0}^{\infty}x^{i}\right)\left(\sum_{i=0}^{\infty}x^{% 2i}\right)\left(\sum_{i=0}^{\infty}x^{3i}\right)=\frac{1}{(1-x)(1-x^{2})(1-x^{% 3})}

Listing 18: Acheter 10 billes - Version 2

⬇


                1
                
                
                
              from sympy import *


                2
                
                
                
              from pandas import *


                3
                
                
                
              init_printing()


                4
                
                
                
              


                5
                
                
                
              x = Symbol(’x’)


                6
                
                
                
              FGO = 1 / ((1-x)*(1-x**2)*(1-x**3))


                7
                
                
                
              polynome = Poly(series(FGO, x, n=16).removeO()).all_coeffs()


                8
                
                
                
              polynome.reverse()


                9
                
                
                
              tableau = DataFrame([polynome])


                10
                
                
                
              tableau.index = ["Valeurs"]


                11
                
                
                
              tableau

$\displaystyle n$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Valeurs	1	1	2	3	4	5	7	8	10	12	14	16	19	21	24	27

Exemple 3.2.4.

De combien de façon peut on choisir 10 billes parmi des billes jaunes, rouges, bleues et vertes, si on veut au moins 2 billes jaunes, au plus 3 billes rouges, un nombre pair de billes bleues et entre 2 et 4 billes vertes ? Dans ce cas, en appliquant la même idée que précédemment, on obtient que la fonction génératrice décrivant le problème est:

\displaystyle\underbrace{\left(\sum_{i=2}^{10}x^{i}\right)}_{\textrm{jaune}}% \underbrace{\left(\sum_{i=0}^{3}x^{i}\right)}_{\textrm{rouge}}\underbrace{% \left(\sum_{i=0}^{5}x^{2i}\right)}_{\textrm{bleues}}\underbrace{\left(\sum_{i=% 2}^{4}x^{i}\right)}_{\textrm{vertes}}

La solution cherchée est celle correspondant au coefficient de $\displaystyle x^{10}$ .

Listing 19: Acheter 10 billes avec contrainte

⬇


                1
                
                
                
              from sympy import *


                2
                
                
                
              from pandas import *


                3
                
                
                
              init_printing()


                4
                
                
                
              


                5
                
                
                
              p1 = sum([x**i for i in range(2,11)])


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


                7
                
                
                
              p3 = sum([x**(2*i) for i in range(0,6)])


                8
                
                
                
              p4 = sum([x**i for i in range(2,5)])


                9
                
                
                
              


                10
                
                
                
              expand(p1*p2*p3*p4).coeff(x**10)

Dans notre cas, il y a donc $\displaystyle 30$ façons de choisir les billes.