Counting polydominoes

Question

Background

A polyomino of size \$n\$ is a contiguous shape made from joining \$n\$ unit squares side by side. A domino is a size-2 polyomino.

A polydomino of size \2ドルn\$ is defined as a polyomino of size \2ドルn\$ which can be tiled with \$n\$ dominoes.

The following are some examples of polydominoes for \$n=3\$ (hexominoes).

. O O | . O . . | O O O . | O O O O O O
O O . | O O O O | O . O O |
O O . | O . . . | |

The following are some hexominoes that are not polydominoes.

. O . | O . . . | O . O .
O O O | O O O O | O O O O
O O . | O . . . |

Challenge

Given a positive integer \$n\$, count the number of distinct polydominoes of size \2ドルn\$. Rotations and reflections are considered as the same shape. Different tilings of the same shape does not count either. You may take the value of \2ドルn\$ as input instead (you may assume the input is always even in this case).

The following shape has two ways to tile with dominoes, but it is counted only once just like other hexominoes.

. O O
O O .
O O .

The sequence is OEIS 056786.

Test cases

The following are the expected results for \$n=1 \cdots 9\$.

1, 4, 23, 211, 2227, 25824, 310242, 3818983, 47752136

• tsh: What are dominoes?
• Bubbler: @tsh A domino is a size-2 polyomino (two unit squares attached side by side).

Answer 1

Ruby, (削除) 266 250 (削除ここまで) 242 bytes

->n,*z{j=(h=1,m=1i,-1,*r=[-m,0]).product h;(r.map{|c|j.map{|v,w|k=r+[v+=c,v+w];k|k==k&&(w=j.map{|y,q|(x=k.map{|v|y*[v,v.conj][q*q]}).map{|g|g-x.map(&:real).min-m*x.map(&:imag).min}.sort_by &:rect})-z==w&&z<<w[0]}};r,*z=z)until r[-n];z.size+1}

Try it online!

Not particularly original, I just recycled my solution to a similar problem, and changed some small details:

• start with the basic domino (instead of single tile)
• add 2 tiles on each step (instead of one)
• check for reflection by using the complex conjugate (instead of only rotation using powers of i)
• (削除) stop when reaching size 2n (instead of n) (削除ここまで) -> Accept 2n as input

How it works:

See the linked post for the full explanation. Basically, use complex numbers to make it easier.

Performance:

43 seconds for n=5 (size 10) on TIO

Thanks Dingus for saving some bytes, the function is a mess and could probably be much shorter anyway if implemented properly.

Answer 2

JavaScript (ES10), 343 bytes

Expects \2ドルn\$ as input.

n=>(c=0,g=(m,k)=>k<n?m.map((r,y)=>m.map((Y,x,[...m])=>(h=(p,R=m[Y=y+!p],P=p-~p<<x)=>(p?x:y)>n-2|(q=r|R)&P|k*!(q&P/2+P*2|(m[y-1]|m[Y+1])&P)?0:m[g(m,k+2,m[y]|=P,m[Y]|=P),m[y]=r,Y]=R)(0)|h(1))):(F=i=>i&&g[M=(m=m.map((r,y)=>m.map((v,x)=>a|=b|=(i&1?r>>n+~x:v>>y)%2<<x,b=0)|b,a=0)).flatMap(v=>v/(a&-a)||[])]|F(i-1))(8)?0:g[M]=++c)([...Array(n)],0)|c

Try it online!