Chemins auto-évitants

On dispose d’un échiquier rectangulaire comportant trois lignes et $nn$ colonnes, où $nn$ désigne un entier strictement positif. Une tour est placée sur la case inférieure gauche et doit rejoindre la case supérieure gauche.

La tour peut passer d’une case à une case contiguë par un côté commun, mais elle ne peut pas repasser par une case qu’elle a déjà occupée : sa trajectoire est dite auto-évitante. On note $R(n)R(n)$ le nombre de chemins possibles sur un tel échiquier.