A034295 Number of different ways to divide an n X n square into sub-squares, considering only the list of parts.
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
Examples
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)
Links
- Alois P. Heinz, List of different ways to divide a 13 X 13 square into sub-squares
- Alois P. Heinz, More ways to divide an 11 X 11 square into sub-squares
- Holger Langenau, Squaring the square: New methods for determining the number of perfect square packings, 2018.
- 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)
- N. J. A. Sloane, Drawing to illustrate a(1)-a(4)
Crossrefs
Programs
-
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])): seq(a(n), n=1..9); # Alois P. Heinz, Apr 15 2013 -
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 *)
Extensions
More terms from Sergio Pimentel, Jun 03 2008
Corrected and extended by Jon E. Schoenfield, Sep 19 2008
Edited by N. J. A. Sloane, Apr 12 2013, at the suggestion of Paolo P. Lava
a(11) corrected by Alois P. Heinz, Apr 15 2013
a(13) from Alois P. Heinz, Apr 19 2013
a(14) from Christopher Hunt Gribble, Oct 26 2013
a(15) and a(16) from Fidel I. Schaposnik, May 04 2015
a(17)-a(23) from Holger Langenau, Sep 20 2017
a(24) from Michael De Vlieger, May 04 2018, from paper written by Holger Langenau
a(25) and a(26) from Holger Langenau, May 14 2018
a(27) from Holger Langenau, Apr 15 2019
a(28) from Holger Langenau, Jun 17 2020
a(28) corrected by Holger Langenau, Jul 31 2020
Comments