4.7 Quelques problèmes supplémentaires

Dans cette section, nous voulons regarder quelques problèmes supplémentaires, qui en apparence se ressemble beaucoup. L’important ici est de porter une attention particulière aux différences entre chacun, et ce qui nous amène à utiliser une méthode ou une autre pour résoudre chacun de ces problèmes.

Exemple 4.7.1.

Un sac contient $\displaystyle 10$ billes, toutes de couleurs différentes. De combien de façon différente Mélanie, Julie et Anne peuvent-ils choisir chacun une bille ? Pour répondre à la question, au moins deux approches sont possible. Premièrement, nous pouvons utiliser le principe du produit, ce qui nous donne directement $\displaystyle 10\times 9\times 8=720$ possibilités. Nous pouvons aussi regarder le problème en terme d’objets que nous voulons choisir. Dans ce cas, il s’agit de choisir $\displaystyle 3$ objets parmi $\displaystyle 10$ avec ordre et sans remise, ce qui nous donne:

\displaystyle 10^{\underline{3}}=\frac{10!}{(10-3)!}=\frac{10!}{7!}=8\times 9% \times 10\leavevmode\nobreak\ \textrm{possibilit\'{e}s}

À noter que les deux méthodes sont bien entendu complètement équivalentes.

Exemple 4.7.2.

Un sac contient $\displaystyle 10$ billes, toutes de couleurs différentes. De combien de façon différente René peut-il choisir $\displaystyle 3$ billes ? L’idée est très semblable à l’exemple précédent, mais cette fois comme une seule personne doit choisir les billes, l’ordre n’est pas importante. On doit donc choisir $\displaystyle 3$ objets parmi $\displaystyle 10$ sans ordre et sans remise, ce qui nous donne:

\displaystyle\binom{10}{3}=\frac{10!}{3!(10-3)!}=\frac{10!}{3!\leavevmode% \nobreak\ 7!}=\frac{8\times 9\times 10}{1\times 2\times 3}=120\leavevmode% \nobreak\ \textrm{possibilit\'{e}s}

Exemple 4.7.3.

Un sac contient $\displaystyle 40$ billes. Parmi les $\displaystyle 40$ billes, $\displaystyle 10$ sont bleus, $\displaystyle 10$ sont jaunes, $\displaystyle 10$ sont vertes et $\displaystyle 10$ sont rouges. De combien de façon différente René peut-il choisir $\displaystyle 3$ billes ? Dans ce cas, comme nous avons plus de billes de chaque couleur que de billes que nous souhaitons choisir, le problème se fait avec remise. On doit donc choisir $\displaystyle 3$ objets parmi $\displaystyle 4$ sans ordre et avec remise. On a donc:

\displaystyle\left\langle 4\atop 3\right\rangle=\frac{(4+3-1)!}{3!(4-1)!}=% \frac{6!}{3!\leavevmode\nobreak\ 3!}=\frac{4\times 5\times 6}{1\times 2\times 3% }=20\leavevmode\nobreak\ \textrm{possibilit\'{e}s}

Exemple 4.7.4.

Un sac contient $\displaystyle 40$ billes. Parmi les $\displaystyle 40$ billes, $\displaystyle 10$ sont bleus, $\displaystyle 10$ sont jaunes, $\displaystyle 10$ sont vertes et $\displaystyle 10$ sont rouges. De combien de façon différente Loïk, Isabelle et Élise peuvent-ils choisir chacun une bille ? Dans ce cas, le problème revient à choisir $\displaystyle 3$ objets parmi $\displaystyle 4$ avec ordre et avec remise. On a donc $\displaystyle 4^{3}=64$ possibilités.

Exemple 4.7.5.

Un sac contient $\displaystyle 10$ billes, toutes de couleurs différentes. De combien de façon différente Michel, René et Marie peuvent-ils choisir chacun $\displaystyle 2$ billes ? Dans ce cas, nous allons utiliser le principe du produit. Michel doit choisir $\displaystyle 2$ billes parmi $\displaystyle 10$ choix sans ordre et sans remise ET René doit choisir $\displaystyle 2$ billes parmi $\displaystyle 8$ choix sans ordre et sans remise ET Marie doit choisir $\displaystyle 2$ billes parmi $\displaystyle 8$ choix sans ordre et sans remise. On obtient donc:

\displaystyle\binom{10}{2}\binom{8}{2}\binom{6}{2}=\frac{10!}{2!\leavevmode% \nobreak\ 8!}\cdot\frac{8!}{2!\leavevmode\nobreak\ 6!}\cdot\frac{6!}{2!% \leavevmode\nobreak\ 4!}=\frac{10!}{2!\leavevmode\nobreak\ 2!\leavevmode% \nobreak\ 2!\leavevmode\nobreak\ 4!}=18900\leavevmode\nobreak\ \textrm{% possibilit\'{e}s}

Exemple 4.7.6.

Un sac contient $\displaystyle 32$ billes. Parmi les $\displaystyle 32$ billes, $\displaystyle 10$ sont bleus, $\displaystyle 10$ sont jaunes, $\displaystyle 10$ sont vertes et $\displaystyle 2$ sont rouges. De combien de façon différente Sarah peut-elle choisir $\displaystyle 3$ billes ? Dans ce cas, le problème revient essentiellement à choisir $\displaystyle 3$ objets parmi $\displaystyle 4$ , sans ordre et avec remise. On a donc:

\displaystyle\left\langle 4\atop 3\right\rangle=\frac{(4+3-1)!}{3!(4-1)!}=% \frac{6!}{3!\leavevmode\nobreak\ 3!}=\frac{4\times 5\times 6}{1\times 2\times 3% }=20\leavevmode\nobreak\ \textrm{possibilit\'{e}s}

Par contre, il est impossible d’avoir $\displaystyle 3$ billes rouges, car il n’y en a pas suffisamment. Il faut donc retiré une possibilité de la réponse. On a donc $\displaystyle 20-1=19$ possibilités. À noter qu’ici une deuxième approche peut s’avérer intéressante et serait particulièrement intéressante dans le cas où nous aurions plus de contrainte. Il s’agit d’utiliser les fonctions génératrices. On peut en effet choisir $\displaystyle 0,1,2$ ou $\displaystyle 3$ billes bleus, ce que l’on peut dénoter à l’aide de la fonction génératrice $\displaystyle(1+x+x^{2}+x^{3})$ . Il en est de même pour les billes jaunes et les billes vertes. Pour ce qui est des billes rouges, nous pouvons choisir $\displaystyle 0,1$ ou $\displaystyle 2$ billes rouges seulement, ce qui nous donne la fonction génératrice $\displaystyle(1+x+x^{2})$ . En multipliant le tout, on obtient donc:

\displaystyle(1+x+x^{2}+x^{3})^{3}(1+x+x^{2})=x^{11}+4x^{10}+10x^{9}+19x^{8}+2% 8x^{7}+34x^{6}+34x^{5}+28x^{4}+19x^{3}+10x^{2}+4x+1

Notre réponse sera donc le coefficient de $\displaystyle x^{3}$ , ce qui correspond au nombre de façon de choisir $\displaystyle 3$ billes. On obtient donc à nouveau $\displaystyle 19$ .

Exemple 4.7.7.

Un sac contient $\displaystyle 25$ billes. Parmi les $\displaystyle 25$ billes, $\displaystyle 3$ sont bleus, $\displaystyle 5$ sont jaunes, $\displaystyle 7$ sont vertes, $\displaystyle 10$ sont rouges. De combien de façons différentes peut-on distribuer les billes parmi $\displaystyle 25$ enfants si chaque enfant reçoit exactement une bille ? Dans ce cas, deux idées sont possibles. Dans un premier temps nous allons utiliser le principe du produit:

$\displaystyle\bullet$ Distribuer les billes bleus sans ordre et sans remise (3 parmi 25)

$\displaystyle\bullet$ Distribuer les billes jaunes sans ordre et sans remise (5 parmi 22)

$\displaystyle\bullet$ Distribuer les billes vertes sans ordre et sans remise (7 parmi 17)

$\displaystyle\bullet$ Distribuer les billes rouges sans ordre et sans remise (10 parmi 10)

Ce qui nous permet d’obtenir:

\displaystyle\binom{25}{3}\binom{22}{5}\binom{17}{7}\binom{10}{10}=\frac{25!}{% 3!\leavevmode\nobreak\ 5!\leavevmode\nobreak\ 7!\leavevmode\nobreak\ 10!}=1% \leavevmode\nobreak\ 177\leavevmode\nobreak\ 930\leavevmode\nobreak\ 353% \leavevmode\nobreak\ 600\leavevmode\nobreak\ \textrm{possibilit\'{e}s}

Nous pouvons aussi de manière complètement équivalente interpréter le problème comme le problème du MISSISSIPPI, ce qui nous donne la réponse un peu plus rapidement.

Exemple 4.7.8.

Un sac contient $\displaystyle 40$ billes. Parmi les $\displaystyle 40$ billes, $\displaystyle 10$ sont bleus, $\displaystyle 10$ sont jaunes, $\displaystyle 10$ sont vertes, et $\displaystyle 10$ sont rouges. De combien de façon différente John peut-il choisir $\displaystyle 3$ billes si parmi les $\displaystyle 3$ billes au moins une est verte ? De ce cas, nous allons procéder en calculant le complément, ce qui nous simplifiera grandement le travail. Nous allons donc compter le nombre total de possibilité, puis soustraire celle qui n’ont aucune bille verte. On a donc:

\displaystyle\left\langle 4\atop 3\right\rangle-\left\langle 3\atop 3\right% \rangle=\frac{(4+3-1)!}{3!(4-1)!}-\frac{(3+3-1)!}{3!(3-1)!}=\frac{6!}{3!% \leavevmode\nobreak\ 3!}-\frac{5!}{3!\leavevmode\nobreak\ 2!}=20-10=10% \leavevmode\nobreak\ \textrm{possibilit\'{e}s}

Ici, la méthode des fonctions génératrices peut à nouveau s’avérer intéressante. En effet, la fonction génératrice correspondante aux billes bleus, aux billes jaunes et aux billes vertes est dans chacun des cas $\displaystyle(1+x+x^{2})$ . À noter que nous n’avons pas mis le terme $\displaystyle x^{3}$ , car il est impossible de choisir $\displaystyle 3$ billes de l’une de ces couleurs. Par contre, celle correspondante aux billes vertes sera $\displaystyle(x+x^{2}+x^{3})$ , car nous devons en choisir au moins une. En multipliant le tout nous obtenons donc:

\displaystyle(1+x+x^{2})^{3}(x+x^{2}+x^{3})=x^{9}+4x^{8}+10x^{7}+16x^{6}+19x^{% 5}+16x^{4}+10x^{3}+4x^{2}+x

La réponse chercher sera donc le coefficient de $\displaystyle x^{3}$ , qui est bien entendu $\displaystyle 10$ comme nous l’avions déjà trouvé.

Exemple 4.7.9.

Un sac contient $\displaystyle 20$ billes. Parmi les $\displaystyle 20$ billes, $\displaystyle 8$ sont bleues, $\displaystyle 5$ sont jaunes, $\displaystyle 5$ sont vertes et $\displaystyle 2$ sont rouges. De combien de façon peut-on donner une bille à chacun des $\displaystyle 10$ enfants de la classe de maternelle de Mme Untel ? Ici le problème est similaire à celui du MISSISSIPPI dans le cas où nous voulions former un mot contenant seulement certaine des lettres. Nous allons donc utiliser l’approche des fonctions génératrices exponentielles. On a donc:

\begin{split}\left(\sum_{n=0}^{8}\frac{x^{n}}{n!}\right)\left(\sum_{n=0}^{5}% \frac{x^{n}}{n!}\right)\left(\sum_{n=0}^{5}\frac{x^{n}}{n!}\right)\left(\sum_{% n=0}^{2}\frac{x^{n}}{n!}\right)=1+4\frac{x^{1}}{1!}+16\frac{x^{2}}{2!}+63\frac% {x^{3}}{3!}+243\frac{x^{4}}{4!}+918\frac{x^{5}}{5!}+3400\frac{x^{6}}{6!}+12349% \frac{x^{7}}{7!}\\ +43915\frac{x^{8}}{8!}+152391\frac{x^{9}}{9!}+513741\frac{x^{10}}{10!}+1674156% \frac{x^{11}}{11!}+5244294\frac{x^{12}}{12!}+15689388\frac{x^{13}}{13!}+445104% 66\frac{x^{14}}{14!}\\ +118774656\frac{x^{15}}{15!}+294666372\frac{x^{16}}{16!}+665909244\frac{x^{17}% }{17!}+1317728412\frac{x^{18}}{18!}+2095133040\frac{x^{19}}{19!}\\ +2095133040\frac{x^{20}}{20!}\end{split}

La solution du problème est le coefficient de $\displaystyle\nicefrac{{x^{10}}}{{10!}}$ . On a donc qu’il y a $\displaystyle 513\leavevmode\nobreak\ 741$ façons de distribuer les billes.

Exemple 4.7.10.

Un sac contient $\displaystyle 20$ billes. Parmi les $\displaystyle 20$ billes, $\displaystyle 8$ sont bleues, $\displaystyle 5$ sont jaunes, $\displaystyle 5$ sont vertes et $\displaystyle 2$ sont rouges. De combien de façon Sophie peut-elle choisir $\displaystyle 10$ billes? On remarque immédiatement que le problème est très similaire au précédent, mais cette fois l’ordre n’est pas importante. Nous allons donc prendre la même approche que pour l’exemple précédent, mais en utilisant les fonctions génératrices ordinaires plutôt que les fonctions génératrices exponentielles.

\begin{split}\left(\sum_{n=0}^{8}x^{n}\right)\left(\sum_{n=0}^{5}x^{n}\right)% \left(\sum_{n=0}^{5}x^{n}\right)\left(\sum_{n=0}^{2}x^{n}\right)=1+4x+10x^{2}+% 19x^{3}+31x^{4}+46x^{5}+62x^{6}+77x^{7}+89x^{8}+97x^{9}\\ +100x^{10}+97x^{11}+89x^{12}+77x^{13}+62x^{14}+46x^{15}+31x^{16}+19x^{17}+10x^% {18}+4x^{19}+x^{20}\end{split}

La solution est le coefficient de $\displaystyle x^{10}$ . Sophie a donc $\displaystyle 100$ possibilités pour choisir $\displaystyle 10$ billes.

Exemple 4.7.11.

$\displaystyle 10$ enfants sont placés sous forme d’un rang. De combien de façons différentes peut-on leur remettre à chacun une bille qui peuvent être bleue, verte, orange ou jaune de sorte qu’un enfant recevant une bille bleue ne soit jamais à côté d’un enfant recevant une bille orange ou jaune ? Pour ce faire, nous allons commencer par modéliser le problème à l’aide d’un automate.

Si on dénote par $\displaystyle x_{n}$ le nombre de solution possible avec $\displaystyle n$ enfants (les solutions valides), et on dénote par:

$\displaystyle a_{n}=$	Nombre de solutions valides se terminant par une boule bleue
$\displaystyle b_{n}=$	Nombre de solutions valides se terminant par une boule verte
$\displaystyle c_{n}=$	Nombre de solutions valides se terminant par une boule orange
$\displaystyle d_{n}=$	Nombre de solutions valides se terminant par une boule jaune

alors à partir de l’automate on obtient le système d’équations définies par récurrence suivant:

\displaystyle\left\{\begin{array}[]{l}a_{n}=a_{n-1}+b_{n-1}\\ b_{n}=a_{n-1}+b_{n-1}+c_{n-1}+d_{n-1}\\ c_{n}=b_{n-1}+c_{n-1}+d_{n-1}\\ d_{n}=b_{n-1}+c_{n-1}+d_{n-1}\\ \end{array}\right.,\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall n\geq 2

avec les valeurs initiales $\displaystyle a_{1}=b_{1}=c_{1}=d_{1}=1$ . À l’aide de Python, ou même à la main, il devient alors relativement facile de construire une table de valeurs.

Listing 25: Solution du problème

⬇


                1
                
                
                
              from sympy import *


                2
                
                
                
              from pandas import *


                3
                
                
                
              init_printing()


                4
                
                
                
              


                5
                
                
                
              def a(n):


                6
                
                
                
                  if n == 1:


                7
                
                
                
                      return 1


                8
                
                
                
                  else:


                9
                
                
                
                      return a(n-1) + b(n-1)


                10
                
                
                
              


                11
                
                
                
              def b(n):


                12
                
                
                
                  if n == 1:


                13
                
                
                
                      return 1


                14
                
                
                
                  else:


                15
                
                
                
                      return a(n-1) + b(n-1) + c(n-1) + d(n-1)


                16
                
                
                
              


                17
                
                
                
              def c(n):


                18
                
                
                
                  if n == 1:


                19
                
                
                
                      return 1


                20
                
                
                
                  else:


                21
                
                
                
                      return b(n-1) + c(n-1) + d(n-1)


                22
                
                
                
              


                23
                
                
                
              def d(n):


                24
                
                
                
                  if n == 1:


                25
                
                
                
                      return 1


                26
                
                
                
                  else:


                27
                
                
                
                      return b(n-1) + c(n-1) + d(n-1)


                28
                
                
                
              


                29
                
                
                
              def x(n):


                30
                
                
                
                  return a(n) + b(n) + c(n) + d(n)


                31
                
                
                
              


                32
                
                
                
              tableau = DataFrame({


                33
                
                
                
                  "a(n)": [a(n) for n in range(1,11)],


                34
                
                
                
                  "b(n)": [b(n) for n in range(1,11)],


                35
                
                
                
                  "c(n)": [c(n) for n in range(1,11)],


                36
                
                
                
                  "d(n)": [d(n) for n in range(1,11)],


                37
                
                
                
                  "x(n)": [x(n) for n in range(1,11)]


                38
                
                
                
              })


                39
                
                
                
              tableau.index = [n for n in range(1,11)]


                40
                
                
                
              tableau

$\displaystyle n$	$\displaystyle a_{n}$	$\displaystyle b_{n}$	$\displaystyle c_{n}$	$\displaystyle d_{n}$	$\displaystyle x_{n}$
1	1	1	1	1	4
2	2	4	3	3	12
3	6	12	10	10	38
4	18	38	32	32	120
5	56	120	102	102	380
6	176	380	324	324	1204
7	556	1204	1028	1028	3816
8	1760	3816	3260	3260	12096
9	5576	12096	10336	10336	38344
10	17672	38344	32768	32768	121552

La solution de notre problème est donc $\displaystyle 121\leavevmode\nobreak\ 552$ possibilités. Pour résoudre le problème, nous aurions aussi pu réécrire notre système d’équations définie par récurrence sous forme matricielle, et appliquer les méthodes de l’algèbre linéaire pour le résoudre. Dans ce cas, nous aurions obtenu l’équation:

\displaystyle\begin{pmatrix}a_{n}\\ b_{n}\\ c_{n}\\ d_{n}\end{pmatrix}=\underbrace{\begin{pmatrix}1&1&0&0\\ 1&1&1&1\\ 0&1&1&1\\ 0&1&1&1\end{pmatrix}}_{=A}\begin{pmatrix}a_{n-1}\\ b_{n-1}\\ c_{n-1}\\ d_{n-1}\end{pmatrix}=\begin{pmatrix}1&1&0&0\\ 1&1&1&1\\ 0&1&1&1\\ 0&1&1&1\end{pmatrix}^{2}\begin{pmatrix}a_{n-2}\\ b_{n-2}\\ c_{n-2}\\ d_{n-2}\end{pmatrix}=...=\begin{pmatrix}1&1&0&0\\ 1&1&1&1\\ 0&1&1&1\\ 0&1&1&1\end{pmatrix}^{n-1}\begin{pmatrix}1\\ 1\\ 1\\ 1\end{pmatrix}=\begin{pmatrix}17672\\ 38344\\ 32768\\ 32768\end{pmatrix}

La solution de notre problème étant la somme des éléments du vecteur de droite, ce qui nous donne bien entendu la même valeur que nous avions trouvé précédemment.

Il aurait aussi été possible de trouver une seule récurrence utilisant uniquement la suite $\displaystyle x_{n}$ . Bien que cette dernière soit sans doute plus intéressante, en particulier lorsqu’il s’agit de faire les calculs à la main, la trouver dans le cas présent n’est pas trivial sans avoir recours au technique de l’algèbre linéaire. La méthode la plus simple consiste à trouver le polynôme caractéristique de la matrice $\displaystyle A$ :

\displaystyle det(A-\lambda I)=\begin{vmatrix}1-\lambda&1&0&0\\ 1&1-\lambda&1&1\\ 0&1&1-\lambda&1\\ 0&1&1&1-\lambda\end{vmatrix}=\lambda^{4}-4\lambda^{3}+2\lambda^{2}+2\lambda=0

En remplaçant les $\displaystyle\lambda^{4}$ par $\displaystyle x_{n}$ , les $\displaystyle\lambda^{3}$ par $\displaystyle x_{n-1}$ , les $\displaystyle\lambda^{2}$ par $\displaystyle x_{n-2}$ et les $\displaystyle\lambda$ par $\displaystyle x_{n-3}$ , on obtient la récurrence suivante:

\displaystyle\left\{\begin{array}[]{l}x_{n}=4x_{n-1}-2x_{n-2}-2x_{n-3},% \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall n\geq 3% \\ x_{0}=1\\ x_{1}=4\\ x_{2}=12\end{array}\right.

où les valeurs initiales ont été trouvé indépendamment par simple énumération. Notez finalement que bien que la méthode que nous avons utilisé ci-dessus soit particulièrement complexe, vérifier que la récurrence est correcte est pour sa part un problème facile.