Number of domino tilings Write a program or function that given positive n and m calculates the number of valid distinct domino tilings you can fit in a n by m rectangle. This is sequence A099390 in the Online Encyclopedia of Integer Sequences. You may take input in as function argument(s), CLA or on stdin, in any reasonable format. You must return or print a single integer as output.

Each tiling must not leave any gaps, and every distinct tiling is counted, including rotations, reflections, etc. For example, the tilings for 2x3 are:

|--    |||    --| 
|--    |||    --|


Example inputs/outputs:

1,  9 -&gt; 0
2,  2 -&gt; 2
2,  3 -&gt; 3
4,  4 -&gt; 36
4,  6 -&gt; 281
6,  6 -&gt; 6728
7, 10 -&gt; 53175517


Your program should theoretically work for any n and m, but if your program requires too much memory or your data type overflows it's excused. Your program must work correctly for any n, m &lt;= 8 however.



Shortest code in  bytes wins.
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 &lt;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)&gt;0,1);
        %find the row where to place:
        r=find(A(:,c)&gt;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(:)&lt;0)
            v=0;break;
        end
    end
    %if valid, count it as valid
    if v &amp;&amp; ~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)&gt;0,1);r=find(A(:,c)&gt;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(:)&lt;0);v=0;break;end;end;if v &amp;&amp; ~norm(A(:));C=C+1;end;end