A226936 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.

1, 4, 1, 29, 4, 1, 312, 69, 4, 1, 5598, 1184, 153, 4, 1, 176664, 40078, 4552, 373, 4, 1, 9966344, 2311632, 285414, 18160, 917, 4, 1, 1018924032, 241967774, 30278272, 2128226, 74368, 2321, 4, 1, 190191337356, 45914039784, 5860964300, 411308056, 16210982, 311784, 5933, 4, 1

Offset: 1

Author

Alois P. Heinz, Jun 22 2013

Keywords

• nonn
• tabl

Examples

			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:
._._._.  ._._._.  ._._._.  ._._._.  ._._._.  ._._._.
|     |  |   |_|  |_|_|_|  |_|   |  |_|_|_|  |_|_|_|
|     |  |___|_|  |   |_|  |_|___|  |_|   |  |_|_|_|
|_____|  |_|_|_|  |___|_|  |_|_|_|  |_|___|  |_|_|_|.
Triangle T(n,k) begins:
n \ k        1          2         3        4      5     6   7   8
--:----------------------------------------------------------------
1 :          1;
2 :          4,         1;
3 :         29,         4,        1;
4 :        312,        69,        4,       1;
5 :       5598,      1184,      153,       4,     1;
6 :     176664,     40078,     4552,     373,     4,    1;
7 :    9966344,   2311632,   285414,   18160,   917,    4,  1;
8 : 1018924032, 241967774, 30278272, 2128226, 74368, 2321,  4,  1;
		

Links

• Alois P. Heinz, Rows n = 1..15, flattened

Crossrefs

Row sums give: A226554.

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

Cf. A045846.

Programs

Maple

b:= proc(n, l) option remember; local i, k, s, t;
      if max(l[])>n then [0$2] elif n=0 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]*x^(1+i-k)])(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:
T:= n-> seq(coeff(b(n, [0$n])[2],x,k), k=1..n):
seq(T(n), n=1..10);

Mathematica

$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 *)

Formula

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

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