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

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

Offset

1,2

Comments

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

Links

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

Eric Weisstein's World of Mathematics, Hadwiger Problem

Eric Weisstein's World of Mathematics, Cube Dissection

Formula

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

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

Example

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

Crossrefs

Cf. A014544, A228267 (with multiplicity), A259792 (arithmetic instead of geometric partition).

Cf. A034295 (same problem in 2 dimensions rather than 3).

Cf. A000041, A133042.

Sequence in context: A214773 A235618 A076201 * A086791 A291633 A004687

Adjacent sequences: A129665 A129666 A129667 * A129669 A129670 A129671

Keyword

hard,more,nonn,nice

Author

Sergio Pimentel, May 02 2008, Jun 03 2008

Status

approved