|
| |
|
|
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.
|
|
4
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
LINKS
|
|
|
|
FORMULA
|
Sum_{k=1..n} k^2 * T(n,k) = n^2 * A045846(n).
|
|
|
EXAMPLE
|
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;
|
|
|
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 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
