4.7 Quelques problèmes supplémentaires

Une usine produit des crayons de $\displaystyle 10$ couleurs différentes. Chacune de ces couleurs sont disponible en très grande quantité. De combien de façon un client peut-il choisir $\displaystyle 7$ crayons de sorte qu’au moins deux d’entre eux soient de la même couleur ? On remarque ici qu’il est plus facile de compter le complément plutôt que de répondre directement à la question. il est facile de voir que le problème se fait sans ordre. Nous allons donc commencer par compter le nombre de façon de choisir $\displaystyle 7$ couleurs parmi $\displaystyle 10$ avec remise, et soustraire le nombre de façon de choisir $\displaystyle 7$ couleurs parmi $\displaystyle 10$ sans remise. On a donc:

Il y a donc $\displaystyle 11\leavevmode\nobreak\ 320$ façon différente de choisir $\displaystyle 7$ crayons de sorte qu’au moins deux d’entre eux soient de la même couleur.

Une usine produit des crayons de $\displaystyle 10$ couleurs différentes incluant des crayons bleus. Chacune de ces couleurs sont disponibles en très grande quantité. De combien de façons un client peut-il choisir $\displaystyle 7$ crayons de sorte qu’au moins deux d’entre eux soient bleus ?  
 
Première méthode: On peut travailler avec le complément et compter toutes les possibilités sans tenir compte de la contrainte sur le nombre de crayon bleu, puis on enlève les cas où nous avons aucun ou un seul bleu. On a donc:

Il y a donc $\displaystyle 2\leavevmode\nobreak\ 002$ façons de choisir les crayons de sorte qu’au moins deux soient bleus.  
 
Deuxième méthode: On peut aussi résoudre le problème à l’aide d’une fonction génératrice ordinaire. Dans ce cas, nous avons la fonction génératrice suivante:

La réponse est alors obtenu en cherchant le coefficient de $\displaystyle x^{7}$. Le code Python ci-dessous nous permet de retrouver facilement la réponse.

Il est intéressant de remarquer que Python n’est pas vraiment nécessaire pour trouver la solution du problème. En effet, la fonction génératrice que nous avons obtenu peut facilement être réécrite sous forme d’un somme pour en extraire les coefficients. On a donc:

La solution du problème, c’est à dire le coefficient de $\displaystyle x^{7}$ est donc $\displaystyle\left\langle 10\atop 5\right\rangle$.  
 
Troisième méthode: La solution que nous avons obtenu à partir des fonctions génératrices est tellement simple qu’il devrait être possible d’en trouver une interprétation combinatoire simple. En effet, comme le client souhaite avoir au moins deux crayons bleus et que l’ordre n’est pas importante, le client peut tout simplement commencer par prendre les deux crayons bleus (1 option), puis choisir les cinq autres crayons parmi les $\displaystyle 10$ options possibles sans ordre et avec remise, ce qui nous donne immédiatement:

Combien de mots de $\displaystyle 8$ lettres ne contiennent pas la combinaison $\displaystyle AB$ ?  
 
Première méthode: Pour répondre à la question, commençons par considérez tout les mots de $\displaystyle 8$ lettres. Ceci est facile à calculer, il s’agit de $\displaystyle 26^{8}$. Maintenant, nous allons soustraire tout les mots qui contiennent la séquence $\displaystyle AB$. Pour ce faire, on doit premièrement choisir les $\displaystyle 6$ lettres manquantes, ce qui peut être fait de $\displaystyle 26^{6}$ façon, puis pour chacune des lettres choisir si elles vont avant ou après le $\displaystyle AB$, ce qui peut peut être fait de $\displaystyle\left\langle 2\atop 6\right\rangle$ façons. On remarque maintenant que les mots contenant deux fois la suite $\displaystyle AB$ ont été soustrait deux fois, il nous faut donc les ajouter à nouveau. En suivant la même idée, on choisit les $\displaystyle 4$ lettres manquantes, ce qui peut être fait de $\displaystyle 26^{4}$ façons, puis on choisit à quel endroit les placer, soit avant, entre ou après les deux $\displaystyle AB$, ce qui peut être fait de $\displaystyle\left\langle 3\atop 4\right\rangle$ façons. En continuant de la même façon, on obtient finalement:

Deuxième méthode: On peut aussi résoudre le problème à l’aide d’une récurrence. Dénotons par $\displaystyle a_{n}$ le nombre de mots de $\displaystyle n$ lettre qui ne contiennent pas la suite $\displaystyle AB$. On remarque premièrement que pour tout les mots de longueur $\displaystyle n-1$, on peut toujours ajouter une lettre quelconque, sauf dans le cas ou le mot se terminerais par $\displaystyle AB$. On a donc la récurrence suivante:

Troisième méthode: On peut aussi résoudre le problème à l’aide d’un automate. Dans ce cas, on définit trois états: $\displaystyle A,B$ et $\displaystyle X$. L’état $\displaystyle A$ représentant les mots se terminant par $\displaystyle A$, l’état $\displaystyle B$ ceux se terminant par $\displaystyle B$, puis l’état $\displaystyle X$ pour les mots se terminant par n’importe quelle autre lettre.

Cet automate nous permet alors d’obtenir le système de récurrence suivant:

avec les valeurs initiales $\displaystyle a_{1}=b_{1}=1$ et $\displaystyle x_{1}=24$. Le code Python suivant peut alors nous permettre d’obtenir facilement la solution.

Quatrième méthode: Une autre approche pour travailler avec un automate consiste à travailler avec le complément. Dans ce cas, nous allons commencer par compter le nombre de mots qui contiennent $\displaystyle AB$.

À partir de cet automate, on obtient le système de récurrence suivant:

avec les valeurs initiales $\displaystyle a_{0}=1$ et $\displaystyle b_{0}=c_{0}=0$. La solution du problème est donc:

Combien de mots de $\displaystyle 8$ lettres ne contiennent pas la combinaison $\displaystyle AA$ ? Dans ce cas, bien que le problème puisse à première vu sembler très semblable à l’exemple ci-dessus, la solution reste très différente. Le fait que les deux lettres soient identiques veut dire qu’il est possible que la suite AA apparaisse deux fois dans le même mot de manière disjointe, par exemple $\displaystyle AABCAADE$ ou sous la forme d’une suite $\displaystyle AAA$.
 
Première méthode: On peut premièrement utiliser une seule récurrence. Dans ce cas nous avons:

La solution du problème étant donné par la valeur de $\displaystyle a_{8}$. Le code Python suivant peut nous permettre d’obtenir facilement la réponse.

On obtient donc la solution $\displaystyle a_{8}=206\leavevmode\nobreak\ 740\leavevmode\nobreak\ 234\leavevmode\nobreak\ 375$.

Deuxième méthode: On peut aussi résoudre le problème à l’aide d’un automate. Dans ce cas, on définit trois états: $\displaystyle A,B$ et $\displaystyle X$. L’état $\displaystyle A$ représentant les mots se terminant par $\displaystyle A$, l’état $\displaystyle B$ ceux se terminant par $\displaystyle B$, puis l’état $\displaystyle X$ pour les mots se terminant par n’importe quelle autre lettre.

Cet automate nous permet alors d’obtenir le système de récurrence suivant:

avec les valeurs initiales $\displaystyle a_{1}=b_{1}=1$ et $\displaystyle x_{1}=24$. Le code Python suivant peut alors nous permettre d’obtenir facilement la solution.

Troisième méthode: Une autre approche pour travailler avec un automate consiste à travailler avec le complément. Dans ce cas, nous allons commencer par compter le nombre de mots qui contiennent $\displaystyle AA$.

À partir de cet automate, on obtient le système de récurrence suivant:

avec les valeurs initiales $\displaystyle a_{0}=1$ et $\displaystyle b_{0}=c_{0}=0$. La solution du problème est donc:

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:

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

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:

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:

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.

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:

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:

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:

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$.

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)

ET

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

ET

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

ET

$\displaystyle\bullet$ Distribuer les billes rouges sans ordre et sans remise (10 parmi 10)
 
Ce qui nous permet d’obtenir:

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.

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:

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:

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é.

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:

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.

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.

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

$\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:

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

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.

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:

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$:

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:

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.