login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A034295 Number of different ways to divide an n X n square into sub-squares, considering only the list of parts. 24
1, 2, 3, 7, 11, 31, 57, 148, 312, 754, 1559, 3844, 7893, 17766, 37935, 83667 (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

Table of n, a(n) for n=1..16.

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

Jon E. Schoenfield, Table of solutions for n <= 12

N. J. A. Sloane, Drawing to illustrate a(1)-a(4)

EXAMPLE

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(1x1)

   2.  1(2x2) + 21(1x1)

   3.  2(2x2) + 17(1x1)

   4.  3(2x2) + 13(1x1)

   5.  4(2x2) +  9(1x1)

   6.  1(3x3) + 16(1x1)

   7.  1(3x3) +  1(2x2) + 12(1x1)

   8.  1(3x3) +  2(2x2) +  8(1x1)

   9.  1(3x3) +  3(2x2) +  4(1x1)

  10.  1(4x4) +  9(1x1)

  11.  1(5x5)

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])):

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 *)

CROSSREFS

Cf. A045846, A224239.

Cf. A014544, A129668 (these both involve cubes).

Diagonal of A224697.

Sequence in context: A120856 A138000 A140108 * A056354 A072534 A056292

Adjacent sequences:  A034292 A034293 A034294 * A034296 A034297 A034298

KEYWORD

nonn,hard,nice,more

AUTHOR

Erich Friedman, Dec 11 1999

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 22 14:21 EDT 2017. Contains 288632 sequences.