A014544 -id:A014544 - cp's OEIS frontend

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

Erich Friedman, Dec 11 1999

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

			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)

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)

Cf. A045846, A224239.
Cf. A014544, A129668 (these both involve cubes).
Main diagonal of A224697.

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

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

A074764 Numbers of smaller squares into which a square may be dissected.

Original entry on oeis.org

1, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74

Offset: 1

Marc LeBrun, Sep 06 2002

All even k > 2 are present by generalizing this corner+border construction, all odd k > 5 are present because k+3 can be obtained from k by splitting any single square into four, 1 is trivially present and k = 2, 3 & 5 are then fairly easily eliminated.
Also number of smaller similar triangles into which a triangle may be dissected. - Lekraj Beedassy, Nov 25 2003 [This isn't true; for example, an isosceles right triangle can be dissected in 2 and therefore into any positive integer number of smaller similar triangles. - M. F. Hasler, May 24 2024]
Also positive integers k such that there exist k integers x_1, x_2, ..., x_k, distinct or not, satisfying 1 = 1/(x_1)^2 + 1/(x_2)^2 + ... + 1/(x_k)^2. For example, the unique solution for k = 4 is 1 = 1/2^2 + 1/2^2 + 1/2^2 + 1/2^2 (see Hassan Tarfaoui link, Concours Général 1990). - Bernard Schott, Oct 05 2021
With the current definition, one could argue that the initial 1 is wrong and should be 0 instead: One cannot dissect a square into 1 smaller square: not dissecting it yields a(1) = 0 smaller squares. - M. F. Hasler, May 24 2024

			6 is a term of the sequence because a square can be dissected as follows:
  +---+---+---+
  |...|...|...|
  +---+---+---+
  |.......|...|
  |.......+---+
  |.......|...|
  +-------+---+

A. Soifer, How Does One Cut A Triangle?, Chapter 2, CEME, Colorado Springs CO 1990.
Allan C. Wechsler and Michael Kleber, messages to math-fun mailing list, Sep 06, 2002.

Mr. Glaeser, Carrés, Le Petit Archimède, no. 0, January 1973.
Murray Klamkin, Review of "How Does One Cut a Triangle?" by Alexander Soifer, Amer. Math. Monthly, October 1991, pp. 775-. [Annotated scanned copy of pages 775-777 only] See "Grand Problem 2".
Miklós Laczkovich, Tilings of polygons with similar triangles, Combinatorica 10.3 (1990): 281-306.
Miklós Laczkovich. Tilings of triangles Discrete mathematics 140.1 (1995): 79-94.
Miklós Laczkovich, Tilings of polygons with similar triangles, II, Discrete & Computational Geometry 19.3 (1998): 411-425.
Alexander Soifer, How Does One Cut a Triangle?, Chapter 2, Springer-Verlag New York, 2009.
Hassan Tarfaoui, Concours Général 1990 - Exercice 3 (in French).
Andrzej Zak, Dissection of a triangle into similar triangles, Discrete & Computational Geometry 34.2 (2005): 295-312.
Index to sequences related to Olympiads and other Mathematical competitions.
Index entries for linear recurrences with constant coefficients, signature (2,-1).

Cf. A005792, A014544 (cubes).

gf:= x*(1 - x + x^3 - x^4 + x^5)/(1-x):
select(t-> coeftayl(gf, x=0, t)=1, [$1..100])[];  # Alois P. Heinz, Aug 17 2021

CoefficientList[Series[(1 + 2*x -x^2 - x^3)/(1 - x)^2, {x, 0, 20}], x] (* Georg Fischer, Aug 17 2021 *)
LinearRecurrence[{2,-1},{1,4,6,7},80] (* Harvey P. Dale, Oct 17 2021 *)

A074764(n)=if(n>2, n+3, n^2) \\ M. F. Hasler, May 24 2024

A074764 = lambda n: n+3 if n>2 else n*n # M. F. Hasler, May 24 2024

{k : k != 2, 3, or 5}.
G.f. of characteristic function: x*(1 - x + x^3 - x^4 + x^5)/(1-x).
G.f.: x*(1 + 2*x -x^2 - x^3)/(1 - x)^2. - Georg Fischer, Aug 17 2021
a(n) = n + 3 for all n > 2. - M. F. Hasler, May 24 2024
E.g.f.: exp(x)*(3 + x) - x^2/2 - 3*(x + 1). - Stefano Spezia, Sep 17 2024

A129668 Number of different ways to divide an n X n X n cube into subcubes, considering only the list of parts.

Original entry on oeis.org

1, 2, 3, 11, 19, 121, 291, 1656

Offset: 1

Sergio Pimentel, May 02 2008, Jun 03 2008

The Hadwiger problem analyzes how to divide a cube into n subcubes. This sequence analyzes in how many different ways the n X n X n cube can be divided into subcubes.
One of the 1656 possible divisions of the 8 X 8 X 8 cube (42 of 1 X 1 X 1; 4 of 2 X 2 X 2; 2 of 3 X 3 X 3; and 6 of 4 X 4 X 4) solves the last unknown of the Hadwiger problem, n=54, found in 1973.
This sequence does not consider the way the cubes are arranged. - Jon E. Schoenfield, Nov 14 2014

			a(3) = 3 because the 3 X 3 X 3 cube can be divided into subcubes in 3 different ways: a single 3 X 3 X 3 cube, a 2 X 2 X 2 plus 19 1 X 1 X 1 cubes, or 27 1 X 1 X 1 cubes.
a(4) = 11 because the 4 X 4 X 4 cube can be divided into 11 different combinations of subcubes. The table below lists each of the 11 combinations and gives the number of ways those subcubes can be arranged:
   (1) 64 1 X 1 X 1 cubes                       in   1 way
   (2) 56 1 X 1 X 1 cubes and 1 2 X 2 X 2 cube  in  27 ways
   (3) 48 1 X 1 X 1 cubes and 2 2 X 2 X 2 cubes in 193 ways
   (4) 40 1 X 1 X 1 cubes and 3 2 X 2 X 2 cubes in 544 ways
   (5) 32 1 X 1 X 1 cubes and 4 2 X 2 X 2 cubes in 707 ways
   (6) 24 1 X 1 X 1 cubes and 5 2 X 2 X 2 cubes in 454 ways
   (7) 16 1 X 1 X 1 cubes and 6 2 X 2 X 2 cubes in 142 ways
   (8)  8 1 X 1 X 1 cubes and 7 2 X 2 X 2 cubes in  20 ways
   (9)  8 2 X 2 X 2 cubes                       in   1 way
  (10) 37 1 X 1 X 1 cubes and 1 3 X 3 X 3 cube  in   8 ways
  (11)  1 4 X 4 X 4 cube                        in   1 way
The total number of arrangements is 2098 = A228267(4,4,4).

Eric Weisstein's World of Mathematics, Hadwiger Problem
Eric Weisstein's World of Mathematics, Cube Dissection

Cf. A014544, A228267 (with multiplicity), A259792 (arithmetic instead of geometric partition).
Cf. A034295 (same problem in 2 dimensions rather than 3).
Cf. A000041, A133042.

a(n) <= A133042(n) = A000041(n)^3. - David A. Corneth, Nov 25 2017

a(n) <= A259792(n). - R. J. Mathar, Nov 27 2017

A353935 Numbers k such that a cube cannot be divided into k subcubes.

Original entry on oeis.org

2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 21, 23, 24, 25, 26, 28, 30, 31, 32, 33, 35, 37, 40, 42, 44, 47

Offset: 1

Laurence Reeves, May 11 2022

This is the finite list of 32 counts of smaller cubes that a cube cannot be subdivided into.
It is not proven that the last couple of terms belong to this sequence - see Hickerson link.
Note that cubes themselves are not on the list.

Peter Connor and Phillip Marmorino, Decomposing cubes into smaller cubes, Journal of Geometry 109 (2018), article 19.
Dean Hickerson, Further comments on A014544, Nov 01 2007 and Nov 10 2007.
Matthew Hudelson, Dissecting d-cubes into smaller d-cubes, Journal of Combinatorial Theory, Series A, 81 (1998), 190-200.

Cf. A179101 (squares).

Complement of A014544.

cp's OEIS Frontend

A034295 Number of different ways to divide an n X n square into sub-squares, considering only the list of parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A074764 Numbers of smaller squares into which a square may be dissected.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A129668 Number of different ways to divide an n X n X n cube into subcubes, considering only the list of parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A353935 Numbers k such that a cube cannot be divided into k subcubes.

Views

Author

Keywords

Comments

Links

Crossrefs