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.

I have found this formula in internet and I would like to
know is there a way to use it for solving this problem?

There is a solution of this problem which doesn't use this formula. But it uses something related to the problem name :)

Don't you mean Aztec Diamond? And how is it connected then? =)

Your guess is correct. The connection, however, is quite unobvious.

The answer can be calculated as number of perfect matching in corresponding planar graph using Kasteleyn theorem. But it uses determinant of matrix (nm/2)x(mn/2) (symmetric and with zeroes) and complex numbers, so now i don't know, can or cannot it to be applied to this problem.

Hm, maybe it gives the formula posted by Al.Cash :-))))

Edited by author 21.06.2009 20:59

Yes, it gives exactly this formula =) But you can't use it due to precision reasons. We need integral-numbers formula...

Very interesting from theoretical and practical point of view to use Java.BigDecimal with 1000-10000 digits
and catch right answer.

Connection with Aztec Diamond! Something interest, but only for (2n)x(2n) squares:

Consider the 2n-by-2n matrix View the MathML source with mi,j=1 for i,j satisfying |2i−2n−1|+|2j−2n−1|less-than-or-equals, slant2n and mi,j=0 for all other i,j, consisting of a central diamond of 1's surrounded by 0's. When ngreater-or-equal, slanted4, the λ-determinant of the matrix M (as introduced by Robbins and Rumsey [Adv. Math. 62 (1986) 169–184]) is not well defined. However, if we replace the 0's by t's, we get a matrix whose λ-determinant is well defined and is a polynomial in λ and t. The limit of this polynomial as t→0 is a polynomial in λ whose value at λ=1 is the number of domino-tilings of a 2n-by-2n square.

Nice problem! Finally got accepted after trying for 2 hours.

best,

Josh Bao


Edited by author 25.06.2009 12:34

2zbao: I think this gave us no useful information!

Edited by author 25.06.2009 15:27

Your submissions looks like some binary search or other cheatings... Why you get different wrongs many times for tests 29,33,34,36,38,40,42?

P.S. Sorry, if I am wrong.

Edited by author 25.06.2009 19:39

Wolfram Mathematica 8 allows you to use this formula with trigonometry.
He is a genius! It's a wonderful package!!! :)

Didn't read the whole thread, but it's DP problem
http://e-maxx.ru/algo/profile_dynamics