Number of domino tilings

Question

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 -> 0
2,  2 -> 2
2,  3 -> 3
4,  4 -> 36
4,  6 -> 281
6,  6 -> 6728
7, 10 -> 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 <= 8 however.

---

Shortest code in bytes wins.

Answer 1

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  

Answer 2

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

Answer 3

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

Answer 4

C89, 230 bytes

f(n,m,b)int*b;{int s,i;s=i=0;
while(b[i])if(++i==n*m)return 1;
if(i/n<m-1){b[i]=b[i+n]=1;s+=f(n,m,b);b[i]=b[i+n]=0;}
if(i%n<n-1&&!(b[i]|b[i+1])){b[i]=b[i+1]=1;s+=f(n,m,b);b[i]=b[i+1]=0;}
return s;}
g(n,m){int b[99]={};return f(n,m,b);}

For readability I handwrapped this answer - all newlines can safely be removed to get to 230 bytes.

Defines a function int g(int n, int m) that returns the number of tilings. It uses a helper function f that iterates over all valid tilings by placing one domino, recursing, and then removing the domino on a shared board.

Answer 5

Python 3.8 (pre-release), 133 121 115 bytes

lambda m,n:round(abs(prod(2*cos((i//n+1)*pi/-~m)+2j*cos((i%n+1)*pi/-~n)for i in range(m*n)))**.5)
from math import*

Try it online!

(Python 3.8 adds math.prod for product)

-12 bytes thanks to @Bubbler

Implements the following formula (from OEIS A187596):

T(n,k)^2 = absolute value of Prod(Prod( 2*cos(a*Pi/(n+1)) + 2*i*cos(b*Pi/(k+1)), a = 1..n), b = 1..k), where i = sqrt(-1)

Since this multiplies (floating-point) complex numbers together, this loses precision for sufficiently large n, which is permitted by the challenge rules (effectively, data type overflows).

Answer 6

JavaScript (ES7),  149 ... 145  142 bytes

Expects (n)(m).

m=>g=(n,a=[...Array(N=2**m-1).fill(0),1])=>n?g(n-1,a.map((_,i)=>a.reduce((p,c,k)=>p+c*!(h=(x,y)=>y&~x|(x?h(x>>1,x&!y):~k&~i&N))(k&i),0))):a[N]

Try it online!

How?

I've described the algorithm in my Python answer to Domino Recurrence Generator.

The main difference is that it's shorter in JS to combine both state compatibility tests into the following recursive function than to use a regular expression.

( h = (x, y) =>
    y & ~x | (
      x ?
        h(x >> 1, x & !y)
      :
        ~k & ~i & N
    )
)(k & i)

Answer 7

Python 243

I opted for a brute force approach:

• generate m*n/2 directions;
• try and fit the domino on the m*n board.

If they all fit and no spaces are left we have a valid entry.

Here is the code:

import itertools as t
m,n=input()
c,u=0,m*n
for a in t.product([0,1],repeat=u/2):
 l,k,r,h=[' ',]*u,0,'-|',[1,m]
 for t in a:
  l[k]=r[t]
  k+=h[t]   
  if k%m<m and k/m<n and l[k]==' ':l[k]=r[t]
  k=''.join(l).find(' ',1)
 if k<0:c+=1
print c