login
Number of tilings of an n X n square using V (2m+1)-ominoes (m >= 0) in standard orientation.
1

%I #14 Apr 22 2021 08:48:36

%S 1,1,2,8,68,1262,51420,4577274,888837716,376116199534,346688563051200,

%T 695975307003529228

%N Number of tilings of an n X n square using V (2m+1)-ominoes (m >= 0) in standard orientation.

%C The shapes of the tiles are:

%C ._.

%C ._. | |

%C ._. | | | |

%C ._. | |_. | |_._. | |_._._.

%C |_| |___| |_____| |_______| ... .

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Polyomino">Polyomino</a>

%e a(3) = 8:

%e ._____. ._____. ._____. ._____. ._____. ._____. ._____. ._____.

%e |_|_|_| | |_|_| |_|_|_| |_| |_| |_|_|_| |_| |_| | |_|_| | | |_|

%e |_|_|_| |___|_| | |_|_| |_|___| |_| |_| | |___| | |_|_| | |___|

%e |_|_|_| |_|_|_| |___|_| |_|_|_| |_|___| |___|_| |_____| |_____|.

%e .

%p b:= proc(n, l) option remember; local k, m, r;

%p if n=0 or l=[] then 1

%p elif min(l)>0 then (t-> b(n-t, map(h->h-t, l)))(min(l))

%p elif l[-1]=n then b(n, subsop(-1=[][], l))

%p else for k while l[k]>0 do od; r:= 0;

%p for m from 0 while k+m<=nops(l) and l[k+m]=0 and n>m do

%p r:= r+b(n, [l[1..k-1][], 1$m, m+1, l[k+m+1..nops(l)][]])

%p od; r

%p fi

%p end:

%p a:= n-> b(n, [0$n]):

%p seq(a(n), n=0..9);

%t b[n_, l_] := b[n, l] = Module[{k, m, r}, Which[n == 0 || l == {}, 1, Min[l] > 0, Function[t, b[n-t, l-t]][Min[l]], l[[-1]] == n, b[n, ReplacePart[l, -1 -> Nothing]], True, For[k = 1, l[[k]] > 0, k++]; r = 0; For[m = 0, k + m <= Length[l] && l[[k+m]] == 0 && n > m, m++, r = r + b[n, Join[l[[1 ;; k-1]], Array[1&, m], {m+1}, l[[k+m+1 ;; Length[l]]]]]]; r]];

%t a[n_] := b[n, Array[0&, n]];

%t a /@ Range[0, 9] (* _Jean-François Alcover_, Apr 22 2021, after _Alois P. Heinz_ *)

%Y Main diagonal of A322494.

%K nonn,more

%O 0,3

%A _Alois P. Heinz_, Dec 12 2018