|
| |
|
|
A034295
|
|
Number of different ways to divide an n X n square into sub-squares, considering only the list of parts.
|
|
26
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Number of ways an n X n square can be cut into integer-sided squares: collections of integers {a_i} so that squares of length a_i tile an n X n square.
This ignores the way the squares are arranged. We are only counting the lists of parts (compare A045846).
Also applies to the partitions of an equilateral triangle of length n. - Robert G. Wilson v
|
|
|
LINKS
|
Jon E. Schoenfield, Table of solutions for n <= 12 (Caution: this table is missing 6 of the ways to divide an 11 X 11 square into sub-squares! Please see the Alois P. Heinz link listing those six ways. Thanks to Alois for catching this! -- Jon E. Schoenfield)
|
|
|
EXAMPLE
|
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)
|
|
|
MAPLE
|
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])):
|
|
|
MATHEMATICA
|
$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 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,hard,nice,more
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
