The subject of enumerating the dissections of a rectangular board m×n into two-celled pieces (dominoes) was briefly discussed in Chessics (1986, vol.1, #28, p.138) where (in different notation) the following recurrence relation was given.
T(m,n) = S(s=1 ... n) of V(m,s)·T(m,n–s)............................................................................(1)
where V(m,s) is the number of m×s dissections without vertical fault lines, and T(m,0) = 1.
Proof of the formula: V(m.s) is the number of ways of dissecting the part of the rectangle before the first fault line (or the whole rectangle if there is no fault line). T(m,n–s) is the number of ways of dissecting the rest of the rectangle, becoming T(m,0) = 1 when there are no fault lines. Multiplying these together gives the number of ways of dissecting the rectangle for each position s of the first fault line. Summing over all possible positions of the first fault line gives the required total.
This method is practical for calculating the totals when m </= 4 since the values of V(m,s) are then easily found by direct calculation, mostly being zero (in particular they are zero when m and s are both odd, since dominoes always cover an even number of cells).
The nonzero cases are illustrated here:
From these diagrams we find the values:
V(1,2) = 1, V(2,1) = 1, V(2,2) = 1, (V,3,2) = 3, V(3,2h) = 2, V(4,1) = 1, V(4,2) = 4, V(4,2h–1) = 2, V(4,2h) = 3,
and using the above summation we can deduce the following recurrence relations to calculate T(2,n), T(3,n) and T(4,n).
T(2,n) = T(2,n–1) + T(2,n–2)...................................................................................................(2)
T(3,2k) = 4·T(3,2k–2) – T(3,2k–4)..........................................................................................(3)
T(4,n) = T(4,n–1) + 5·T(4,n–2) + T(4,n–3) – T(4,n–4).............................................................(4)
Equation (2) was shown by W. L. Patten in American Mathematical Monthly 1961. This recurrence relation is of course the one that generates the Fibonacci sequence. Equation (3) was given by Chris Holt in Mathematical Spectrum (1994/5, volume 27, #3, p.62). Equation (4) was supplied by me in a letter to Mathematical Spectrum (1995/6, volume 28, #2, p.44).
The subject was revisited in The Games and Puzzles Journal (volume 2, #13, 1996, pp204-5) in an article on 'Dominizing the Chessboard', based mainly on new information in a letter to me (24 Jan 1996) from Robin J. Chapman, Department of Mathematics, University of Exeter. He pointed out that the problem, on boards of all sizes, was completely solved as long ago as 1961!
The relevant paper by P. W. Kasteleyn, Shell-Laboratorium, Amsterdam, has the title 'The statistics of dimers on a lattice, I: The number of dimer arrangements on a quadratic lattice', and appeared in the journal Physica (volume 27, 1961, pp1209–25). This reference seems to have escaped the notice of the recreational mathematics fraternity, presumably because it was published in a physics journal and its title makes no mention of dominoes, dissections or chessboards; also it gives no explicit numerical results. The formula for the number T(m,n) of dissections m by n can be expressed in the form:
T(m,n) = P(j=1...m) P(k=1...n) [4·cos2{jp/(m+1)} + 4·cos2{kp/(n+1)}]1/4...............................(5)
[I'm not sure how cos and pi get into the act, but am assured that this is just a bit of mathematical flim-flam and that they cancel out each other's effect (rather like the White Knight's plan to dye his whiskers green and always carry so large a fan that they could not be seen).]
An unpublished paper by James Propp, 'Dimers and dominoes', Massachusetts Institute of Technology, dated 24/ix/1992, based on Kasteleyn, notes that the number of domino tilings of an 8×8 board is 12,988,816 = 3604².
Robin Chapman kindly evaluated the formula for all cases up to 20×20 using the computer algebra system MAPLE. Here are the results up to 72 cells:
| 2×2=2, | 2×3=3, | 2×4=5, | 2×5=8, | 2×6=13, |
| 2×7=21, | 2×8=34, | 2×9=55, | 2×10=89, | 2×11=144, |
| 2×12=233, | 2×13=377, | 2×14=610, | 2×15=987, | 2×16=1597, |
| 2×17=2584, | 2×18=4181, | 2×19=6765, | 2×20=10946, | 2×21=17711, |
| 2×22=28657, | 2×23=46368, | 2×24=75025, | 2×25=121393, | 2×26=196418, |
| 2×27=317811, | 2×28=514229, | 2×29=832040, | 2×30=1346269, | 2×31=2178309, |
| 2×32=3524578, | 2×33=5702887, | 2×34=9227465, | 2×35=14930352, | 2×36=24157817. |
| 3×4=11, | 3×6=41, | 3×8=153, | 3×10=571, | 3×12=2131, |
| 3×14=7953, | 3×16=29681, | 3×18=110771, | 3×20=413403, | 3×22=1542841, |
| 3×24=5757961. | ||||
| 4×4=36, | 4×5=95, | 4×6=281, | 4×7=781, | 4×8=2245, |
| 4×9=6336, | 4×10=18061, | 4×11=51205, | 4×12=145601, | 4×13=413351, |
| 4×14=1174500, | 4×15=3335651, | 4×16=9475901, | 4×17=26915305, | 4×18=76455961. |
| 5×6=1183, | 5×8=14824, | 5×10=185921, | 5×12=2332097, | 5×14=29253160. |
| 6×6=6728, | 6×7=31529, | 6×8=167089, | 6×9=817991, | |
| 6×10=4213133, | 6×11=21001799, | 6×12=106912793. | ||
| 7×8=1292697, | 7×10=53175517. | |||
| 8×8=12988816. | 8×9=108435745 | |||
Propp also notes that the total is a square on square boards of side 4k, and twice a square on square boards of side 4k+2.
For 6×6 we have: 6728 = 2×58². The 10×10 gives: 258584046368 = 2×359572²
and 12×12 gives 53060477521960000 = 230348600²
Chapman notes that Kasteleyn's formula also gives the number of tilings of an m×n rectangle with a given number of horizontal tiles. He has computed these for an 8×8 square. The results are listed below. If A(n) is the number of tilings with n horizontal tiles (n even) then A(n) = A(32–n).
| A(0) = A(32) = 1, | A(2) = A(30) = 70, | A(4) = A(28) = 1785, |
| A(6) = A(26) = 21656, | A(8) = A(24) = 144092, | A(10) = A(22) = 580620, |
| A(12) = A(20) = 1511368, | A(14) = A(18) = 2644858, | A(16) = 3179916. |
The problem remains of how to calculate V(m,n) for larger values of m, and of determining the number F(m,n) of fault-free dissections (with neither vertical nor horizontal fault lines).
Problem 150 in Chessics (volume 2, #23, 1985) was: Dissect a chessboard into dominoes so that the number of 2×2s (dominoes with long sides matching) is minimised. The unique solution (apart from rotation) is diagrammed here.
This is a case of a general result on dominoes that I found: Every domino dissection of a rectangle must contain at least one 2×2 inset, i.e. two dominoes side by side; and a domino dissection that has exactly one 2×2 inset must be either square (2k by 2k) or near-square (2k by 2k–1), with the 2×2 centrally placed and the other dominoes in 'rings' around it. To prove the first part of this, start at the a1 corner and try to construct a dissection without a 2×2. We are forced to place dominoes in a 'herringbone' pattern diagonally from the corner, and this forces the formation of a 2×2 where it meets the opposite edge.