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 *)
A034295
Number of different ways to divide an n X n square into sub-squares, considering only the list of parts.
Original entry on oeis.org
1, 2, 3, 7, 11, 31, 57, 148, 312, 754, 1559, 3844, 7893, 17766, 37935, 83667, 170165, 369698, 743543, 1566258, 3154006, 6424822, 12629174, 25652807, 49802454, 98130924, 189175310, 368095797
Offset: 1
From _Jon E. Schoenfield_, Sep 18 2008: (Start)
a(3) = 3 because the 3 X 3 square can be divided into sub-squares in 3 different ways: a single 3 X 3 square, a 2 X 2 square plus five 1 X 1 squares, or nine 1 X 1 squares.
There are a(5) = 11 different ways to divide a 5 X 5 square into sub-squares:
1. 25(1 X 1)
2. 1(2 X 2) + 21(1 X 1)
3. 2(2 X 2) + 17(1 X 1)
4. 3(2 X 2) + 13(1 X 1)
5. 4(2 X 2) + 9(1 X 1)
6. 1(3 X 3) + 16(1 X 1)
7. 1(3 X 3) + 1(2 X 2) + 12(1 X 1)
8. 1(3 X 3) + 2(2 X 2) + 8(1 X 1)
9. 1(3 X 3) + 3(2 X 2) + 4(1 X 1)
10. 1(4 X 4) + 9(1 X 1)
11. 1(5 X 5)
a(9) = 312 because the 9 X 9 square can be divided into 312 different combinations of sub-squares such as three 4 X 4 squares plus thirty-three 1 X 1 squares, etc. (End)
-
b:= proc(n, l) option remember; local i, k, s;
if max(l[])>n then {} elif n=0 then {0}
elif min(l[])>0 then (t->b(n-t, map(h->h-t, l)))(min(l[]))
else for k while l[k]>0 do 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-> nops(b(n, [0$n])):
seq(a(n), n=1..9); # Alois P. Heinz, Apr 15 2013
-
$RecursionLimit = 1000; 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_] := a[n] = b[n, Array[0&, n]] // Length; Table[Print[a[n]]; a[n], {n, 1, 12} ] (* Jean-François Alcover, Feb 18 2014, after Alois P. Heinz *)
A219924
Number A(n,k) of 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
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 5, 6, 5, 1, 1, 1, 1, 8, 13, 13, 8, 1, 1, 1, 1, 13, 28, 40, 28, 13, 1, 1, 1, 1, 21, 60, 117, 117, 60, 21, 1, 1, 1, 1, 34, 129, 348, 472, 348, 129, 34, 1, 1, 1, 1, 55, 277, 1029, 1916, 1916, 1029, 277, 55, 1, 1
Offset: 0
A(3,3) = 6, because there are 6 tilings of a 3 X 3 rectangle using integer-sided squares:
._____. ._____. ._____. ._____. ._____. ._____.
| | | |_| |_| | |_|_|_| |_|_|_| |_|_|_|
| | |___|_| |_|___| |_| | | |_| |_|_|_|
|_____| |_|_|_| |_|_|_| |_|___| |___|_| |_|_|_|
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, 1, ...
1, 1, 1, 1, 1, 1, 1, 1, ...
1, 1, 2, 3, 5, 8, 13, 21, ...
1, 1, 3, 6, 13, 28, 60, 129, ...
1, 1, 5, 13, 40, 117, 348, 1029, ...
1, 1, 8, 28, 117, 472, 1916, 7765, ...
1, 1, 13, 60, 348, 1916, 10668, 59257, ...
1, 1, 21, 129, 1029, 7765, 59257, 450924, ...
Columns (or rows) k=0+1, 2-10 give:
A000012,
A000045(n+1),
A002478,
A054856,
A054857,
A219925,
A219926,
A219927,
A219928,
A219929.
-
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, k)-> `if`(n>=k, b(n, [0$k]), b(k, [0$n])):
seq(seq(A(n, d-n), n=0..d), d=0..14);
# The following is a second version of the program that lists the actual dissections. It produces a list of pairs for each dissection:
b:= proc(n, l, ll) local i, k, s, t;
if max(l[])>n then 0 elif n=0 or l=[] then lprint(ll); 1
elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l), ll)
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)],
[ll[],[k,1+i-k]])
od; s
fi
end:
A:= (n, k)-> b(k, [0$n], []):
A(5,5);
# In each list [a,b] means put a square with side length b at
leftmost possible position with upper corner in row a. For example
[[1,3], [4,2], [4,2], [1,2], [3,1], [3,1], [4,1], [5,1]], gives:
___.___.
| | |
| |_|
|___|_|_|
| | |_|
|_|___|_|
-
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, k = Position[l, 0, 1][[1, 1]]; 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, {j, k, i}], l[[i+1;; -1]] ] ] ]; s]]; a[n_, k_] := If[n >= k, b[n, Array[0&, k]], b[k, Array[0&, n]]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 13 2013, translated from 1st Maple program *)
A227690
Number A(n,k) of tilings of a k X n rectangle using integer-sided square tiles reduced for symmetry; square array A(n,k), n >= 0, k >= 0, read by antidiagonals.
Original entry on oeis.org
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 4, 3, 4, 1, 1, 1, 1, 5, 6, 6, 5, 1, 1, 1, 1, 9, 10, 13, 10, 9, 1, 1, 1, 1, 12, 21, 39, 39, 21, 12, 1, 1, 1, 1, 21, 39, 115, 77, 115, 39, 21, 1, 1, 1, 1, 30, 82, 295, 521, 521, 295, 82, 30, 1, 1
Offset: 0
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, 2, 2, 4, 5, 9, 12, 21, ...
1, 1, 2, 3, 6, 10, 21, 39, 82, ...
1, 1, 4, 6, 13, 39, 115, 295, 861, ...
1, 1, 5, 10, 39, 77, 521, 1985, 8038, ...
1, 1, 9, 21, 115, 521, 1494, 15129, 83609, ...
1, 1, 12, 39, 295, 1985, 15129, 56978, 861159, ...
1, 1, 21, 82, 861, 8038, 83609, 861159, 4495023, ...
...
A(4,3) = 6 because there are 6 ways to tile a 3 X 4 rectangle by subsquares, reduced for symmetry, i.e., where rotations and reflections are not counted as distinct:
._____ _. ._______. ._______.
| |_| | | | | |_|_|
| |_| |___|_ _| |___| |
|_____|_| |_|_|_|_| |_|_|___|
._______. ._______. ._______.
| |_|_| |_| |_| |_|_|_|_|
|___|_|_| |_|___|_| |_|_|_|_|
|_|_|_|_| |_|_|_|_| |_|_|_|_|
A226979
Number of ways to cut an n X n square into squares with integer sides, reduced for symmetry, where the orbits under the symmetry group of the square, D4, have 2 elements.
Original entry on oeis.org
0, 0, 0, 2, 2, 24, 36, 344, 504, 7657, 11978, 289829
Offset: 1
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.
a(8)-a(12) from
Ed Wynn, Apr 01 2014
A226980
Number of ways to cut an n X n square into squares with integer sides, reduced for symmetry, where the orbits under the symmetry group of the square, D4, have 4 elements.
Original entry on oeis.org
0, 0, 1, 6, 26, 264, 1157, 23460, 153485, 6748424, 70521609, 6791578258
Offset: 1
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.
a(8)-a(12) from
Ed Wynn, Apr 01 2014
A227004
Irregular triangle read by rows: T(n,k) is the number of inequivalent tilings by squares of an n X n square lattice that contain k nodes unconnected to any of their neighbors.
Original entry on oeis.org
1, 1, 1, 1, 1, 0, 0, 1, 1, 3, 4, 2, 2, 0, 0, 0, 0, 1, 1, 3, 13, 20, 17, 6, 10, 5, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 6, 37, 138, 280, 300, 255, 218, 98, 43, 55, 28, 20, 11, 1, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 1
Offset: 1
For n = 4, there are 3 inequivalent tilings that contain 1 isolated node, so T(4,1) = 3.
A 2 X 2 square contains 1 isolated node.
Consider that each tiling 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 3 tilings are:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 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 1 1 1 1 1 1
A226978
Number of ways to cut an n X n square into squares with integer sides, reduced for symmetry, where the orbits under the symmetry group of the square, D4, have 1 element.
Original entry on oeis.org
1, 2, 2, 4, 4, 12, 8, 44, 32, 228, 148, 1632, 912, 16004, 8420, 213680, 101508, 3933380, 1691008, 98949060, 38742844, 3413919788, 1213540776, 161410887252, 52106993880
Offset: 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:
---------
| | | | |
---------
| | | |
--- ---
| | | |
---------
| | | | |
---------
a(8)-a(12) from
Ed Wynn, Apr 02 2014
A226981
Number of ways to cut an n X n square into squares with integer sides, reduced for symmetry, where the orbits under the symmetry group of the square, D4, have 8 elements.
Original entry on oeis.org
0, 0, 0, 1, 45, 1194, 55777, 4471175, 669049507, 187616301623, 98793450008033, 97702667035688951
Offset: 1
For n=5, there are 45 dissections where the orbits under the symmetry group of the square, D4, have 8 elements.
For n=4, this is the only dissection:
---------
| | | |
| -----
| | |
----- |
| | | |
---------
| | | | |
---------
a(8)-a(12) from
Ed Wynn, Apr 02 2014
A225803
Number T(n,k,u) of tilings of an n X k rectangle using integer-sided square tiles, reduced for symmetry, containing u nodes that are unconnected to any of their neighbors; irregular triangle T(n,k,u), 1 <= k < n, u >= 0, read by rows.
Original entry on oeis.org
1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 2, 0, 1, 1, 1, 2, 2, 1, 2, 4, 0, 2, 1, 1, 4, 13, 10, 6, 3, 1, 0, 0, 1, 1, 1, 3, 4, 1, 1, 3, 8, 3, 2, 3, 0, 0, 1, 1, 6, 23, 33, 24, 15, 6, 0, 2, 2, 2, 1, 1, 6, 40, 101, 129, 79, 74, 53, 13, 9, 11, 4, 0, 0, 0, 0, 1
Offset: 1
The irregular triangle T(n,k,u) begins:
n,k\u 0 1 2 3 4 5 6 7 8 9 10 11 12 ...
2,1 1
3,1 1
3,2 1 1
4,1 1
4,2 1 2 1
4,3 1 2 2 0 1
5,1 1
5,2 1 2 2
5,3 1 2 4 0 2 1
5,4 1 4 13 10 6 3 1 0 0 1
6,1 1
6,2 1 3 4 1
6,3 1 3 8 3 2 3 0 0 1
6,4 1 6 23 33 24 15 6 0 2 2 1
6,5 1 6 40 101 79 74 53 13 9 11 4 0 0 ...
...
T(5,3,2) = 4 because there are 4 different sets of tilings of the 5 X 3 rectangle by integer-sided squares in which each tiling contains 2 isolated nodes. Any sequence of group D2 operations will transform each tiling in a set into another in the same set. Group D2 operations are:
. the identity operation
. rotation by 180 degrees
. reflection about a horizontal axis through the center
. reflection about a vertical axis through the center
A 2 X 2 square contains 1 isolated node. Consider that each tiling 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. An example of a tiling in each set is:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Showing 1-10 of 19 results.
Comments