2.3 Problème de chaînes ternaires

Combien y a-t-il de chaînes ternaire de longueur $\displaystyle 10$ pour lesquels aucun $\displaystyle 1$ n’est adjacent (avant ou après) à un $\displaystyle 0$ ? Ici, la méthode que nous avons utilisé pour l’exemple précédent n’est pas d’une grande utilité. L’astuce est d’utiliser des variables intermédiaires. On commence par dénoter par $\displaystyle x_{n}$ le nombre de chaînes ternaires de longueurs $\displaystyle n$ qui n’ont pas de $\displaystyle 0$ et $\displaystyle 1$ adjacents (i.e. les chaînes valides). On divise ensuite les solutions en différents cas:

$\displaystyle a_{n}$	$\displaystyle=$	Les chaînes valides de longueur $\displaystyle n$ qui se termine par un $\displaystyle 0$
$\displaystyle b_{n}$	$\displaystyle=$	Les chaînes valides de longueur $\displaystyle n$ qui se termine par un $\displaystyle 1$
$\displaystyle c_{n}$	$\displaystyle=$	Les chaînes valides de longueur $\displaystyle n$ qui se termine par un $\displaystyle 2$

Maintenant, remarquons que pour toutes les chaînes valides qui se termine par un $\displaystyle 0$ , on peut toujours ajouter soit un $\displaystyle 0$ ou un $\displaystyle 2$ . De plus, pour les chaînes valides qui se termine par un $\displaystyle 1$ , on peut ajouter un $\displaystyle 0$ ou un $\displaystyle 2$ . Finalement, pour les chaînes valides se terminant par un $\displaystyle 2$ , on peut ajouter soit un $\displaystyle 0$ , $\displaystyle 1$ ou $\displaystyle 2$ . Ceci peut être représenter par l’automate ci-dessous:

À partir de ceci, on peut obtenir les systèmes de récurrences suivants:

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

Auquel nous devons ajouter les valeurs initiales $\displaystyle a_{1}=b_{1}=c_{1}=1$ . Il est relativement facile à partir de ces équations de calculer $\displaystyle a_{10},b_{10}$ et $\displaystyle c_{10}$ , puis les additionner pour obtenir la solution de notre problème. À nouveau, ceci peut être facilement accompli à l’aide de Python.

Listing 4: Problème des chaînes ternaires à l’aide d’un système de récurrences

⬇


              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) + c(n-1)


              10
              
              
              
            


              11
              
              
              
            def b(n):


              12
              
              
              
                if n == 1:


              13
              
              
              
                    return 1


              14
              
              
              
                else:


              15
              
              
              
                    return b(n-1) + c(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)


              22
              
              
              
            


              23
              
              
              
            tableau = DataFrame({


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


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


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


              27
              
              
              
                "Somme": [a(n) + b(n) + c(n) for n in range(1,11)]


              28
              
              
              
            })


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


              30
              
              
              
            tableau

Ce qui nous permet d’obtenir le tableau suivant:

$\displaystyle n$	$\displaystyle a_{n}$	$\displaystyle b_{n}$	$\displaystyle c_{n}$	Somme
1	1	1	1	3
2	2	2	3	7
3	5	5	7	17
4	12	12	17	41
5	29	29	41	99
6	70	70	99	239
7	169	169	239	577
8	408	408	577	1393
9	985	985	1393	3363
10	2378	2378	3363	8119

Il y a donc un total de $\displaystyle 8119$ chaînes ternaires de longueur $\displaystyle 10$ pour lesquels aucun $\displaystyle 1$ n’est adjacent à un $\displaystyle 0$ . Comme pour l’exemple des chaînes binaires, il nous est aussi possible de ramener notre système de récurrence en une seule récurrence.

$\displaystyle\displaystyle x_{n}$	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle a_{n}+b_{n}+c_{n}$
	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle a_{n-1}+c_{n-1}+b_{n-1}+c_{n-1}+a_{n-1}+b_{n-1}+c_{% n-1}$
	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle 2(a_{n-1}+b_{n-1}+c_{n-1})+c_{n-1}$
	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle 2x_{n-1}+c_{n-1}$
	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle 2x_{n-1}+(a_{n-2}+b_{n-2}+c_{n-2})$
	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle 2x_{n-1}+x_{n-2}$

Cette dernière récurrence étant valide pour tout $\displaystyle n\geq 3$ . Il nous faut cependant deux valeurs initiales. On a donc $\displaystyle x_{1}=3$ et $\displaystyle x_{2}=7$ . La récurrence décrivant notre problème est donc:

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

À partir de cette dernière, il devient relativement simple d’utiliser Python pour construire un tableau avec les différentes valeurs de $\displaystyle x_{n}$ .

Listing 5: Problème des chaînes ternaires à l’aide d’une seule récurrence

⬇


              1
              
              
              
            from sympy import *


              2
              
              
              
            from pandas import *


              3
              
              
              
            init_printing()


              4
              
              
              
            


              5
              
              
              
            def x(n):


              6
              
              
              
                if n == 1:


              7
              
              
              
                    return 3


              8
              
              
              
                if n == 2:


              9
              
              
              
                    return 7


              10
              
              
              
                else:


              11
              
              
              
                    return 2*x(n-1) + x(n-2)


              12
              
              
              
            


              13
              
              
              
            tableau = DataFrame([[x(n) for n in range(1,11)]])


              14
              
              
              
            tableau.columns = [n for n in range(1,11)]


              15
              
              
              
            tableau.index = ["valeurs"]


              16
              
              
              
            tableau

Ce qui nous donne le tableau suivant:

$\displaystyle n$	1	2	3	4	5	6	7	8	9	10
$\displaystyle x_{n}$	3	7	17	41	99	239	577	1393	3363	8119

Nous obtenons donc à nouveau qu’il y a $\displaystyle 8119$ chaînes ternaires de longueur $\displaystyle 10$ qui n’ont pas de $\displaystyle 0$ et $\displaystyle 1$ adjacents.

L’algèbre linéaire nous donne une autre approche pour résoudre le problème. En effet, le système d’équations de récurrence peut être réécrit sous la forme matricielle suivante:

\displaystyle\begin{pmatrix}a_{n}\\ b_{n}\\ c_{n}\end{pmatrix}=\begin{pmatrix}1&0&1\\ 0&1&1\\ 1&1&1\end{pmatrix}\begin{pmatrix}a_{n-1}\\ b_{n-1}\\ c_{n-1}\end{pmatrix}=\begin{pmatrix}1&0&1\\ 0&1&1\\ 1&1&1\end{pmatrix}^{2}\begin{pmatrix}a_{n-2}\\ b_{n-2}\\ c_{n-2}\end{pmatrix}=...=\begin{pmatrix}1&0&1\\ 0&1&1\\ 1&1&1\end{pmatrix}^{n-1}\begin{pmatrix}a_{1}\\ b_{1}\\ c_{1}\end{pmatrix}

Pour trouver la solution de notre problème, on a donc:

\displaystyle\begin{pmatrix}a_{10}\\ b_{10}\\ c_{10}\end{pmatrix}=\begin{pmatrix}1&0&1\\ 0&1&1\\ 1&1&1\end{pmatrix}^{9}\begin{pmatrix}1\\ 1\\ 1\end{pmatrix}=\begin{pmatrix}2378\\ 2378\\ 3363\end{pmatrix}

La solution du problème est donc $\displaystyle x_{10}=2378+2378+3363=8119$ chaînes ternaires. Remarquez qu’ici pour calculer facilement l’exposant de la matrice, il est à nouveau nécessaire d’utiliser un logiciel tel que Python.

Listing 6: Problème des chaînes ternaires version matricielle

⬇


              1
              
              
              
            from sympy import *


              2
              
              
              
            init_printing()


              3
              
              
              
            


              4
              
              
              
            A = Matrix([[1,0,1],[0,1,1],[1,1,1]])


              5
              
              
              
            b = Matrix([1,1,1])


              6
              
              
              
            Reponse = A**9 * b


              7
              
              
              
            Reponse.norm(1)

À la place d’utiliser Python, il aurait aussi été possible d’effectuer la diagonalisation de la matrice à l’aide des valeurs propres et des vecteurs propres pour évaluer la puissance de la matrice.