Dans le cas 2xN, c'est la suite de Fibonacci : un pavage 2xN commence à gauche soit par un domino vertical, puis il y a un pavage 2x(N-1) ; soit par deux dominos horizontaux, puis il y a un pavage 2x(N-2). On obtient ainsi U(N)=U(N-1)+U(N-2).

Dans le cas 3xN, on applique la même idée, mais c'est un peu plus complexe. Déjà, inutile d'espérer quoi que ce soit si N est impair, étant donné qu'un domino recouvre deux cases. Sinon, on remarque qu'un pavage de largeur N, en commençant de la gauche, c'est soit un pavage 3x2 (3 possibilités) suivi d'un pavage de largeur N-2 ; soit, un pavage 3x4 ne contenant pas de sous-pavage 3x2 (2 possibilités) suivi d'un pavage de largeur N-4 ; soit...

En poursuivant le raisonnement, il vient V(N)=3V(N-2)+2(V(N-4)+V(N-6)+...+V(0)) ce qui se transforme en V(N)=4V(N-2)-V(N-4) (avec V(0)=1 et V(2)=3).

Il vient [latex]V(N)=\frac{3+\sqrt{3}}{6}(2+\sqrt{3})^\frac{N}{2}+\frac{3-\sqrt{3}}{6}(2-\sqrt{3})^\frac{N}{2}[/latex].

https://oeis.org/A001835

Y'a du Fibonacci dans l'air

La première question est toute simple : F(N+1) le problème est en tout point identique à celui de "grenouille et escaliers".

Pour 3 x N , déjà, N doit être pair...
Ensuite, il faut se concentrer sur les remplissages « intermédiaires », c'est à dire les rangs pour les quels le remplissage est complet au rang 2n.

Pour remplir 2 colonnes, il y a 3 possibilités.

Pour en remplir 4 ,
soit on part d'un remplissage de 2, (3x3 possibilités)
Soit on n'a pas de sécantes = > 2 possibilités
On arrive donc à 11 remplissages.

Pour en remplir 6,
Soit on part de 4 => 11 x 3
Soit on part de 2 (sans sécante pour finir) => 3 x 2
Soit on part de 0 (sans sécante)  => 2
On arrive à 41 possibilités …

2 : 3
4 : 11
6 : 41
8 : 153
….

On a donc 2 fois la somme des termes précédents , plus le terme précédent, plus 2.

Cela peut s'apparenter à une sorte de suite de  Fibonacci avec :

f(N) = 4 f(N-2) – f(N-4) en prenant N pair

f(2)=3
f(4)=11
f(6)=41
f(8)=153
f(10)=571
f(12)=2131
f(14)=7953
f(16)=29681
f(18)=110771
f(20)=413403
f(22)=1542841
f(24)=5757961

pour 2 * N je pense que c'est la suite de Fibonacci

Je cherche encore pour le 3 * N

1) Pour le premier cas, si on appelle (U(n)) la suite dont le n-ième terme correspond au nombre de pavage possible pour un rectangle 2*n, on commence par remarquer que U(1)=1, U(2)=2, U(3)=3, U(5)=5, on pense à la suite de Fibonacci.
Pour s'en persuader, on démontre par récurrence qu'un rectangle 2*(n+1) admet U(n)+U(n-1) pavages différents.

En effet, un rectangle 2*(n+1) est soit un rectangle 2*(n) auquel on ajoute un domino vertical, => U(n) pavages possibles, soit un rectangle 2*(n-1) auquel on ajoute deux dominos horizontaux => U(n-1) pavages possibles.

On a donc U(n)=U(n-1)+U(n-2), suite récurrente d'ordre 2, équation caractéristique : x²-x-1=0 dont une des racines est le nombre d'or et l'autre l'opposé de son inverse.

Je préfère ne pas écrire U(n) explicitement, c'est moche sans Latex

Une fois la récurrence trouvée l'OEIS donne une formule pour f(2n-2) :

f(2n-2) = 1/6 (3 (2 - Sqrt[3])^n + Sqrt[3] (2 - Sqrt[3])^n + 3 (2 + Sqrt[3])^n - Sqrt[3] (2 + Sqrt[3])^n)