A226554 Number of squares in all tilings of an n X n square using integer-sided square tiles.

0, 1, 5, 34, 386, 6940, 221672, 12582472, 1293374998, 242394178200, 83374069529638, 52845726291860344, 61928161880183204434, 134499571879749571406816, 542432658409586214809714176, 4068438590479352629770422328000, 56820656114941381799512710314429768

Offset: 0

Author

Alois P. Heinz, Jun 10 2013

Keywords

• nonn

Crossrefs

Main diagonal of A226545.

Row sums of A226936.

Cf. A045846.

Programs

Maple

b:= proc(n, l) option remember; local i, k, s, t;
      if max(l[])>n then [0, 0] elif n=0 or l=[] then [1, 0]
    elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l))
    else for k do if l[k]=0 then break fi od; s:=[0$2];
         for i from k to nops(l) while l[i]=0 do s:=s+(h->h+[0, h[1]])
           (b(n, [l[j]$j=1..k-1, 1+i-k$j=k..i, l[j]$j=i+1..nops(l)]))
         od; s
      fi
    end:
a:= n-> b(n, [0$n])[2]:
seq(a(n), n=0..10);

Mathematica

b[n_, l_] := b[n, l] = Module[{i, k, s, t},
     Which[Max[l] > n, {0, 0}, n == 0 || l == {}, {1, 0},
     Min[l] > 0, t = Min[l]; b[n - t, l - t], True,
       k = Position[l, 0, 1][[1, 1]]; s = {0, 0};
     For[i = k, i <= Length[l] && l[[i]] == 0, i++,
       s = s + Function[h, h + {0, h[[1]]}][b[n, Join[l[[1;; k-1]],
       Table[1+i-k, {j, k, i}], l[[i+1;;]]]]]]; s]];
a[n_] := b[n, Array[0&, n]][[2]];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 15}] (* Jean-François Alcover, Apr 27 2022, after Alois P. Heinz in A226545 *)

Extensions

a(16) from Alois P. Heinz, Nov 16 2016