Pavage par des dominos

Publié le 28/01/17

Soit {{\mathcal U}_{n}} une surface rectangulaire de 4*n cases.
Soit {u_{n}} le nombre de façons de remplir {{\mathcal U}_{n}} par des dominos (horizontaux ou verticaux).
On voit ci-dessous un exemple de remplissage du rectangle {{\mathcal U}_{9}}.
article-28-01-17-fig1

  1. Trouver une relation de récurrence vérifiée par les {u_{n}}.
    Indication : comment la dernière colonne a-t-elle été remplie?
  2. Écrire une fonction Python permettant de calculer {u_n}.
    Vérifier, par exemple, que {u_{30}=21096536145301}.
  3. On définit le polynôme {P(x)=x^4-x^3-5x^2-x+1}
    Déterminer les racines {x_{1}\lt x_{2}\lt x_{3}\lt x_{4}} de P.
    Vérifier numériquement avec Python.
  4. Prouver que : {\forall\, n\in\mathbb{N},\;u_{n}=\dfrac1{\sqrt{29}}(-x_{1}^{n+1}-x_{2}^{n+1}+x_{3}^{n+1}+x_{4}^{n+1})}
  5. Montrer que, sur un intervalle à préciser: {\displaystyle\sum_{n=0}^{+\infty}u_{n}x^n=\dfrac{1-x^2}{P(x)}}

  1. On note respectivement {{\mathcal V}_{n}} et {{\mathcal W}_{n}} les surfaces rectangulaires incomplètes (pour ce qui est de la colonne la plus à droite), telles qu’elles sont représentées (fig.2) et (fig.3) dans le cas particulier {n=9}.
    article-28-01-17-fig2
    article-28-01-17-fig3
    La hauteur de {{\mathcal V}_{n},{\mathcal W}_{n}} est {4}, leur largeur totale est {n}.
    On note {v_{n}} (resp. {w_{n}}) le nombre de façons de remplir {{\mathcal V}_{n}} (resp. {{\mathcal W}_{n}}) avec de tels dominos.

    Il est clair que {u_{1}=v_{1}=w_{1}=1}.
    On complète ces définitions en posant {u_{0}=1} et {v_{0}=w_{0}=0} (ces conventions assurent que les relations de récurrence étudiées dans l’exercice sont vraies à partir de l’entier {0}).
    On considère l’un quelconques des {u_{n}} remplissages de {{\mathcal U}_{n}}.
    On discute suivant la façon dont on remplit la colonne la plus à droite.

    • On peut la remplir avec deux dominos verticaux (comme dans l’exemple fig.1).
      Il y a bien sûr {u_{n-1}} façons de procéder de cette manière (il reste à remplir {{\mathcal U}_{n-1}}).
    • On peut la remplir avec un domino vertical séparé par deux dominos horizontaux, comme indiqué fig.a: il y a alors {w_{n-1}} façons de procéder (car il reste à remplir {{\mathcal W}_{n-1}}).
    • On peut la remplir avec un domino vertical et deux dominos horizontaux contigus, comme indiqué fig.b ou fig.c. Dans chacune de ces éventualités (qui s’excluent), il y a {v_{n-1}} possibilités car il reste à remplir {{\mathcal V}_{n-1}} (ou le symétrique de {{\mathcal V}_{n-1}} par rapport à l’axe horizontal médian, on va pas chipoter).
    • On peut la remplir avec quatre dominos horizontaux, et il y a {u_{n-2}} possibilités (si {n=2}, c’est cohérent avec {u_{0}=1}: la seule façon de remplir un rectangle vide, c’est de ne rien faire…)

    article-28-01-17-abc
    Finalement, on a : {u_{n}=u_{n-1}+2v_{n-1}+w_{n-1}+u_{n-2}} pour tout {n\ge2}.

    Avec des arguments analogues, on a {\begin{cases}v_{n}=u_{n-1}+v_{n-1}\text{\ pour\ }n\ge1\\w_{n}=u_{n-1}+w_{n-2}\text{\ pour\ }n\ge2\end{cases}}

    Remarque: si {n=2}, la condition {w_{n}=u_{n-1}+w_{n-2}} est valable en posant {w_{0}=0}.

    On trouve {\begin{cases}u_{2}=u_{1}+2v_{1}+w_{1}+u_{0}=5\\v_{2}=u_{1}+v_{1}=2\cr w_{2}=u_{1}+w_{0}=1\end{cases}}

    On obtient également {u_{3}=u_{2}+2v_{2}+w_{2}+u_{1}=11}.

    Pour {n\ge4}, on a {\begin{cases}u_{n}=u_{n-1}+2v_{n-1}+w_{n-1}+u_{n-2}\\u_{n-2}=u_{n-3}+2v_{n-3}+w_{n-3}+u_{n-4}\end{cases}}

    On remarque que {\begin{cases}v_{n-1}-v_{n-3}=u_{n-2}+u_{n-3}\\w_{n-1}-w_{n-3}=u_{n-2}\end{cases}}.

    Ainsi, par différence :
    \begin{array}{rl}u_{n}-u_{n-2}&=(u_{n-1}-u_{n-3})+2(u_{n-2}+u_{n-3})\\&\phantom{\Bigl(}+\,u_{n-2}+(u_{n-2}-u_{n-4})\end{array}Finalement : {\forall n\ge4,\;u_{n}=u_{n-1}+5u_{n-2}+u_{n-3}-u_{n-4}}

  2. Voici la fonction suite, et la vérification demandée :

  3. Avec le changement de variable y=x+\dfrac{1}{x}, on trouve :
    {\begin{array}{rl}\dfrac{P(x)}{x^2}&=x^{2}-x-5-\dfrac{1}{x}+\dfrac{1}{x^{2}}\\&=y^{2}-y-7\end{array}}Ainsi : {P(x)=0\Leftrightarrow y^{2}-y-7=0\Leftrightarrow y\in\{a,b\}},
    \quadoù on a posé {a=\dfrac{1-\sqrt{29}}{2}} et {b=\dfrac{1+\sqrt{29}}{2}}

    Ensuite : {x+\dfrac{1}{x}=a\Leftrightarrow x^{2}-a x+1=0\Leftrightarrow x\in\{x_{1},x_{2}\}},
    \quadoù on a posé {x_{1}=\dfrac{a}{2}-\dfrac{\sqrt{a^{2}-4}}{2}} et {x_{2}=\dfrac{a}{2}+\dfrac{\sqrt{a^{2}-4}}{2}}

    De même : {x+\dfrac{1}{x}=b\Leftrightarrow x\in\{x_{3},x_{4}\}},
    \quadoù on a posé {x_{3}=\dfrac{b}{2}-\dfrac{\sqrt{b^{2}-4}}{2}} et {x_{4}=\dfrac{b}{2}+\dfrac{\sqrt{b^{2}-4}}{2}}:

    NB: {a^{2}-4=a+3=\dfrac{7-\sqrt{29}}{2}} et {b^{2}-4=b+3=\dfrac{7+\sqrt{29}}{2}}

    Les quatre racines de {P} sont donc :
    \begin{array}{c}x_{1}=\dfrac14-\dfrac14\,\sqrt {29}-\dfrac14\,\sqrt {14-2\,\sqrt {29}}\\\\x_{2}=\dfrac14-\dfrac14\,\sqrt {29}+\dfrac14\,\sqrt {14-2\,\sqrt {29}}\\\\x_{3}=\dfrac14+\dfrac14\,\sqrt {29}-\dfrac14\,\sqrt {14+2\,\sqrt {29}}\\\\x_{4}=\dfrac14+\dfrac14\,\sqrt {29}+\dfrac14\,\sqrt {14+2\,\sqrt {29}}\end{array}

    Avec Python, on crée les variables x1, x2, x3, x4 :

    On crée le polynôme P comme un objet de type poly1d.
    On calcule ensuite les racines de P, que l’on trie dans l’ordre croissant, et on place le résultat dans une variable racP. On retouve bien sûr les résultats précédents :

  4. Les suites géométriques {n\mapsto x_{k}^{n}}, satisfont à la même relation (E) que les u_n (l’équation caractéristique est {P(x)=0}).

    Par linéarité, {n\mapsto v_{n}=\dfrac1{\sqrt{29}}(-x_{1}^{n+1}-x_{2}^{n+1}+x_{3}^{n+1}+x_{4}^{n+1})} satisfait encore à (E).

    Comme c’est une récurrence de pas 4, il suffit de prouver {v_{n}=u_{n}} pour {0\le n\le 3}.

    On note : {a=\dfrac{1-\sqrt{29}}{2},\;b=\dfrac{1+\sqrt{29}}{2}} et {\begin{cases}s_{n}=x_{1}^{n}+x_{2}^{n}\\t_{n}=x_{3}^{n}+x_{4}^{n}\end{cases}}.

    Rappelons que x_1,x_2 sont les racines de x^{2}-ax+1=0
    et que x_3,x_4 sont les racines de x^{2}-bx+1=0.

    On en déduit les relations {\begin{cases}s_{n}=as_{n-1}-s_{n-2}\\t_{n}=at_{n-1}-t_{n-2}\end{cases}}.

    On sait que {\begin{cases}s_{0}=2,\;s_{1}=a\\t_{0}=2,\;t_{1}=b\end{cases}}, avec {\begin{cases}a^{2}=a+7\\b^{2}=b+7\end{cases}}

    On trouve alors {\begin{cases}s_{2}=as_{1}-s_{0}=a^{2}-2=a+5\\s_{3}=as_{2}-s_{1}=a^{2}+4a=5a+7\end{cases}}

    De même : {s_{4}=as_{3}-s_{2}=5a^{2}+6a-5=11a+30}

    Mutatis muntandis, on trouve : {t_{2}=b+5}, {t_{3}=5b+7}, {t_{4}=11b+30}.

    Ainsi, du fait que {b-a=\sqrt{29}} :
    {\begin{array}{ll}v_{0}=\dfrac1{\sqrt{29}}(t_{1}-s_{1})=1&v_{1}=\dfrac1{\sqrt{29}}(t_{2}-s_{2})=1\\\\v_{2}=\dfrac1{\sqrt{29}}(t_{3}-s_{3})=5&v_{3}=\dfrac1{\sqrt{29}}(t_{4}-s_{4})=11\end{array}}On a obtenu {u_{n}=v_{n}} pour {0\le n\le 3}.

    Conclusion : {\forall\, n\ge 3,\;u_{n}=\dfrac1{\sqrt{29}}(-x_{1}^{n+1}-x_{2}^{n+1}+x_{3}^{n+1}+x_{4}^{n+1})}.

  5. On a :
    {f(x)=\dfrac{1-x^2}{P(x)}=\dfrac{1-x^2}{(x-x_{1})(x-x_{2})(x-x_{3})(x-x_{4})(x-x_{5})}}.

    Ainsi {f} est DSE en 0, le rayon étant {R=\min|x_{k}|\approx 0.352}.

    Pour {\left|{x}\right|\lt \left|{x_{3}}\right|}, on a :
    {\begin{array}{l}(1-x-5x^2-x^3+x^4)\displaystyle\sum_{n=0}^{+\infty}u_{n}x^n\\=\displaystyle\sum_{n=0}^{+\infty}u_{n}x^n-\displaystyle\sum_{n=1}^{+\infty}u_{n-1}x^n-5\displaystyle\sum_{n=2}^{+\infty}u_{n-2}x^n-\displaystyle\sum_{n=3}^{+\infty}u_{n-3}x^n+\displaystyle\sum_{n=4}^{+\infty}u_{n-4}x^n\\\\=u_{0}+(u_{1}-u_{0})x+(u_{2}-u_{1}-5u_{0})x^2\\\phantom{\bigg(}+(u_{3}-u_{2}-5u_{1}-u_{0})x^3\\\quad+\displaystyle\sum_{n=4}^{+\infty}(u_{n}-u_{n-1}-5u_{n-2}-u_{n-3}+u_{n-4})x^{n}\\\\=1-x^2\end{array}}Ainsi, pour \left|{x}\right|\lt \left|{x_{3}}\right| : {\dfrac{1-x^2}{1-x-5x^2-x^3+x^4}=\displaystyle\sum_{n=0}^{+\infty}u_{n}x^{n}} .