Number of domino tilings

Matlab, 292

I am sure this can be shortened a lot just by porting it into another language.

The basic idea is bruteforcing: I came up with kind of an enumeration of all ways how to place m*n/2 domino bricks on an m*n board. But this enumeration also includes many invalid tilings (bricks that overlap or go outside of the board.) So the program constructs all those tilings, and only counts the valid ones. The runtime complexity is about O(2^(m*n/2) * m*n). Memory is not a problem for the 8x8 as it only needs O(m*n) memory. But the time needed for 8x8 is about 20 days.

Here the fully commented version that explains what is going on.

PS: If anyone knows how to make the Matlab syntax highlighting work, please include the corresponding tag in this answer!

function C=f(m,n)
d = ceil(m*n/2);%number of dominoes
%enumeration: %the nth bit in the enumeration says whether the nth 
% domino pice is upright or not. we enumerate like this:
% firt piece goes top left:
% next piece goes to the left most column that has an empty spot, in the
% top most empty spot of that column
C=0;%counter of all valid tilings
for e=0:2^d-1 %go throu all enumerations
    %check whether each enumeration is valid
    A = ones(m,n);
    %empty spots are filled with 1
    %filled spots are 0 (or if overlapping <0) 
    v=1;%flag for the validity. hte grid is assumed to be valid until proven otherwise
    for i=1:d %go throu all pieces, place them in A
        %find the column where to place:
        c=find(sum(A)>0,1);
        %find the row where to place:
        r=find(A(:,c)>0,1);
        %find direction of piece:
        b=de2bi(e,d);
        if b(i)
            x=0;y=1;
        else
            x=1;y=0;
        end
        %fill in the piece:
        try
            A(r:r+y,c:c+x)=A(r:r+y,c:c+x)-1;
        catch z
            v=0;break;
        end
        %check whether A has no overlapping pieces
        if any(A(:)<0)
            v=0;break;
        end
    end
    %if valid, count it as valid
    if v && ~norm(A(:))
        disp(A)
        C=C+1;
    end
end

Here the fully golfed one:

function C=f(m,n);m=4;n=6;d=ceil(m*n/2);C=0;for e=0:2^d-1;A=ones(m,n);v=1;for i=1:d;c=find(sum(A)>0,1);r=find(A(:,c)>0,1);b=de2bi(e,d);if b(i);x=0;y=1;else;x=1;y=0;end;try;A(r:r+y,c:c+x)=A(r:r+y,c:c+x)-1;catch z;v=0;break;end;if any(A(:)<0);v=0;break;end;end;if v && ~norm(A(:));C=C+1;end;end

Pyth, 30 29 bytes

L?bsmy-tb]dfq1.a-VThbb1y*FUMQ

Try it online: Demonstration / Test Suite

All example inputs run in the online compiler. The last one takes a few seconds though.

Explanation:

In my code I'll define a recursive function y. The function y takes a list of 2D-coordinates and returns the number of different domino tilings using these coordinates. E.g. y([[0,0], [0,1]]) = 1 (one horizontal domino), y([[0,0], [1,1]]) = 0 (coordinates are not adjacent) and y([[0,0], [0,1], [1,0], [1,1]]) = 2 (either two horizontal or two vertical dominoes). After defining the function I'll call it with all coordinates [x,y] with x in [0, 1, m-1], y in [0, 1, n-1].

How does the recursive function work? It's quite simple. If the list of coords is empty, there is exactly one valid tiling and y returns 1.

Otherwise I take the first coordinate in the list b[0], and search the remaining coordinates for a neighbors. If there is no neighbor to b[0], then there is no tiling possible, therefore I return 0. If there is one or more neighbors, then the number of tilings is (the number of tilings where I connect b[0] with the first neighbor via a domina, plus the number of tilings where I connect b[0] with the second neighbor, plus ...) So I call the function recursively for each neighbor with the shortened list (by removing the two coords b[0] and neighbor). Afterwards I sum up all results and return them.

Because of the order of the coords there are always only two neighbors possible, the one on the right side and the one below. But my algorithm doesn't care about that.

                          UMQ  convert the input numbers into ranges
                        *F     Cartesian product (coords of each square)
L                              define a function y(b):
 ?b                              if len(b) > 0:
           f         b             filter b for squares T, which satisfy:
              .a-VThb                Euclidean distance between T and b[0]
            q1                       is equal to 1 (direct neighbors)
    m                              map each neighbor d to:
      -tb]d                          remove d from b[1]
     y                               and call recursively y with the rest
   s                               sum all those values and return them
                                 else:
                      1            return 1 (valid domino tiling found)
                       y*FUMQ  Call y with all coords and print the result  

APL (Dyalog Extended), 26 bytes

{⍎0⍕√|×/⌾/¨2×2○○,⍵}⍳÷∘⊂1∘+

Try it online!

A monadic tacit function that takes a 2-element vector n m as its sole argument.

A port of fireflame241's Python answer, and in turn an implementation of the formula:

$$ T(n,k)^2 = \left| \prod^n_{a=1}{\prod^k_{b=1}{2 \cos \frac{a\pi}{n+1}+2i \cos \frac{b\pi}{k+1}}} \right| $$

Turns out that the results before rounding are pretty accurate (under 1e-14 relative error for the test cases), except when the result is expected to be zero.

How it works

{⍎0⍕√|×/⌾/¨2×2○○,⍵}⍳÷∘⊂1∘+  ⍝ input←n m
                   ⍳        ⍝ 2D array of all pairs of 1..n , 1..m
                    ÷∘⊂     ⍝ divided by wrapped pair of
                       1∘+  ⍝ (n+1)(m+1)
{               ,⍵}  ⍝ Ravel the 2D array, giving a vector of pairs
           2×2○○     ⍝ 2×cos(pi × each number)
        ⌾/¨          ⍝ Convert each pair x,y to x + yi
      ×/  ⍝ Product of all complex numbers
     |    ⍝ Abs
    √     ⍝ Sqrt
 ⍎0⍕      ⍝ Round the number by converting to string with
          ⍝ zero digits under decimal point, then evaling it back