Pavages de dominos - solution
Combien de façons de paver un rectangle de m×n avec des dominos ?2×n
Considérons le cas le plus simple 1 domino dans un rectangle de 2×1, bien sûr d'une seule façon. Le cas 2×2 donne tout aussi facilement f2 = 2De façon générale soit fn = le nombre de pavages du rectangle 2×n
Ajoutons un domino au bout de 2×n, ou deux dominos en long au bout de 2×(n-1) donne tous les pavages de 2×(n+1) soit
| fn+1 = fn + fn-1 |
(on peut aussi partir de f0 = 1 = une seule façon de ne mettre aucun domino dans un rectangle de 2×0)
3×2n
Bien sûr 3×(2n+1) est impossible, on n'en parle même pas...
Considérons le cas le plus simple de 3 dominos dans un rectangle de 3×2
Il y a (voir ci-dessus) f3 = 3 solutions :
Ajoutons un deuxième bloc de 3×2.
Il y a donc 3×3 façons de placer les dominos dans ces deux blocs indépendamment.
Mais il y a aussi deux façons de placer les dominos dans 3×4 sans former aucun bloc vertical de 3×2 :
Pour un tel bloc de 3×2k sans blocs 3×2 internes, il n'y a que deux possibilités,
obtenues en dupliquant les dominos bleus du cas 3×4.
Chacune de ces possiblités donne donc lieu à ai×2 possibilités
soit :
| an+1 = 3×an + 2×∑i<nai |
Calculons an+1 - an = 3×an + 2×∑i<nai - 3×an-1 - 2×∑i<n-1ai = 3×an - an-1 + 2×∑i<n-1ai - 2×∑i<n-1ai = 3×an - an-1 et finalement :
| an+1 = 4×an - an-1 |
a2 = 4×3 - 1 = 11
a3 = 4×11 - 3 = 41
a4 = 4×41 - 11 = 153
a5 = 4×153 - 41 = 571
...
C'est à dire la suite A001835 de l'OEIS.
Pour obtenir une formule générale, on cherche des solutions de la forme
an = Aun + Bvn
u et v sont solutions de t² = 4t - 1 soit u,v = 2 ± √3
Les conditions initiales a0 = 1 et a1 = 3 donnent A et B et la formule :
| an = (3 + √3)(2 + √3)n/6 + (3 - √3)(2 - √3)n/6 |
Comme (3 - √3)(2 - √3)n/6 < 1, ceci peut aussi s'écrire :
| an = Sup[(3 + √3)(2 + √3)n/6]
avec Sup[x] = plus petit entier ≥ x |
Puisque (2 + 1×√3)(2 - 1×√3) = 1,
on peut dire que 2 et 1 sont les solutions fondamentales de l'équation de Pell
x² - 3y² = 1
et les an ressemblent donc à des solutions de l'équation de Pell généralisée
x² - 3y² = K
et plus précisément an = y
On connait deux solutions particulières y = 1 et 3 soit
u² - 3 = K, v² - 27 = K soit v² - u² = 24 dont les seules solutions sont
u = 5, v = 7 et K = 22 et u = 1, v = 5, K = -2.
L'équation x² - 3y² = - 2 possède une seule solution fondamentale x = 1, y = 1 conduisant aux an ci-dessus.
L'équation x² - 3y² = 22 possède les deux solutions fondamentales (5, ±1) soit les deux familles de solutions
y = 1, 7, 27, ...
et y = -1, 3, 13, ...
dont seules quelques solutions font partie des an.
Les an sont les solutions de :
| 3y² - 2 est un carré |
Ceci peut d'ailleurs se vérifier directement en développant l'expression de 3a²n - 2 = [ (√3 + 1)(2 + √3)n/2 - (√3 - 1)(2 - √3)n/2 ] ²
Au delà...
Le cas général est beaucoup plus compliqué. Les récurrences sont de degré > 2. Citons sans démonstrations :4×n
T(1) = 1, T(2) = 5, T(3) = 11, T(4) = 36, etT(n) = T(n-1) + 5T(n-2) + T(n-3) - T(n-4).
OEIS A005178
5×n
Bien sûr n impair est impossible soit T(2k+1)=0T(1) = 0, T(2) = 8, T(3) = 0, T(4) = 95, T(5) = 0, T(6) = 1183, T(7) = 0, T(8) = 14824, et
T(n) = 15T(n-2) - 32T(n-4) + 15T(n-6) - T(n-8).
OEIS A003775
6×n
T(1) = 1, T(2) = 13, T(3) = 41, T(4) = 281, T(5) = 1183, T(6) = 6728, T(7) = 31529, T(8) = 167089, T(9) = 817991, T(10) = 4213133, T(11) = 21001799, T(12) = 106912793, T(13) = 536948224, T(14) = 2720246633, etT(n) = 40T(n-2) - 416T(n-4) + 1224T(n-6) - 1224T(n-8) + 416T(n-10) - 40T(n-12) + T(n-14).
OEIS A028468
7×n
T(1) = 0, T(2) = 21, T(3) = 0, T(4) = 781, T(5) = 0, T(6) = 31529, T(7) = 0, T(8) = 1292697, T(9) = 0, T(10) = 53175517, T(11) = 0, T(12) = 2188978117, T(13) = 0, T(14) = 90124167441, T(15) = 0, T(16) = 3710708201969, etT(n) = 56T(n-2) - 672T(n-4) + 2632T(n-6) - 4094T(n-8) + 2632T(n-10) - 672T(n-12) +
56T(n-14) - T(n-16).
OEIS A28469
En particulier le pavage d'un rectangle de 7×8 avec les 28 dominos = 1292697,
et le nombre de positions différentes du jeu correspondant :
1292697 × 28! × 221,
le 221 étant les retournement des dominos autres que les doubles.
8×n
T(1) = 1, T(2) = 34, T(3) = 153, T(4) = 2245, T(5) = 14824, T(6) = 167089, T(7) = 1292697, T(8) = 12988816, T(9) = 108435745, T(10) = 1031151241, T(11) = 8940739824, T(12) = 82741005829, T(13) = 731164253833, T(14) = 6675498237130, T(15) = 59554200469113, T(16) = 540061286536921, T(17) = 4841110033666048, T(18) = 43752732573098281, T(19) = 393139145126822985, T(20) = 3547073578562247994, T(21) = 31910388243436817641, T(22) = 287665106926232833093, T(23) = 2589464895903294456096, T(24) = 23333526083922816720025, T(25) = 210103825878043857266833, T(26) = 1892830605678515060701072, T(27) = 17046328120997609883612969, T(28) = 153554399246902845860302369, T(29) = 1382974514097522648618420280, T(30) = 12457255314954679645007780869, T(31) = 112199448394764215277422176953, T(32) = 1010618564986361239515088848178, etT(n) = 153T(n-2) - 7480T(n-4) + 151623T(n-6) - 1552087T(n-8) + 8933976T(n-10) - 30536233T(n-12) + 63544113T(n-14) - 81114784T(n-16) + 63544113T(n-18) - 30536233T(n-20) + 8933976T(n-22) - 1552087T(n-24) + 151623T(n-26) - 7480T(n-28) + 153T(n-30) - T(n-32).
OEIS A028470
En particulier le pavage d'un échiquier 8×8 = 12988816
Plus généralement on a :
2n×2n
a(n) = 2n × B(n)2, avec B(n) = n+1 (mod 32) si n pair, et B(n) = n (mod 32) si n impair.OEIS A004003
1, 2, 36, 6728, 12988816, 258584046368, ...
m×n
OEIS A099390Si m,n pairs : T(m,n) = ∏j=1..m/2 ∏k=1..n/2 ( 4cos²(jπ/(m+1)) + 4cos²(kπ/(n+1)) ).
Et en résumé pour m,n < 8 :
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 2 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 |
| 3 | 0 | 3 | 0 | 11 | 0 | 41 | 0 | 153 |
| 4 | 1 | 5 | 11 | 36 | 95 | 281 | 781 | 2245 |
| 5 | 0 | 8 | 0 | 95 | 0 | 1183 | 0 | 14824 |
| 6 | 1 | 13 | 41 | 281 | 1183 | 6728 | 31529 | 167089 |
| 7 | 0 | 21 | 0 | 781 | 0 | 31529 | 0 | 1292697 |
| 8 | 1 | 34 | 153 | 2245 | 14824 | 167089 | 1292697 | 12988816 |
