À faire en classe
Ces exercices sont faits pour travailler en classe. Ils servent à approfondir les notions de la section et à atteindre les objectifs d’apprentissage plus avancés.
1.
On considère \(C(n)\) le nombre de chaînes binaires de longueur \(n\) possédant un nombre pair de \(0.\) Trouver une relation de récurrence pour \(C(n)\) ainsi que la condition initiale, c’est-à-dire déterminer la valeur de \(C(1)\text{.}\)
Réponse.
Solution.
Les chaîne binaires de longueur un sont soit \(1\) ou \(0\text{.}\) Ainsi, la chaîne \(1\) est la seule contenant un nombre pair de \(0\text{,}\) d’où \(C(1)=1\text{.}\)
Par la suite, on considère une chaîne binaire de longueur \(n\text{,}\) qu’on note \(d_1d_2\dots d_{n-1}d_n\text{,}\) avec \(d_i\in \{0,1\}\text{.}\) Pour déterminer \(C(n)\) on utilise le principe de la somme sur la valeur de \(d_n\text{.}\) Il ya deux cas possible, soit \(d_n=1\text{,}\) ou bien \(d_n=0\text{.}\)
Si \(d_n=1\text{,}\) puisque la chaîne \(d_1d_2\dots d_{n-1}1\) possède un nombre pair de \(0\text{,}\) il doit y avoir un nombre pair de \(0\) dans la chaîne \(d_1d_2\dots d_{n-1}\text{.}\) Il en en a donc \(C(n-1)\text{.}\)
Si \(d_n=0\text{,}\) puisque la chaîne \(d_1d_2\dots d_{n-1}0\) possède un nombre pair de \(0\text{,}\) il doit y avoir un nombre impair de \(0\) dans la chaîne \(d_1d_2\dots d_{n-1}\text{.}\) Par l’exercice 5.4.17, on sait qu’il a aussi \(C(n-1)\) suite de ce type.
Par le principe de la somme, on a que \(C(n)=C(n-1)+C(n-1)=2C(n-1)\text{.}\)
2.
On considère \(D(n)\) le nombre de chaînes de chiffres (en base dix) de longueur \(n\) possédant un nombre pair de \(0.\) Trouver une relation de récurrence pour \(D(n)\) ainsi que la condition initiale, c’est-à-dire déterminer la valeur de \(D(1)\text{.}\)
Réponse.
Solution.
Les chaîne de chiffres en base dix de longueur un sont \(0, 1, 2, 3, 4, 5, 6, 7, 8\) ou \(9\text{.}\) Ainsi, il y en a \(9\) contenant un nombre pair de \(0\text{,}\) d’où \(D(1)=9\text{.}\)
Par la suite, on considère une chaîne chiffres en base dix de longueur \(n\text{,}\) qu’on note \(d_1d_2\dots d_{n-1}d_n\text{,}\) avec \(d_i\in \{0,1,\dots,9\}\text{.}\) Pour déterminer \(D(n)\) on utilise le principe de la somme sur la valeur de \(d_n\text{.}\) Il ya deux cas possible, soit \(d_n\neq 0\text{,}\) ou bien \(d_n=0\text{.}\)
Si \(d_n\neq 0\) il y a \(9\) choix pour \(d_n\) et puisque la chaîne \(d_1d_2\dots d_{n-1}\ast\) possède un nombre pair de \(0\text{,}\) il doit y avoir un nombre pair de \(0\) dans la chaîne \(d_1d_2\dots d_{n-1}\text{.}\) Il y a donc \(9\cdot D(n-1)\) chaînes de chiffres de longueur \(n\) ayant un nombre pair de \(0\) avec \(d_n \neq 0\text{.}\)
Si \(d_n=0\text{,}\) puisque la chaîne \(d_1d_2\dots d_{n-1}0\) possède un nombre pair de \(0\text{,}\) il doit y avoir un nombre impair de \(0\) dans la chaîne \(d_1d_2\dots d_{n-1}\text{.}\) On veut donc compter le nombre de chaînes de chiffre de longueur \(n-1\) ayant un nombre impair de \(0\) à l’aide de \(D(n-1)\text{.}\) Puisqu’il y a \(10^{n-1}\) chaînes de chiffres de longueur \(n-1\text{,}\) il y en aura \(10^{n-1}-D(n-1)\) avec un nombre impair de \(0\text{.}\)
Par le principe de la somme, on a que \(D(n)=9\cdot D(n-1)+(10^{n-1}-D(n-1))=8C(n-1)+10^{n-1}\text{.}\)
3.
On pose \(P_k\) le nombre de permutations d’un ensemble fini à \(k\) éléments. On sait déjà que \(P_k=k!.\) On veut retrouver cette formule à l’aide d’une relation de récurrence.
(a)
Trouver une relation de récurrence pour \(P_k\)Réponse.
\(P_k = k P_{k-1}\)
(b)
Déterminer \(P_1\)Réponse.
\(P_1=1\)
(c)
Utiliser la relation de récurrence et la condition initiale trouvée dans les étapes précédentes pour vérifier que \(P_k=k!\)Solution.
En utilisant la relation de récurrence à plusieurs reprises (à \(k-1\) reprise pour être exacte), on a
\begin{align*}
P_k\amp=kP_{k-1} \\
P_k\amp=k({k-1})P_{k-2} \\
P_k\amp=k({k-1})(k-2)P_{k-3} \\
\amp\vdots \\
P_k\amp=k({k-1})(k-2)(k-3)\cdots (2)P_{1} \\
P_k\amp=k({k-1})(k-2)(k-3)\cdots (2)(1)=k!
\end{align*}
4.
Une machine distributrice accepte uniquement des pièces de \(1\$,\) des pièces de \(2\$\) et des billets de \(5\$\)
Posons \(p_n\) le nombre de façons de donner \(n\) dollars à cette machine si l’ordre dans laquelle on donne l’argent est importante.
(a)
Trouver une relation de récurrence pour \(p_n\text{.}\)
Réponse.
\(p_{n}=p_{n-1}+p_{n-2}+p_{n-5}\)
Solution.
On cherche une relation de récurrence pour \(n\geq 5.\) Pour déterminer \(p_n,\) on utilise le principe de la somme selon la dernière pièce ou le dernier billet utilisé afin de donner les \(n\) dollars.
Ainsi, avant de donner la dernière pièce/le dernier billet, on avait donné \(n-1,\, n-2\) ou bien \(n-5\) dollar.
Par le principe de la somme, on a \(p_n=p_{n-1} + p_{n-2}+p_{n-5}\text{.}\)
(b)
Trouver les conditions initiales pour ce problème, c’est-à-dire déterminer \(p_1, p_2, p_3, p_4\) et \(p_5\text{.}\)Indice 1.
Indice 2.
Indice 3.
Réponse.
\begin{align*}
p_1\amp=1\\
p_2\amp=2\\
p_3\amp=3\\
p_4\amp=5\\
p_5\amp=9
\end{align*}
(c)
Déterminer \(p_{10}\text{.}\)5.
On note \(a_n\) le nombre de chaînes binaires de longueur \(n\) qui contiennent trois \(0\) consécutifs.
(a)
Trouver une relation de récurrence pour \(a_n\) avec \(n\geq 4\text{.}\)Réponse.
\(a_n = a_{n-1} + a_{n-2}+a_{n-3}+2^{n-3} \)
Solution.
Soit \(d_1\dots d_{n-3}d_{n-2}d_{n-1}d_n\) une chaîne binaire de longueur \(n\) qui contient trois \(0\) consécutifs. On sépare en plusieurs cas selon les valeurs des derniers caractères. En particulier, on sépare selon l’endroit où se trouve le dernier \(1\) dans la chaîne \(d_1\dots d_{n-3}d_{n-2}d_{n-1}d_n\text{.}\) Il y aura quatre cas différents.
Si le dernier \(1\) est à la dernière position, c’est-à-dire si \(d_n=1\text{,}\) alors les trois \(0\) consécutifs se trouvent dans la chaîne \(d_1\dots d_{n-3}d_{n-2}d_{n-1}\text{.}\) Il y a donc \(a_{n-1}\) possibilités.
Si le dernier \(1\) est à l’avant dernière position, c’est-à-dire si \(d_{n-1}d_n=10\text{,}\) alors les trois \(0\) consécutifs se trouvent dans la chaîne \(d_1\dots d_{n-3}d_{n-2}\text{.}\) Il y a donc \(a_{n-2}\) possibilités.
Si le dernier \(1\) est à la troisième position en partant de la fin, c’est-à-dire si \(d_{n-2}d_{n-1}d_n=100\text{,}\) alors les trois \(0\) consécutifs se trouvent dans la chaîne \(d_1\dots d_{n-3}\text{.}\) Il y a donc \(a_{n-3}\) possibilités.
Finalement, si le dernier \(1\) est avant \(d_{n-2}\text{,}\) c’est-à-dire si \(d_{n-2}d_{n-1}d_n=000\text{,}\) alors il y a déjà trois \(0\) consécutifs dans la chaîne \(d_1\dots d_{n-3}d_{n-2}d_{n-1}d_n=d_1\dots d_{n-3}000\text{.}\) Il n’y a donc aucune restriction sur la chaîne \(d_1\dots d_{n-3}\text{,}\) c’est-à-dire qu’il y a \(2^{n-3}\) possibilités.
Par le principe de la somme, on a \(a_n=a_{n-1} + a_{n-2}+a_{n-3}+2^{n-3}\text{.}\)
(b)
Trouver les conditions initiales, c’est-à-dire déterminer \(a_1, a_2\) et \(a_3\text{.}\)Réponse.
(c)
Déterminer \(a_{7}\)Réponse.
\(a_7=47\)
6.
On note \(a_n\) le nombre de chaînes binaires de longueur \(n\) qui ne contiennent pas trois \(0\) consécutifs.
(a)
Trouver une relation de récurrencepour \(a_n\text{.}\)Réponse.
\(a_n = a_{n-1} + a_{n-2}+a_{n-3} \)
Solution.
Soit \(d_1\dots d_{n-3}d_{n-2}d_{n-1}d_n\) une chaîne binaire de longueur \(n\) qui ne contient pas trois \(0\) consécutifs. On sépare en plusieurs cas selon les valeurs des derniers caractères. En particulier, on sépare selon l’endroit où se trouve le dernier \(1\) dans la chaîne \(d_1\dots d_{n-3}d_{n-2}d_{n-1}d_n\text{.}\) Il y aura trois cas différents.
Si le dernier \(1\) est à la dernière position, c’est-à-dire si \(d_n=1\text{,}\) alors la chaîne \(d_1\dots d_{n-3}d_{n-2}d_{n-1}\) ne doit pas contenir trois \(0\) consécutifs. Il y a donc \(a_{n-1}\) possibilités.
Si le dernier \(1\) est à l’avant dernière position, c’est-à-dire si \(d_{n-1}d_n=10\text{,}\) alors la chaîne \(d_1\dots d_{n-3}d_{n-2}\) ne doit pas contenir trois \(0\) consécutifs. Il y a donc \(a_{n-2}\) possibilités.
Si le dernier \(1\) est à la troisième position en partant de la fin, c’est-à-dire si \(d_{n-2}d_{n-1}d_n=100\text{,}\) alors la chaîne \(d_1\dots d_{n-3}\) ne doit pas contenir trois \(0\) consécutifs. Il y a donc \(a_{n-3}\) possibilités.
Finalement, on remarque que le dernier \(1\) ne peu pas être avant le \(d_{n-2}\text{.}\) En effet, si c’était le cas, on aurait \(d_{n-2}d_{n-1}d_n=000\text{,}\) mais alors il y aurait trois \(0\) consécutifs dans la chaîne \(d_1\dots d_{n-3}d_{n-2}d_{n-1}d_n=d_1\dots d_{n-3}000\text{.}\)
Par le principe de la somme, on a \(a_n=a_{n-1} + a_{n-2}+a_{n-3}\text{.}\)
(b)
Trouver les conditions initiales, c’est-à-dire trouver \(a_1, a_2\) et \(a_3\text{.}\)Réponse.
(c)
Déterminer \(a_{7}\)Réponse.
\(a_7=81\)
7.
On considère un échiquier de dimension \(2\times n\text{,}\) c’est-à-dire un échiquer formé de deux rangés, et chacune de ces rangés est formée de \(n\) cases. On veut recouvrir cet échiquer à l’aide de tuiles de dimension \(1\times 2\text{,}\) \(2\times 1\) et \(2\times 2\text{.}\)
On note \(a_n\) le nombre de façons d’accomplir cette tâche.
(a)
Solution.
Si \(n = 1\text{,}\) l’échiquier est de dimension \(2\times 1\text{.}\) Il y a donc une seule façon d’accomplir cette tâche, en plaçant une tuile \(2\times 1\text{.}\) Ainsi, \(a_1=1\text{.}\)
Si \(n = 2\text{,}\) l’échiquier est de dimension \(2\times 2\text{.}\) Il y a donc trois façons d’accomplir cette tâche. En plaçant deux tuiles de dimension \(2\times 1\text{,}\) en plaçant deux tuiles de dimension \(1\times 2\) ou encore en plaçant une tuile de dimension \(2\times 2\text{.}\) Ainsi, \(a_2=3\text{.}\)
(b)
Trouver une relation de récurrence pour \(a_n\text{.}\)
Solution.
On sépare la tâche en trois catégories. Pour se faire, on regarde quelle sorte de tuile à été utilisée afin de recouvrir la case en haut à gauche de l’échiquer. Il y a trois façons de le faire, une pour chaque type de tuiles, \(1\times 2\text{,}\) \(2\times 1\) ou \(2\times 2\text{.}\)
Si on a utilisé une tuile de dimension \(2\times 1\text{,}\) il reste à recouvrir un échiquier de dimension \(2\times (n-1)\text{.}\) Il y a \(a_{n-1}\) façons d’accomplir cette tâche.
Si on a utilisé une tuile de dimension \(1\times 2\text{,}\) alors on a nécessairement urilisé une autre tuile de dimension \(1\times 2\) pour recouvrir la case en bas à gauche. Il reste donc à recouvrir un échiquier de dimension \(2\times (n-2)\text{.}\) Il y a \(a_{n-2}\) façons d’accomplir cette tâche.
Finalement, si on a utilisé une tuile de dimension \(2\times 2\text{,}\) il reste à recouvrir un échiquier de dimension \(2\times (n-2)\text{.}\) Il y a \(a_{n-2}\) façons d’accomplir cette tâche.
Ainsi, par le principe de la somme, on a \(a_n=a_{n-1}+a_{n-2}+a_{n-2}=a_{n-1}+2a_{n-2}\text{.}\)
(c)
Résoudre la relation de récurrence à l’aide des conditions initiales (à l’aide de \(a_1\) et \(a_2\)).
Solution.
À l’aide de l’équation caractéristique, on trouve que \(a_n=\alpha_1 (2)^n + \alpha_2 (-1)^n\text{.}\)
Puisque \(1=a_1= 2\alpha_1-\alpha_2\) et \(3=a_2=4\alpha_1 +\alpha_2\text{,}\) on peut résoudre ces équations et obtenir \(\alpha_1=\frac{2}{3}\) et \(\alpha_2=\frac{1}{3}\text{.}\)
Ainsi, \(a_n=\frac{2\cdot 2^n}{3}+\frac{1(-1)^n}{3}=\frac{2^{n+1}+(-1)^n}{3}\text{.}\)
8.
On considère \(s_n\) le nombre de chaînes binaites de longueur \(n\) qui contiennent la suite de caractères \(01\text{.}\)
(a)
(b)
Trouver une relation re récurrence pour la suite \(\{s_n\}\text{.}\)
Solution.
On considère la tâche d’écrire une chaîne binaire de longueur \(n\) contenant la suite \(01\text{.}\) On utilise le principe de la somme selon le premier caractère utilisé.
Si le premier caractère est un \(1\text{,}\) alors il doit y avoir la suite \(01\) à quelque part dans les \(n-1\) caractères restants. Ainsi, il reste à choisir une chaînes à \(n-1\) caractères contenant la suite \(01\text{.}\) Il y a \(s_{n-1}\) façons d’accomplir cette tâche.
Si le premier caractère utilisé est un \(0\text{,}\) il faut faire plus attention. On doit encore séparer en deux cas.
Tout d’abord, si la chaîne commence par \(0\text{,}\) il se peut que la suite \(01\) se trouve parmi les \(n-1\) caractères restants. Ainsi, il reste à choisir une chaînes à \(n-1\) caractères contenant la suite \(01\text{.}\) Il y a \(s_{n-1}\) façons d’accomplir cette tâche.
Cependant, on remarque que dans le cas précédent, on ne compte pas les chaînes qui contiennent la suite \(01\) uniquement dans les deux premiers caractères. On suppose donc que la suite \(01\) se retouve dans la chaîne uniquement au début de celle-ci. C’est-à-dire que la chaîne commence par \(01\text{,}\) mais n’a pas la suite \(01\) dans les \(n-2\) caractères restants. Ainsi, il reste à choisir une chaîne de \(n-2\) caractères qui ne contient pas la suite \(01\text{.}\) En passant par le complément, il y a \(2^{n-2}-s_{n-2}\) façons d’accomplir cette tâche.
Par le principe de la somme, on a \(s_n=2s_{n-1}-s_{n-2}+2^{n-2}\text{.}\)
(c)
Trouver une expression pour \(s_n\text{.}\) Puisque la relation est non homogène, on devra utiliser une solution particulière. Prendre une solution particulière de la forme \(c 2^n\text{,}\) où \(c\in \R\) est une constante à déterminer.
Solution.
On commence par résoudre la relation homogène. On trouve alors \(s_n^{(h)}=\alpha_1 (1)^n + \alpha_2 n (1)^n= \alpha_1 + \alpha_2 n\)
Ensuite, on remplaçant par \(c2^n\) dans la relation, on obtient
\begin{align*}
c2^n \amp = 2(c2^{n-1}) - c2^{n-2} + 2^{n-2} \amp\amp \\
\Rightarrow 2c \amp = 2c - c+1 \amp\amp \text{ en divisant par } 2^{n-2}\\
\Rightarrow c \amp = 1 \amp\amp \text{.}
\end{align*}
Ainsi, on a que \(s_n = \alpha_1 + \alpha_2 n + 2^n\text{.}\) À l’aide des conditions initiales, on a \(s_1=0 = \alpha_1 + \alpha_2\) et \(s_2=1=\alpha_1 + 2\alpha_2\text{.}\) On peut résoudre ces équations et obtenir \(\alpha_1=-1\) et \(\alpha_2=1\text{.}\)
Par ce qui précède, on a \(s_n= -1 + n + 2^n\text{.}\)
