|
%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
|
