login
Number T(n,k) of squares of size k^2 in all tilings of an n X n square using integer-sided square tiles; triangle T(n,k), n >= 1, 1 <= k <= n, read by rows.
4

%I #24 Apr 27 2022 08:57:15

%S 1,4,1,29,4,1,312,69,4,1,5598,1184,153,4,1,176664,40078,4552,373,4,1,

%T 9966344,2311632,285414,18160,917,4,1,1018924032,241967774,30278272,

%U 2128226,74368,2321,4,1,190191337356,45914039784,5860964300,411308056,16210982,311784,5933,4,1

%N Number T(n,k) of squares of size k^2 in all tilings of an n X n square using integer-sided square tiles; triangle T(n,k), n >= 1, 1 <= k <= n, read by rows.

%H Alois P. Heinz, <a href="/A226936/b226936.txt">Rows n = 1..15, flattened</a>

%F Sum_{k=1..n} T(n,k) = A226554(n).

%F Sum_{k=1..n} k^2 * T(n,k) = n^2 * A045846(n).

%e For n=3 there are [29, 4, 1] squares of sizes [1^2, 2^2, 3^3] in all tilings of a 3 X 3 square:

%e ._._._. ._._._. ._._._. ._._._. ._._._. ._._._.

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

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

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

%e Triangle T(n,k) begins:

%e n \ k 1 2 3 4 5 6 7 8

%e --:----------------------------------------------------------------

%e 1 : 1;

%e 2 : 4, 1;

%e 3 : 29, 4, 1;

%e 4 : 312, 69, 4, 1;

%e 5 : 5598, 1184, 153, 4, 1;

%e 6 : 176664, 40078, 4552, 373, 4, 1;

%e 7 : 9966344, 2311632, 285414, 18160, 917, 4, 1;

%e 8 : 1018924032, 241967774, 30278272, 2128226, 74368, 2321, 4, 1;

%p b:= proc(n, l) option remember; local i, k, s, t;

%p if max(l[])>n then [0$2] elif n=0 then [1, 0]

%p elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l))

%p else for k do if l[k]=0 then break fi od; s:=[0$2];

%p for i from k to nops(l) while l[i]=0 do s:= s+(h->h+

%p [0, h[1]*x^(1+i-k)])(b(n, [l[j]$j=1..k-1,

%p 1+i-k$j=k..i, l[j]$j=i+1..nops(l)])) od; s

%p fi

%p end:

%p T:= n-> seq(coeff(b(n, [0$n])[2],x,k), k=1..n):

%p seq(T(n), n=1..10);

%t $RecursionLimit = 1000; b[n_, l_List] := b[n, l] = Module[{i, k, s, t}, Which[Max[l] > n, {0, 0}, n == 0, {1, 0}, Min[l] > 0, t = Min[l]; b[n-t, l-t], True, k = Position[l, 0, 1, 1][[1, 1]]; s = {0, 0}; For[i = k, i <= Length[l] && l[[i]] == 0, i++, s = s + Function[h, h + {0, h[[1]]*x^(1+i-k)}][b[n, Join[l[[1 ;; k-1]], Array[1+i-k&, i-k+1], l[[i+1 ;; -1]] ] ] ] ]; s] ]; T[n_] := Table[Coefficient[b[n, Array[0&, n]][[2]], x, k], {k, 1, n}]; Table[T[n], {n, 1, 10}] // Flatten (* _Jean-François Alcover_, Dec 23 2013, translated from Maple *)

%Y Row sums give: A226554.

%Y Main diagonal and lower diagonals give: A000012, A010709, A226892.

%Y Cf. A045846.

%K nonn,tabl

%O 1,2

%A _Alois P. Heinz_, Jun 22 2013