A045846
Number of distinct ways to cut an n X n square into squares with integer sides.
Original entry on oeis.org
1, 1, 2, 6, 40, 472, 10668, 450924, 35863972, 5353011036, 1500957422222, 790347882174804, 781621363452405930, 1451740730942350766748, 5064070747064013556294032, 33176273260130056822126522884, 408199838581532754602910469192704
Offset: 0
For n=3 the 6 dissections are: the full 3 X 3 square; 9 1 X 1 squares; one 2 X 2 square and five 1 X 1 squares (in 4 ways).
- Andrew Gozzard and Max Ward, Table of n, a(n) for n = 0..25 (terms 0..20 from Steve Butler).
- Steve Butler, Jason Ekstrand, Steven Osborne, Counting Tilings by Taking Walks in a Graph, A Project-Based Guide to Undergraduate Research in Mathematics, Birkhäuser, Cham (2020), see page 169.
- N. J. A. Sloane, Illustration of the first five terms of A045846 and A224239, page 1 of 4 (Each dissection from A224239 is labeled with the number of its images under the symmetry group of the square. The sum of these numbers is A045846(n).)
- N. J. A. Sloane, Illustration of the first five terms of A045846 and A224239, page 2 of 4 (The largest squares are drawn in red. The next-largest squares, unless of size 1, are drawn in blue.)
- N. J. A. Sloane, Illustration of the first five terms of A045846 and A224239, page 3 of 4 (The largest squares are drawn in red. The next-largest squares, unless of size 1, are drawn in blue.)
- N. J. A. Sloane, Illustration of the first five terms of A045846 and A224239, page 4 of 4 (The largest squares are drawn in red. The next-largest squares, unless of size 1, are drawn in blue.)
- Ed Wynn, Exhaustive generation of Mrs Perkins's quilt square dissections for low orders, arXiv:1308.5420 [math.CO], 2013-2014.
See
A224239 for the number of inequivalent ways.
-
b:= proc(n, l) option remember; local i, k, s, t;
if max(l[])>n then 0 elif n=0 or l=[] then 1
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;
for i from k to nops(l) while l[i]=0 do s:=s+
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]):
seq(a(n), n=0..11); # Alois P. Heinz, Apr 15 2013
-
$RecursionLimit = 1000; b[n_, l_List] := b[n, l] = Module[{i, k, s, t}, Which[ Max[l]>n, 0, n == 0 || l == {}, 1, Min[l]>0, t = Min[l]; b[n-t, l-t], True, For[k = 1, True, k++, If[l[[k]] == 0, Break[]]]; s=0; For[i=k, i <= Length[l] && l[[i]] == 0, i++, s = s + b[n, Join[l[[1 ;; k-1]], Table[1+i-k, {i-k+1}], l[[i+1 ;; Length[l]]]]]]; s]]; a[n_] := b[n, Array[0&, n]]; Table[a[n], {n, 0, 11}] (* Jean-François Alcover, Feb 25 2015, after Alois P. Heinz *)
A226545
Number A(n,k) of squares in all tilings of a k X n rectangle using integer-sided square tiles; square array A(n,k), n>=0, k>=0, read by antidiagonals.
Original entry on oeis.org
0, 0, 0, 0, 1, 0, 0, 2, 2, 0, 0, 3, 5, 3, 0, 0, 4, 12, 12, 4, 0, 0, 5, 25, 34, 25, 5, 0, 0, 6, 50, 98, 98, 50, 6, 0, 0, 7, 96, 256, 386, 256, 96, 7, 0, 0, 8, 180, 654, 1402, 1402, 654, 180, 8, 0, 0, 9, 331, 1625, 4938, 6940, 4938, 1625, 331, 9, 0
Offset: 0
A(3,3) = 1 + 6 + 6 + 6 + 6 + 9 = 34:
._____. ._____. ._____. ._____. ._____. ._____.
| | | |_| |_| | |_|_|_| |_|_|_| |_|_|_|
| | |___|_| |_|___| |_| | | |_| |_|_|_|
|_____| |_|_|_| |_|_|_| |_|___| |___|_| |_|_|_|
Square array A(n,k) begins:
0, 0, 0, 0, 0, 0, 0, 0, ...
0, 1, 2, 3, 4, 5, 6, 7, ...
0, 2, 5, 12, 25, 50, 96, 180, ...
0, 3, 12, 34, 98, 256, 654, 1625, ...
0, 4, 25, 98, 386, 1402, 4938, 16936, ...
0, 5, 50, 256, 1402, 6940, 33502, 157279, ...
0, 6, 96, 654, 4938, 33502, 221672, 1426734, ...
0, 7, 180, 1625, 16936, 157279, 1426734, 12582472, ...
Columns (or rows) k=0-10 give:
A000004,
A001477,
A067331(n-1) for n>0,
A226546,
A226547,
A226548,
A226549,
A226550,
A226551,
A226552,
A226553.
-
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, k)-> `if`(n>=k, b(n, [0$k]), b(k, [0$n]))[2]:
seq(seq(A(n, d-n), n=0..d), d=0..14);
-
b[n_, l_List] := 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 ;; -1]]]]] ]; s]]; a[n_, k_] := If[n >= k, b[n, Array[0&, k]], b[k, Array[0&, n]]][[2]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 13 2013, translated from Maple *)
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.
Original entry on oeis.org
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
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;
-
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);
-
$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 *)
A226897
a(n) is the total number of parts in the set of partitions of an n X n square lattice into squares, considering only the list of parts.
Original entry on oeis.org
1, 5, 16, 59, 156, 529, 1351, 3988, 10236, 27746, 66763, 176783, 412450
Offset: 1
For n = 3, the partitions are:
Square side 1 2 3 Total Parts
9 0 0 9
5 1 0 6
0 0 1 1
Total 16
So a(3) = 16.
-
b:= proc(n, l) option remember; local i, k, s, t;
if max(l[])>n then {} elif n=0 or l=[] then {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:={};
for i from k to nops(l) while l[i]=0 do s:=s union
map(v->v+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:
a:= n-> add(coeff(add(j, j=b(n, [0$n])), x, i), i=1..n):
seq(a(n), n=1..9); # Alois P. Heinz, Jun 21 2013
-
$RecursionLimit = 1000; b[n_, l_List] := b[n, l] = Module[{i, k, s, t}, Which [Max[l]>n, {}, n == 0 || l == {}, {0}, Min[l]>0, t = Min[l]; b[n-t, l-t], True, k = Position[l, 0, 1, 1][[1, 1]]; s = {}; For[i = k, i <= Length[l] && l[[i]]== 0, i++, s = s ~Union~ Map[Function[{v}, v+x^(1+i-k)], b[n, Join[l[[1 ;; k-1]], Array[1+i-k&, i-k+1], l[[i+1 ;; -1]] ]]]]; s]]; a[n_] := Sum[Coefficient[Sum[j, {j, b[n, Array[0&, n]]}], x, i], {i, 1, n}]; Table[a[n], {n, 1, 9}] (* Jean-François Alcover, May 29 2015, after Alois P. Heinz *)
Showing 1-4 of 4 results.
Comments