2.2 Problème de chaines binaires

Combien y a-t-il de chaines binaires de longueur $\displaystyle 10$ ne contenant pas deux $\displaystyle 0$ consécutifs? Pour ce faire, nous pourrions bien évidement énumérer toutes les possibilités, mais à première vu il semble y en avoir beaucoup. Nous allons donc plutôt prendre l’approche de définir une relation de récurrence. Posons $\displaystyle a_{n}$ le nombre de chaine binaire de longueur $\displaystyle n$ ne contenant pas deux $\displaystyle 0$ consécutif. Il est facile de voir que $\displaystyle a_{1}=2$ et $\displaystyle a_{2}=3$ . Maintenant, remarquons qu’une chaine binaire de longueur $\displaystyle n$ avec $\displaystyle n\geq 2$ doit soit se terminer par un $\displaystyle 0$ ou bien par un $\displaystyle 1$ . Pour toutes les chaines de longueur $\displaystyle n-1$ , il est toujours possible d’ajouter un $\displaystyle 1$ à la fin pour obtenir une chaine binaire de longueur $\displaystyle n$ satisfaisant le problème, par contre ceci n’est pas possible avec $\displaystyle 0$ car on risquerait d’obtenir une chaine qui se termine par $\displaystyle 00$ . Donc si une chaine binaire de longueur $\displaystyle n$ ne contient pas pas deux $\displaystyle 0$ consécutif et se termine par $\displaystyle 0$ , alors elle doit obligatoirement se terminer par $\displaystyle 10$ . On remarque alors qu’il que ceci correspond en fait au nombre de chaine de longueur $\displaystyle n-2$ qui satisfait le problème. Ceci peut-être visualisé sous forme du diagramme suivant:

À partir de ces informations, on obtient donc la récurrence suivante:

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

À partir de la récurrence, il devient maintenant beaucoup plus simple de répondre à la question. Il est possible de la résoudre pour obtenir une formule explicite, mais dans le cas présent, comme nous cherchons uniquement la $\displaystyle 10e$ valeur, on peut utiliser le code suivant:

Listing 1: Valeur unique pour le problème des chaînes binaires

⬇


              1
              
              
              
            from sympy import *


              2
              
              
              
            from pandas import *


              3
              
              
              
            init_printing()


              4
              
              
              
            


              5
              
              
              
            def a(n):


              6
              
              
              
                if n == 1:


              7
              
              
              
                    return 2


              8
              
              
              
                if n == 2:


              9
              
              
              
                    return 3


              10
              
              
              
                else:


              11
              
              
              
                    return a(n-1) + a(n-2)


              12
              
              
              
            


              13
              
              
              
            a(10)

qui nous permet d’obtenir directement la valeur de $\displaystyle a_{10}=144$ . Remarquons cependant que dans la plupart des cas, il est plus intéressant de faire un tableau de valeurs complet. Ceci peut bien entendu être obtenu à la main, mais aussi automatiquement à l’aide de Python en utilisant plutôt le code suivant:

Listing 2: Tableau pour le problème des chaînes binaires

⬇


              1
              
              
              
            from sympy import *


              2
              
              
              
            from pandas import *


              3
              
              
              
            init_printing()


              4
              
              
              
            


              5
              
              
              
            def a(n):


              6
              
              
              
                if n == 1:


              7
              
              
              
                    return 2


              8
              
              
              
                if n == 2:


              9
              
              
              
                    return 3


              10
              
              
              
                else:


              11
              
              
              
                    return a(n-1) + a(n-2)


              12
              
              
              
            


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


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


              15
              
              
              
            tableau.index = ["Valeurs"]


              16
              
              
              
            tableau

Ce dernier code nous permet alors d’obtenir le tableau suivant:

$\displaystyle n$	1	2	3	4	5	6	7	8	9	10
$\displaystyle a_{n}$	2	3	5	8	13	21	34	55	89	144

À nouveau, on obtient que le nombre de chaînes binaires de longueur $\displaystyle 10$ qui ne contient pas deux $\displaystyle 0$ consécutifs est $\displaystyle 144$ . Alternativement, on peut aussi répondre à cette question à partir d’un système d’équations définie par récurrence. Ceci peut-être accompli à partir de variable intermédiaire et d’un automate. Nous allons donc définir les variables suivantes:

$\displaystyle x_{n}$	$\displaystyle=$	Les chaînes binaires de longueur $\displaystyle n$ qui ne contiennent pas deux $\displaystyle 0$ consécutif et qui se termine par un $\displaystyle 0$
$\displaystyle y_{n}$	$\displaystyle=$	Les chaînes binaires de longueur $\displaystyle n$ qui ne contiennent pas deux $\displaystyle 0$ consécutif et qui se termine par un $\displaystyle 1$

D’après la définition, nous savons que si le dernier chiffre est un $\displaystyle 1$ , on peut toujours ajouter un $\displaystyle 0$ ou un $\displaystyle 1$ . Par contre, si le dernier chiffre est un $\displaystyle 0$ , alors on peut uniquement ajouter un $\displaystyle 1$ . Ceci nous donne donc l’automate suivant:

Ceci nous donne le système suivant:

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

Avec les valeurs initiales $\displaystyle x_{1}=y_{1}=1$ . À nouveau, Python peut nous permettre de compléter directement un tableau avec les différentes valeurs.

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

⬇


              1
              
              
              
            from sympy import *


              2
              
              
              
            from pandas import *


              3
              
              
              
            init_printing()


              4
              
              
              
            


              5
              
              
              
            def x(n):


              6
              
              
              
                if n == 1:


              7
              
              
              
                    return 1


              8
              
              
              
                else:


              9
              
              
              
                    return y(n-1)


              10
              
              
              
            


              11
              
              
              
            def y(n):


              12
              
              
              
                if n == 1:


              13
              
              
              
                    return 1


              14
              
              
              
                else:


              15
              
              
              
                    return x(n-1) + y(n-1)


              16
              
              
              
            


              17
              
              
              
            tableau = DataFrame({


              18
              
              
              
                "x_n": [x(n) for n in range(1,11)],


              19
              
              
              
                "y_n": [y(n) for n in range(1,11)],


              20
              
              
              
                "Somme": [x(n) + y(n) for n in range(1,11)]


              21
              
              
              
            })


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


              23
              
              
              
            tableau

Ce qui nous permet cette fois d’obtenir le tableau suivant. Notez que ce tableau, en plus de nous donner le nombre de chaînes qui ne contiennent pas deux $\displaystyle 0$ consécutifs, les séparent en nombre de ces chaînes qui se terminent par un $\displaystyle 0$ et en chaînes qui se terminent par un $\displaystyle 1$ .

$\displaystyle n$	$\displaystyle x_{n}$	$\displaystyle y_{n}$	Somme
1	1	1	2
2	1	2	3
3	2	3	5
4	3	5	8
5	5	8	13
6	8	13	21
7	13	21	34
8	21	34	55
9	34	55	89
10	55	89	144

Bien qu’il soit possible de travailler directement avec ce système, dans le cas présent il est aussi facile de le simplifier pour obtenir la récurrence que nous avions déjà obtenu. Comme nous sommes intéressé par les chaînes qui se termine par $\displaystyle 0$ et celle qui se termine $\displaystyle 1$ , la solution du problème est donné par la récurrence suivante:

\displaystyle a_{n}=x_{n}+y_{n}=y_{n-1}+x_{n-1}+y_{n-1}=a_{n-1}+y_{n-1}=a_{n-1% }+x_{n-2}+y_{n-2}=a_{n-1}+a_{n-2}

On remarque immédiatement qu’il s’agit de la même récurrence que nous avions obtenu précédemment.