2.4 Problème de blocks

De combien de façon différente peut-on couvrir 10\displaystyle 10 cases (adjacentes) avec des blocks de couleur jaune, rouge, vert, bleu et violet, si les blocks de couleurs jaune, rouge et vert occupent chacun deux cases, et les blocks de couleur bleu et violet occupent trois cases ? Voici un exemple d’une telle configuration.

La première chose à remarquer est que les options pour le dernier block dépend des blocks qui ont déjà été placé avant lui. Ceci est un indication qu’une récurrence est particulièrement adapté pour résoudre le problème. Pour construire cette récurrence, remarquons que le nombre de suite de blocks de longueur n\displaystyle n qui se termine avec un block jaune est égal au nombre de suite de blocks de longueur n−2\displaystyle n-2, car pour chacune de ces suites, on peut toujours ajouter un block jaune. Il en est de même pour les suites de blocks se terminant par un block rouge ou un block vert. Pour les suites de blocks de longueur n\displaystyle n se terminant par un block bleu, il y en a autant que de suite de block de longueur n−3\displaystyle n-3, car pour chacune de ces suites de block on peut toujours ajouter un block bleu, et de même pour les suites se terminant par un block violet. Comme une suite de block de longueur n\displaystyle n doit obligatoirement se terminer par un block jaune, rouge, vert, bleu ou violet. Ceci peut être visualiser à l’aide du diagramme en arbre suivant:

On obtient donc la récurrence suivante:

xn=3⁢xn−2+2⁢xn−3\displaystyle x_{n}=3x_{n-2}+2x_{n-3}

Comme cette suite utilise les trois valeurs précédentes, il nous faut donc trois valeurs initiales, ce qui peut facilement être obtenu par énumération. On a donc:

{xn=3⁢xn−2+2⁢xn−3,∀n≥4x1=0x2=3x3=2\displaystyle\left\{\begin{array}[]{l}x_{n}=3x_{n-2}+2x_{n-3},\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall n\geq 4\\ x_{1}=0\\ x_{2}=3\\ x_{3}=2\end{array}\right.

On peut alors utiliser le code Python suivant pour compléter un tableau de valeurs.

Listing 7: Problème de block: Récurrence
⬇

              1
              
              
              
            from sympy import *


              2
              
              
              
            from pandas import *


              3
              
              
              
            init_printing()


              4
              
              
              
            


              5
              
              
              
            def x(n):


              6
              
              
              
                if n == 1:


              7
              
              
              
                    return 0


              8
              
              
              
                if n == 2:


              9
              
              
              
                    return 3


              10
              
              
              
                if n == 3:


              11
              
              
              
                    return 2


              12
              
              
              
                else:


              13
              
              
              
                    return 3*x(n-2) + 2*x(n-3)


              14
              
              
              
            


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


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


              17
              
              
              
            tableau.index = ["Valeurs"]


              18
              
              
              
            tableau

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

n\displaystyle n 1 2 3 4 5 6 7 8 9 10
xn\displaystyle x_{n} 0 3 2 9 12 31 54 117 224 459

Il y a donc un total de 459\displaystyle 459 suites de blocks possible qui forment une chaîne de longueur n\displaystyle n. Il est aussi possible de trouver une formule explicite pour ce problème, ce que nous ferons plus tard. Pour le moment, vous pouvez utiliser l’induction pour démontrer que la récurrence satisfait la formule explicite suivante:

xn=49⁢(2)n+59⁢(−1)n+13⁢n⁢(−1)n,∀n≥1\displaystyle x_{n}=\frac{4}{9}(2)^{n}+\frac{5}{9}(-1)^{n}+\frac{1}{3}n(-1)^{n% },\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall n\geq 1

À partir de la formule explicite, il est à nouveau possible d’utiliser Python pour retrouver les différentes valeurs de notre tableau.

Listing 8: Problème de block: Formule explicite
⬇

              1
              
              
              
            from sympy import *


              2
              
              
              
            from pandas import *


              3
              
              
              
            init_printing()


              4
              
              
              
            


              5
              
              
              
            def x(n):


              6
              
              
              
                return Rational(4,9) * 2**n + Rational(5,9) * (-1)**n + Rational(1,3) * n * (-1)**n


              7
              
              
              
            


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


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


              10
              
              
              
            tableau.index = ["Valeurs"]


              11
              
              
              
            tableau