A140108 Duplicate of A034295.
1, 2, 3, 7, 11, 31, 57, 148, 312, 754, 1559, 3844
Offset: 1
This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
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).
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 *)
For n=5, the illustrations (see links) show that the 77 solutions consist of: 4 dissections each with 1 image under the group of the square, for a total of 4, 2 dissections each with 2 images under the group of the square, totaling 4, 26 dissections each with 4 images under the group of the square, totaling 104, and 45 dissections each with 8 images under the group of the square, totaling 360, for a grand total of 77 dissections with 472 images, agreeing with A045846(5) = 472.
A(4,5) = 9 because there are 9 ways to divide a 4 X 5 rectangle into subsquares, considering only the list of parts: [20(1 X 1)], [16(1 X 1), 1(2 X 2)], [12(1 X 1), 2(2 X 2)], [11(1 X 1), 1(3 X 3)], [8(1 X 1), 3(2 X 2)], [7(1 X 1), 1(2 X 2), 1(3 X 3)], [4(1 X 1), 4(2 X 2)], [4(1 X 1), 1(4 X 4)], [3(1 X 1), 2(2 X 2), 1(3 X 3)]. There is no way to divide this rectangle into [2(1 X 1), 2(3 X 3)]. Square array A(n,k) begins: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, ... 1, 1, 2, 3, 4, 5, 7, 8, 10, 12, ... 1, 1, 3, 4, 7, 9, 14, 17, 24, 29, ... 1, 1, 3, 5, 9, 11, 20, 26, 36, 48, ... 1, 1, 4, 7, 14, 20, 31, 47, 71, 95, ... 1, 1, 4, 8, 17, 26, 47, 57, 102, 143, ... 1, 1, 5, 10, 24, 36, 71, 102, 148, 238, ... 1, 1, 5, 12, 29, 48, 95, 143, 238, 312, ...
b:= proc(n, l) option remember; local i, k, s, t;
if max(l[])>n then {} elif n=0 or l=[] then {[]}
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(x->sort([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, k)-> `if`(n>=k, nops(b(n, [0$k])), nops(b(k, [0$n]))):
seq(seq(A(n, d-n), n=0..d), d=0..12);
b[n_, l_] := b[n, l] = Module[{i, k, m, s, t}, Which[Max[l] > n, {}, n == 0 || l == {}, {{}}, Min[l] > 0, t = Min[l]; b[n-t, l-t], True, k = Position[l, 0, 1][[1, 1]]; s = {}; For[i = k, i <= Length[l] && l[[i]] == 0, i++, s = s ~Union~ Map[Function[x, Sort[Append[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_, k_] := If[n >= k, Length @ b[n, Array[0&, k]], Length @ b[k, Array[0&, n]]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Dec 19 2013, translated from Maple *)
For n=5, there are 2 dissections where the orbits under the symmetry group of the square, D4, have 2 elements. For n=4, the 2 dissections can be seen in A240120 and A240121.
For n=5, there are 26 dissections where the orbits under the symmetry group of the square, D4, have 4 elements. The 6 dissections for n=4 can be seen in A240123 and A240125.
The a(3) = 21 possible sets of pieces that can tile a 3 X 3 square are given in the table below. (Each column on the right gives a set of pieces.)
.
length X width | number of pieces
---------------+------------------------------------------
3 X 3 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 X 3 | 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 X 2 | 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 X 3 | 0 1 0 0 1 1 0 0 0 3 2 2 1 1 1 1 0 0 0 0 0
1 X 2 | 0 0 1 0 1 0 2 1 0 0 1 0 3 2 1 0 4 3 2 1 0
1 X 1 | 0 0 1 3 0 2 1 3 5 0 1 3 0 2 4 6 1 3 5 7 9
The irregular triangle begins: n,k\u 0 1 2 3 4 5 6 7 8 9 10 11 12 ... 1,1 1 2,1 1 2,2 1 1 3,1 1 3,2 1 1 3,3 1 1 0 0 1 4,1 1 4,2 1 1 1 4,3 1 1 1 0 1 4,4 1 1 1 1 2 0 0 0 0 1 5,1 1 5,2 1 1 1 5,3 1 1 1 0 1 1 5,4 1 1 1 1 2 1 1 0 0 1 5,5 1 1 1 1 2 1 1 1 0 1 0 0 0 ... ... For n = 5 and k = 4 there are 2 partitions that contain 4 isolated nodes, so T(5,4,4) = 2. Consider that each partition is composed of ones and zeros where a one represents a node with one or more links to its neighbors and a zero represents a node with no links to its neighbors. Then the 2 partitions are: 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
a(16)=7 since 16 = 3^2+7*1 = 3^2+2^2+3*1 = 2^2+12*1 = 2*2^2+8*1 = 3*2^2+4*1 = 4*2^2 = 16*1^2 (where 1 = 1^2). a(17)=9 since 17 = 4^2+1 = 3^2+8*1 = 3^2+2^2+4*1 = 3^2+2*2^2 = 2^2+13*1 = 2*2^2+9*1 = 3*2^2+5*1 = 4*2^2+1 = 17*1^2.
b:= proc(n, i) option remember; `if`(n=0, 1,
`if`(i<1, 0, b(n, i-1) +`if`(i^2>n, 0, b(n-i^2, i))))
end:
a:= proc(n) local r; r:= isqrt(n);
b(n, r-`if`(r^2>=n, 1, 0))
end:
seq(a(n), n=0..100); # Alois P. Heinz, Apr 16 2013
b[n_, i_] := b[n, i] = If[n == 0, 1,
If[i < 1, 0, b[n, i - 1] + If[i^2 > n, 0, b[n - i^2, i]]]];
a[n_] := With[{r = Floor@Sqrt[n]}, b[n, r - If[r^2 >= n, 1, 0]]];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Apr 28 2022, after Alois P. Heinz *)
a(n,m)={!m && n<5 && return(n!=1); m || m=sqrtint(n-1); sum(k=2,m, sum(j=1,n\k^2,a(n-j*k^2,k-1)),1)}
For n=5, there are 4 dissections where the orbits under the symmetry group of the square, D4, have 1 element. For n=4, 3 dissections divide the square into uniform subsquares (of sizes 1, 2 and 4 respectively), and this is the 4th: --------- | | | | | --------- | | | | --- --- | | | | --------- | | | | | ---------
Comments