200 geometry/tiling/count.1x2.p
Description
This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.
200 geometry/tiling/count.1x2.p
Count the ways to tile an MxN rectangle with 1x2 dominos.
geometry/tiling/count.1x2.s
The number of ways to tile an MxN rectangle with 1x2 dominos is
2^(M*N/2) times the product of
{ cos^2(m*pi/(M+1)) + cos^2(n*pi/(N+1)) } ^ (1/4)
over all m,n in the range 0<m<M+1, 0<n<N+1.
[Exercises:
0) Why does this work for M*N odd?
1) When M<3 the count can be determined directly;
check that it agrees with the above formula.
2) Prove directly this formula gives an integer for all M,N, and
further show that if M=N it is a perfect square when 4|N and
twice a square otherwise.
]
Where does this come from? For starters note that, with the usual checker-
board coloring, each domino must cover one light and one dark square. Assume
that M*N is even (but as it happens our formula will work also when both
M,N are odd --- see exercise 0 above). Form a square matrix of size
M*N/2 whose rows and columns are indexed by the light and dark squares,
and whose (j,k) entry is 1 if the j-th light and k-th dark square are
adjacent and zero otherwise. There are now three key ideas:
First, the number of tilings is the number of ways to match each light
square with an adjacent dark square; thus it is the _permanent_ of our
matrix (recall that the permanent of a rxr matrix is a sum of the same
r! terms that occur in its determinant, except without the usual +1/-1
sign factors).
Second, that by modifying this matrix slightly we can convert the
permanent to a determinant; this is nice because determinants are generally
much easier to evaluate than permanents. One way to do this is to replace
all the 1's that correspond to vertical adjacency to i's, and multiply the
whole thing by a suitable power of i (which will disappear when we raise
it to a fourth power).
[Exercise 3: check that this transformation actually works as advertised!]
Third, that we can diagonalize the resulting matrix A --- or, more
conveniently, the square matrix of A' order M*N whose order-(M*N/2)
blocks are 0,A;A-transpose,0 , whence det(A') = +-(det(A))^2. Then
the rows and columns of A' are indexed by squares of either hue on our
generalized checkerboard, and its entries are 1 for horizontally adjacent
squares, i for vertically adjacent ones, and 0 for nonadjacent (including
coincident) squares. This A' can be diagonalized by using the trigonometric
basis of vectors v_ab (a,b as in the formula above) whose coordinate at
the (m,n)-th square is sin(a*m*pi/(M+1)) * sin(b*n*pi/(N+1)).
Exercise 4: verify that these are in fact orthogonal eigenvectors of A',
determine their eigenvalues, and complete the proof of the above formula.
(None of this is new, but it does not seem to be well-known: indeed
each of the above steps seems to have been discovered independently
several times, and I'm not sure whom to credit with the first discovery
of this particular application of the method. For different approaches
to exactly solvable problems involving the enumeration of domino tilings,
see the two papers of G.Kuperberg, Larsen, Propp and myself on
"Alternating-Sign Matrices and Domino Tilings" in the first volume of
the _Journal of Algebraic Combinatorics_.)
--Noam D. Elkies (elkies@zariski.harvard.edu)
Dept. of Mathematics, Harvard University
geometry/tiling/rational.sides.p
A rectangular region R is divided into rectangular areas. Show that if
each of the rectangles in the region has at least one side with
rational length then the same can be said of R.
geometry/tiling/rational.sides.s
"Fourteen proofs of a result about tiling a rectangle" (Stan Wagon)
_The American Mathematical Monthly_, Aug-Sep 1987, Vol 94 #7. There
was also a fifteenth proof published a few issues later, attributed to
a (University of Kentucky?) student.
geometry/tiling/rectangles.with.squares.p
Given two sorts of squares, (axa) and (bxb), what rectangles can be tiled?
geometry/tiling/rectangles.with.squares.s
A rectangle can be tiled with (axa) and (bxb) squares, iff
(i) gcd(a,b)=1 , and any of the following hold:
either: both sides of the rectangle are multiples of a;
or: both sides of the rectangle are multiples of b;
or: one side is a multiple of (ab), and the other is any length EXCEPT
one of a finite number of "bad" lengths: those numbers which are
NOT positive integer combinations of a & b. { By Sylvester's theorem
there are (a-1)(b-1)/2 of these, the largest being (a-1)(b-1)-1. }
(ii) gcd(a,b) = d .
Then merely apply (i) to the problem with a,b replaced
by a/d, b/d and the rectangle lengths also divided by d.
i.e. all cells must appear in (dxd) subsquares.
------
PROOF
It is clear that (ii) follows from (i), and that simple constructions give
the "if" part of (i). For the "only if" part, we prove that...
(S) If one side of the rectangle is not divisible by a, and the other is
not divisible by b, then the tiling is impossible.
The results in (i) follow immediately from (S).
To prove (S): ( Chakraborty-Hoey style ).
~~~~~~~~~~~~~~~~
Let the width of the rectangle be a NON-(a-multiple). Then the number of
bxb squares starting (i.e. top edge) at row 1 must be a NON-a-multiple.
Thus the number of bxb starting at row 2 must BE an a-multiple. Similarly
for the number starting at rows 3,4,...,b . Then the number starting at
row (b+1) must be a NON-a-multiple again.
Similarly the number starting at rows (2b+1), (3b+1), (4b+1),... must all be
non-a-multiples. So if the number of rows is NOT a multiple of b, (call it
bx+r), then row (bx+1) must have a NON-a-multiple of bxb squares starting
there, i.e. at least one, and there is no room left to squeeze it in. [QED]
----
A Rickard-style proof of (S) is ..BBB....BBWWW...WBBB....BBWWW...W(..etc) ~~~~~~~ also possible, by ..BBB....BBWWW...WBBB....BBWWW...W coloring the rectangle in ..BBB....BBWWW...WBBB....BBWWW...W vertical strips as shown here: <- a ->< b-a ><- a ->< b-a >
Every square tile covers an a-multiple of black squares. But if the width
is a NON-b-multiple, and the number of rows is a NON-a-multiple, then there
are a NON-a-multiple of black squares in total. [QED]
(Note: the coloring must have 1 column of blacks on the right, and any
==== spare columns of whites on the left.)
===================
Bill Taylor. wft@math.canterbury.ac.nz
>A Rickard-style proof of (S) is ..BBB....BBWWW...WBBB....BBWWW...W(..etc) > ~~~~~~~ also possible, by ..BBB....BBWWW...WBBB....BBWWW...W >coloring the rectangle in ..BBB....BBWWW...WBBB....BBWWW...W >vertical strips as shown here: <- a ->< b-a ><- a ->< b-a > >
>Every square tile covers an a-multiple of black squares. But if the width
>is a NON-b-multiple, and the number of rows is a NON-a-multiple, then there
>are a NON-a-multiple of black squares in total. [QED]
>
>(Note: the coloring must have 1 column of blacks on the right, and any
> ==== spare columns of whites on the left.)
This statement of how to position the colouring isn't good enough, I'm
afraid. Take a=4, b=7 and consider e.g. a 19x10 rectangle. Coloured your
way, you get:
BWWWBBBBWWWBBBBWWWB
BWWWBBBBWWWBBBBWWWB
:::::::::::::::::::
BWWWBBBBWWWBBBBWWWB
BWWWBBBBWWWBBBBWWWB
The result has 10*10=100 black squares in it, which *is* a multiple of a=4,
despite the fact that 19 is not a multiple of 7 and 10 is not a multiple of
4.
Of course, there is an alternative offset for the pattern that does give you
the result you want:
WWBBBBWWWBBBBWWWBBB
WWBBBBWWWBBBBWWWBBB
:::::::::::::::::::
WWBBBBWWWBBBBWWWBBB
WWBBBBWWWBBBBWWWBBB
To show this happens in general: because the width of the rectangle is a
non-multiple of b, it is possible to position it on the pattern so that the
leftmost column in the rectangle is white and the column just right of the
right edge of the rectangle is black. Suppose N columns are black with this
positioning. Then the rectangle contains N*H black cells, where H is the
height of the rectangle.
If we then shift the rectangle right by one, the number of black columns
increases by 1 and it contains (N+1)*H black cells. The difference between
these two numbers of black cells is H, which is not a multiple of a.
Therefore N*H and (N+1)*H cannot both be multiples of a, and so one of these
two positionings of the pattern will suit your purposes.
David Seal
dseal@armltd.co.uk
Continue to:
My Books
