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)}}

Cliquer ici pour voir (ou cacher) le corrigé