Exercice 1 — Les codes

Sujet

On considère des séquences de lettres vérifiant les propriétés suivantes :
(P1) Chaque séquence est exclusivement composée des lettres \(\mathrm{M}, \mathrm{A}\) et T .
(P2) Toute séquence commence par la lettre M .
(P3) Une séquence ne comporte jamais deux lettres consécutives identiques.
La longueur d'une séquence est le nombre de lettres qui la composent.
Exemple. La séquence M TM AM TAT, est une séquence de longueur 8 et se terminant par la lettre T.
Pour chaque entier \(\mathrm{n} \geq 1\), on note :

• \(\mathrm{s}_{\mathrm{n}}\) : le nombre total de séquences de longueur n ;
• \(\mathrm{m}_{\mathrm{n}}\) : le nombre de séquences de longueur n qui se terminent par M ;
• \(\mathrm{a}_{\mathrm{n}}\) : le nombre de séquences de longueur n qui se terminent par A ;
• \(\quad t_{n}\) : le nombre de séquences de longueur \(n\) qui se terminent par \(T\).

Les parties I et II peuvent être traitées de façons indépendantes.

Partie I

1. Déterminer \(\mathrm{m}_{1}, \mathrm{a}_{1}\) et \(\mathrm{t}_{1}\).
2. Justifier que \(\mathrm{m}_{2}=0, \mathrm{a}_{2}=1\) et \(\mathrm{t}_{2}=1\).
3. Déterminer \(\mathrm{m}_{3}, \mathrm{a}_{3}\) et \(\mathrm{t}_{3}\).
4. Justifier que : \(\mathrm{s}_{5}=2^{4}\).
5. On donne : \(\mathrm{m}_{6}=10\) et \(\mathrm{a}_{6}=\mathrm{t}_{6}=11\). En déduire : \(\mathrm{m}_{7}\) et \(\mathrm{t}_{7}\).

Partie II

Un code est constitué de trois des séquences décrites ci-dessus, toutes les trois de longueur 6. Ainsi, le code cidessous est la succession de trois séquences de longueur 6, finissant respectivement par \(M\), \(A\) et \(T\) :

On rappelle que : \(\mathrm{m}_{6}=10\) et \(\mathrm{t}_{6}=11\).
Combien existe-t-il de codes différents formés par la succession de :

1. trois séquences identiques finissant par \(M\) ?
2. trois séquences différentes finissant par \(M\) ?
3. deux séquences identiques finissant par \(M\) et une séquence finissant par \(T\) (pas nécessairement dans cet ordre) ?
4. deux séquences différentes finissant par \(M\) et une séquence finissant par \(T\) (pas nécessairement dans cet ordre) ?

Remarque: La structure primaire d'une protéine est modélisée par un code de ce type.