2.5 Problème de mots

Combien de mots de $\displaystyle 10$ lettres formé à partir de l’alphabet $\displaystyle{\cal A}=\{a,b,c,d\}$ contiennent la séquence $\displaystyle aab$ ? Pour résoudre se problème, remarquons premièrement que contrairement aux problèmes précédents, nous ne cherchons pas à exclure une séquence des mots acceptable, mais plutôt à compter uniquement ceux qui la contiennent. Une première approche consisterait à travailler avec le complément, ce qui peut être accompli de manière très similaire à ce que nous avons fait dans le problème des chaînes ternaires. Nous allons cependant prendre une approche différente et chercher plutôt à les compter directement. L’idée est à nouveau de travailler avec un automate, mais cette fois en considérant un point de départ bien déterminé, et un point d’arriver correspondant aux mots qui contiennent la séquence.

L’idée est de lire un mot lettre par lettre, de gauche à droite, en commençant à notre état initiale que nous avons dénoté $\displaystyle X$ dans l’automate. Après avoir lu chaque lettre, on se déplace dans l’automate vers l’état correspondant à lettre que nous avons lu. Lorsque l’on rencontre un $\displaystyle a$ , on se déplace vers l’état suivant (dénoté $\displaystyle Y$ ), si la lettre suivante est aussi un $\displaystyle a$ , on continue vers le troisième état (dénoté $\displaystyle Z$ ), et de même, si la lettre suivante est un $\displaystyle b$ , on se déplace vers le dernier état (dénoté $\displaystyle W$ ). Lorsque nous avons atteint l’état $\displaystyle W$ , cela signifie que notre mot contient la séquence $\displaystyle aab$ . De plus, lorsque nous sommes aux états $\displaystyle Y$ ou $\displaystyle Z$ et que la lettre lu ne correspond pas à ce que nous avons besoin pour former la séquence $\displaystyle aab$ , alors on revient à notre état initiale. Si on dénote par $\displaystyle x_{n},y_{n},z_{n}$ et $\displaystyle w_{n}$ les suites correspondant à chacun des états, alors on obtient le système d’équations définies par récurrence suivant:

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

De plus, comme au départ, avant de commencer la lecture, nous sommes à l’état $\displaystyle X$ , on définit les valeurs initiales comme étant $\displaystyle x_{0}=1,y_{0}=z_{0}=w_{0}=0$ . Comme nous sommes intéressé par les mots de $\displaystyle 10$ lettres qui contiennent la séquence $\displaystyle aab$ , nous cherchons à trouver le nombre de mots qui seront à l’état $\displaystyle W$ après $\displaystyle 10$ étapes, c’est à dire on cherche la valeur de $\displaystyle w_{10}$ . On peut alors utiliser le code Python suivant:

Listing 9: Problème de mots: Méthode 1

⬇


              1
              
              
              
            from sympy import *


              2
              
              
              
            from pandas import *


              3
              
              
              
            init_printing()


              4
              
              
              
            


              5
              
              
              
            def x(n):


              6
              
              
              
                if n == 0:


              7
              
              
              
                    return 1


              8
              
              
              
                else:


              9
              
              
              
                    return 3*x(n-1) + 3*y(n-1) + 2*z(n-1)


              10
              
              
              
            


              11
              
              
              
            def y(n):


              12
              
              
              
                if n == 0:


              13
              
              
              
                    return 0


              14
              
              
              
                else:


              15
              
              
              
                    return x(n-1)


              16
              
              
              
            


              17
              
              
              
            def z(n):


              18
              
              
              
                if n == 0:


              19
              
              
              
                    return 0


              20
              
              
              
                else:


              21
              
              
              
                    return y(n-1) + z(n-1)


              22
              
              
              
            


              23
              
              
              
            def w(n):


              24
              
              
              
                if n == 0:


              25
              
              
              
                    return 0


              26
              
              
              
                else:


              27
              
              
              
                    return z(n-1) + 4*w(n-1)


              28
              
              
              
            


              29
              
              
              
            DataFrame({


              30
              
              
              
                "x_n": [x(n) for n in range(0,11)],


              31
              
              
              
                "y_n": [y(n) for n in range(0,11)],


              32
              
              
              
                "z_n": [z(n) for n in range(0,11)],


              33
              
              
              
                "w_n": [w(n) for n in range(0,11)]


              34
              
              
              
            })

Ce qui nous permet d’obtenir facilement le tableau suivant:

$\displaystyle n$	$\displaystyle x_{n}$	$\displaystyle y_{n}$	$\displaystyle z_{n}$	$\displaystyle w_{n}$
0	1	0	0	0
1	3	1	0	0
2	12	3	1	0
3	47	12	4	1
4	185	47	16	8
5	728	185	63	48
6	2865	728	248	255
7	11275	2865	976	1268
8	44372	11275	3841	6048
9	174623	44372	15116	28033
10	687217	174623	59488	127248

Il y a donc $\displaystyle 127\leavevmode\nobreak\ 248$ mots de $\displaystyle 10$ lettres qui contiennent la séquence $\displaystyle aab$ .

Il est aussi possible d’utiliser la même approche que pour les problèmes de chaînes binaires et ternaires, mais dans ce cas, les choses se compliquent un peu. En effet, les automates que nous avons utilisés pour résoudre ces problèmes nous permettent de compter le nombre de chaînes ou de mots qui excluent une certaine séquence. On peut donc travailler avec le complément. Il nous est cependant nécessaire de créer deux états distincts pour les $\displaystyle A$ . Un premier pour les mots de $\displaystyle n$ lettres se terminant par un seul $\displaystyle A$ , et un autre pour les mots de $\displaystyle n$ lettres se terminant par au moins deux $\displaystyle A$ (Que nous dénotons par $\displaystyle AA$ ).

En dénotant par $\displaystyle e_{n}$ la suite des mots qui se termine par $\displaystyle AA$ , on obtient donc le système de récurrences suivant:

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

avec les valeurs initiales $\displaystyle a_{1}=b_{1}=c_{1}=d_{1}=1$ et $\displaystyle e_{1}=0$ .

Ce qui peut être facilement implémenté dans Python. Il faut cependant faire attention, car, comme nous l’avons mentionné plus tôt, notre automate travaille avec le complément. Comme il y a $\displaystyle 4^{n}$ mots de $\displaystyle n$ lettres au total, le nombre de mots de $\displaystyle n$ lettre qui contiennent la séquence $\displaystyle AAB$ est donc:

\displaystyle 4^{n}-a_{n}-b_{n}-c_{n}-d_{n}-e_{n}

Listing 10: Problème de mots: Méthode 2

⬇


              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 b(n-1) + c(n-1) + d(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 a(n-1) + b(n-1) + c(n-1) + d(n-1) + e(n-1)


              22
              
              
              
            


              23
              
              
              
            def d(n):


              24
              
              
              
                if n == 1:


              25
              
              
              
                    return 1


              26
              
              
              
                else:


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


              28
              
              
              
            


              29
              
              
              
            def e(n):


              30
              
              
              
                if n == 1:


              31
              
              
              
                    return 0


              32
              
              
              
                else:


              33
              
              
              
                    return a(n-1) + e(n-1)


              34
              
              
              
            


              35
              
              
              
            def total(n):


              36
              
              
              
                return 4**n


              37
              
              
              
            


              38
              
              
              
            def sansAAB(n):


              39
              
              
              
                return a(n) + b(n) + c(n) + d(n) + e(n)


              40
              
              
              
            


              41
              
              
              
            def avecAAB(n):


              42
              
              
              
                return total(n) - sansAAB(n)


              43
              
              
              
            


              44
              
              
              
            tableau = DataFrame({


              45
              
              
              
                "Tout": [total(n) for n in range(1,11)],


              46
              
              
              
                "Sans AAB": [sansAAB(n) for n in range(1,11)],


              47
              
              
              
                "Avec AAB": [avecAAB(n) for n in range(1,11)]


              48
              
              
              
            })


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


              50
              
              
              
            tableau

Ce qui nous permet d’obtenir le tableau suivant:

$\displaystyle n$	Tout	Sans AAB	Avec AAB
1	4	4	0
2	16	16	0
3	64	63	1
4	256	248	8
5	1024	976	48
6	4096	3841	255
7	16384	15116	1268
8	65536	59488	6048
9	262144	234111	28033
10	1048576	921328	127248

Comme pour notre première approche, nous obtenons à nouveau qu’il y a $\displaystyle 127\leavevmode\nobreak\ 248$ mots de $\displaystyle 10$ lettres qui contiennent la séquence $\displaystyle AAB$ .