Wikipedia:Reference desk archive/Mathematics/2006 August 8

From Wikipedia, the free encyclopedia

Humanities Science Mathematics Computing/IT Language Miscellaneous Archives

The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions at one of the pages linked to above.

< August 7 Mathematics desk archive August 9 >

[edit] Domino tiling

Dominos are black tiles of size 2 by 1. I know that the number of ways to tile an area of size 2 by n with these dominos is the (n+1)th Fibonnacci Number (depending on the starting point) and this can be proven quite easily using recursions. However, how many different ways are there to tile an m by n rectangle with dominoes? --AMorris (talk)●(contribs) 08:08, 8 August 2006 (UTC)

For every fixed value of m you can give a system of recurrence relations for varying n, just like for the 2 by n case (but increasingly more complicated as m increases), and use that to give a closed formula depending on n. As far as I know, no-one has succeeded in doing something similar with both m and n as parameters. --Lambiam^Talk 09:38, 8 August 2006 (UTC)

This is called the "dimer problem" (which I can't find in Wikipedia). There is no simple closed solution, but Kasteleyn found a determinant formula that leads to a pretty double product formula. This survey of the dimer problem has the formula at the start of section 5. McKay 10:42, 8 August 2006 (UTC)

However, the pretty double product formula that McKay referenced only applies to cases where M and N are even. StevoX 12:55, 8 August 2006 (UTC)

Why do you say that? Experimentally it seems to work for all sizes. McKay 03:26, 9 August 2006 (UTC)

Oops- I misread the formula in this paper/lecture by Richard P. Stanley and Federico Ardila to only work with even numbers due to the statement that it solves for tilings of 2M x 2N. I wrongly assumed that M and N had to be integers. --StevoX 04:15, 9 August 2006 (UTC)

I read that part of the paper but i can't see how it would work for a rectangle of dimensions 3 by 4, because in this case m = 1.5 and how do u take the product from k=1 to 1.5? And if both 2m and 2n are odd, does the answer come out as zero? Otherwise it's a pretty damn interesting formula especially the fact that it yields an integer value with all those cosines. Thanks. --AMorris (talk)●(contribs) 06:49, 9 August 2006 (UTC)

The formula given by Stanley-Ardila is less general. Look at the version I referenced--it works for all sizes and even correctly gives the value 0 if both dimensions are odd. McKay 11:58, 9 August 2006 (UTC)

The OP will no doubt be interested in the work of Jim Propp and others on Aztec diamonds and other topics connected with random domino tilings; see this page. Propp is well known as coinventor with David Wilson of an algorithm for perfect sampling, e.g. for a simulation of a near-critical Ising model. Hmm.. lotta red links there, which seems strange since the Propp-Wilson algorithm is more or less the centerpiece of a recent undergraduate textbook in the highly regarded London Mathematical Society student text series (volume 52):

• Häggström, Olle (2002). Finite Markov Chains and Algorithmic Applications. Cambridge: Cambridge University Press. ISBN 0-521-89001-2..

I'd agree with the implied suggestion that the dimer problem deserves a Wikipedia article. (In the interests of ridiculously complete disclosure: I know Jim Propp, but then the theory of tiling is still a pretty small world, so this is hardly surprising!)---CH 02:20, 12 August 2006 (UTC)