Cuboids in a Cube: {##1,n##} Dim. n

[bob012345]

TL;DR Summary

How many cuboids can be drawn within a cube?

Extending the previous problem of Cubes Within Cubes, where we asked how many cubes can be drawn within a cube, now we ask how many cuboids of size {$i ,j ,k = 1,n$} can be drawn in a cube of dimension $n$ where $n$ is an integer.

 

[andrewkirk]

Nit-pick: It is cuboids within a cuboid, not within a cube.

For a d-dimensional cuboid with side length n, the answer will be
$$\sum_{k=1}^n k^d$$
We apply the same logic as we did for the 3-dimensional case: a cube of side length m can have its maximum on dimension j at any of the (n - m + 1) coordinate levels m, m+1, …, n-1, n. Since there are m dimensions, that gives $(n - m +1)^d$ possible locations for a given vertex of the cuboid.

The sum can also be expressed as the product of (m+1) factors that are all linear in n.

 

[bob012345]

Nit-pick: It is cuboids within a cuboid, not within a cube.

For a d-dimensional cuboid with side length n, the answer will be
$$\sum_{k=1}^n k^d$$
We apply the same logic as we did for the 3-dimensional case: a cube of side length m can have its maximum on dimension j at any of the (n - m + 1) coordinate levels m, m+1, …, n-1, n. Since there are m dimensions, that gives $(n - m +1)^d$ possible locations for a given vertex of the cuboid.

The sum can also be expressed as the product of (m+1) factors that are all linear in n.

I'm sticking my neck out here but I believe the solution for how many cubes can be drawn in a cube of dimension $n$ in 3D is $\sum_{k=1}^n k^3$ This was the answer in my previous post Cubes Within Cubes. The answer $\sum_{k=1}^n k^d$ would apply for different dimensions $d$ to lines within a line, squares within a square, cubes within a cube and hypercubes within a hypercube ect. but I believe not for cuboids {$i,j,k=1,n$} within a $n$ sided perfect cuboid to use your preference.

Test your answer for a 2x2x2 cube. The number of entities given by this answer is 9 which is; $$\sum_{k=1}^2 k^3=1^3+2^3=9 $$This accounts for one 2x2x2 and eight 1x1x1's but no 1x1x2's or 2x2x1's which when added give the total as 27.

 

[pbuk]

Summary:: How many cuboids can be drawn within a cube?

Extending the previous problem of Cubes Within Cubes, where we asked how many cubes can be drawn within a cube, now we ask how many cuboids of size {$i ,j ,k = 1,n$} can be drawn in a cube of dimension $n$ where $n$ is an integer.

You need to be more careful with your words: from your later post it is clear that when you wrote "a cube of dimension $n$" you meant "a cube with edges of integer length $n$".

... but I believe not for cuboids {$i,j,k=1,n$} within a $n$ sided perfect cuboid to use your preference.

Similarly, (i) a perfect cuboid is not what you think it is; (ii) all cuboids have exactly six sides, you are using $n$ to refer to the length of each edge so to refer to an "n-sided" anything is meaningless.

Why do you think these 'puzzles' are interesting?

 

[pbuk]

Nit-pick: It is cuboids within a cuboid, not within a cube.

For a d-dimensional cuboid with side length n, the answer will be
...

Double nit-pick: all (non-degenerate) cuboids have 3 dimensions. The n-dimensional generalisation of a cuboid (which is different from the shape the OP seems to have had in mind, which was a simple cube) can be called a polytope although I think you could also unambiguously call it an n-cuboid or hypercuboid, or as you later do a d-dimensional cuboid.

However as all edges of this shape are of equal length it can simply be called a hypercube (or d-cube where d is the number of dimensions).

 

[bob012345]

Double nit-pick: all (non-degenerate) cuboids have 3 dimensions. The n-dimensional generalisation of a cuboid (which is different from the shape the OP seems to have had in mind, which was a simple cube) can be called a polytope although I think you could also unambiguously call it an n-cuboid or hypercuboid, or as you later do a d-dimensional cuboid.

However as all edges of this shape are of equal length it can simply be called a hypercube (or d-cube where d is the number of dimensions).

Well, Wikipedia says "The basic difference between a cube and cuboid is that a cube has equal length, height and breadth whereas in cuboids these three may or may not be the same. The cuboid can also be called a right rectangular prism."

That's what I had in mind. I'm not talking about cubes!

 

[pbuk]

I'm not talking about cubes!

Summary:: How many cuboids can be drawn within a cube?

Extending the previous problem of Cubes Within Cubes, where we asked how many cubes can be drawn within a cube, now we ask how many cuboids of size {$i ,j ,k = 1,n$} can be drawn in a cube of dimension $n$ where $n$ is an integer.

'I'm afraid I can't put it more clearly,' Alice replied very politely, 'for I can't understand it myself to begin with; and being so many different sizes in a day is very confusing.'

 

[bob012345]

The hurrier I go, the behinder I get...

The original question is how many cuboids can be drawn within a cube. The object of the puzzle is cuboids , not cubes per se. So, given a cube of a certain size $n$, and yes, I should have been more careful and not say dimension as one might commonly speak of the dimensions of a bed, how many cuboids, and I meant the more restrictive definition of right cuboids or just rectangular boxes, can be drawn inside it? Quote from unknown source attributed to Lewis Carroll.

 

[pbuk]

So why do you think this, and the earlier puzzle, are interesting?

The solutions as @andrewkirk pointed are trivially found by counting. Many people who are interested in mathematical puzzles need more than this - perhaps something where there is an elegant inductive solution.

 

[etotheipi]

Can I ask a dumb question... what does the notation $\{i ,j ,k = 1,n \}$ mean?

 

[bob012345]

So why do you think this, and the earlier puzzle, are interesting?

The solutions as @andrewkirk pointed are trivially found by counting. Many people who are interested in mathematical puzzles need more than this - perhaps something where there is an elegant inductive solution.

Maybe so but then those people are certainly free to not post in my puzzles. Is all counting trivial? How do you convert a labor of innumerable terms to a simple formula? Can one learn new methods or gain insight along the way? Why do some people compute pi to more and more digits? Or why do some people enjoy probability questions, aren't they just counting? Why are these kinds of puzzles published on math sites or in math books?

Maybe the challenge of figuring out clever ways to count things is itself fun for some people. Why do I think these puzzles are interesting? I don't easily think spatially or geometrically so when I approach such a problem I enjoy figuring out how to figure it out. Along the way for this problem I discovered many interesting symmetries, relationships and tricks. There were several ah-ha moments. I learned a few things about counting, permutations, summing series. I saw relationships between similar problems in different dimensions. There is also a little friendly competition among some friends over solving these kinds of problems as well as other logical conundrums. Besides, there were several levels of 'elegance' to the process of putting the final answer into a compact form.

Here is a little paper I found in dealing with just rectangles and squares for reference to the triviality of the questions. Maybe totally boring and uninteresting to you but this author seems to have had some fun.

https://www.researchgate.net/publication/233955119_The_Total_Number_of_Squares_and_Rectangles_are_There_in_Rectangle_Square_Boards

Also, I have not seen a correct answer to the puzzle offered up by anyone here nor have I seen evidence that the problem is actually as yet completely understood as I meant it to be. @andrewkirk partially answered the previous puzzle, not this one.

 

[bob012345]

Can I ask a dumb question... what does the notation $\{i ,j ,k = 1,n \}$ mean?

It's not a dumb question. It means rectangular box's (right cuboids) with sizes ranging from 1 to n in each direction. So, given a cube where $n=2$ (a 2x2x2 cube), the lengths of the boxes along the different directions vary from 1 to 2 in all combinations. You would have boxes from 2x2x2, 2x2x1, 2x1x1, 1x2,2... and the rest down to 1x1x1 within a 2x2x2 cube. If you pick a set of axes such as {$x,y,z$}, these represent both the sizes and orientations of the boxes.

 

[etotheipi]

Ah okay, thanks for clarifying. Is that standard notation? Seems like it might be clearer to write something like if $(i, j, k)$ is a tuple containing the side lengths of a particular cuboid, then the set of available cuboids are$$C = \{(i, j, k) : i, j, k \in [1,n]\cap \mathbb{N}\}$$but of course, this isn't important to the question at hand

 

[bob012345]

Ah okay, thanks for clarifying. Is that standard notation? Seems like it might be clearer to write something like if $(i, j, k)$ is a tuple containing the side lengths of a particular cuboid, then the set of available cuboids are$$C = \{(i, j, k) : i, j, k \in [1,n]\cap \mathbb{N}\}$$but of course, this isn't important to the question at hand

Thanks. What does the last part {$\cap \mathbb{N}$} mean? The lengths are all integers for this problem.

 

[etotheipi]

Thanks. What does the last part {$\cap \mathbb{N}$} mean? The lengths are all integers for this problem.

The set $[1,n]\cap \mathbb{N}$ contains the natural numbers from $1$ to $n$; I just write it like this because $[1,n]$ on its own also contains all of the non-integers within that interval, so it's necessary to take the intersection with the natural numbers.

 

[bob012345]

The set $[1,n]\cap \mathbb{N}$ contains the natural numbers from $1$ to $n$; I just write it like this because $[1,n]$ on its own also contains all of the non-integers within that interval, so it's necessary to take the intersection with the natural numbers.

Thanks. I originally specified $n$ as an integer. I assumed it was clear {$i,j,k$} were integers too.

 

[andrewkirk]

I assumed that by 'cuboid' the OP meant a generalisation of the notion to numbers of dimensions other than 3. I answered on that basis. On returning and seeing the discussion, I see they mean by 'cuboid' what I have always known by the name 'rectangular prism'. I was not aware that some now use 'cuboid' as a synonym for that. Perhaps I'm showing my age!

For a rectangular prism with sides of integer lengths $a\le b\le c$ the number of cubes that can fit inside it will be:
$$\sum_{i=1}^a (a-i+1)(b-i+1)(c-i+1)$$
This uses the same reasoning as above.

Observe that for $a=b=c$ this reduces to the formula for when the containing shape is a cube.

WHOOPS! I just noticed the question is asking to count the cuboids/rec prisms within a cube rather than the other way around, which is what I did above in this post. I'll think again and edit this.

EDIT: For a cube with side length $m$, the number of rec prisms that can fit inside will be:
$$\sum_{i=1}^m\sum_{j=1}^m\sum_{k=1}^m (m-i+1)(m-j+1)(m-k+1)
$$
$$= \left(\sum_{i=1}^m (m - i + 1) \right)
\left(\sum_{j=1}^m (m - j + 1) \right)
\left(\sum_{k=1}^m (m - k + 1) \right)
$$
$$
=
\left(\sum_{k=1}^m (m - k + 1) \right)^3
=
\left(m(m+1) - m(m+1)/2 \right)^3
=
\left(m(m+1)/2 \right)^3
=
\frac18 m^3(m+1)^3
$$
I checked this for containing cubes of sides 1, 2 and 3 it seems to be correct for those.

 

[bob012345]

I assumed that by 'cuboid' the OP meant a generalisation of the notion to numbers of dimensions other than 3. I answered on that basis. On returning and seeing the discussion, I see they mean by 'cuboid' what I have always known by the name 'rectangular prism'. I was not aware that some now use 'cuboid' as a synonym for that. Perhaps I'm showing my age!

For a rectangular prism with sides of integer lengths a≤b≤c the number of cubes that can fit inside it will be:
∑i=1a(a−i)(b−i)(c−i)
This uses the same reasoning as above.

Observe that for a=b=c this reduces to the formula for when the containing shape is a cube.

WHOOPS! I just noticed the question is asking to count the cuboids/rec prisms within a cube rather than the other way around, which is what I did above in this post. I'll think again and edit this.

I'm looking forward to your solution so then I can post mine. Hopefully we will match.

 

[bob012345]

I assumed that by 'cuboid' the OP meant a generalisation of the notion to numbers of dimensions other than 3. I answered on that basis. On returning and seeing the discussion, I see they mean by 'cuboid' what I have always known by the name 'rectangular prism'. I was not aware that some now use 'cuboid' as a synonym for that. Perhaps I'm showing my age!

For a rectangular prism with sides of integer lengths $a\le b\le c$ the number of cubes that can fit inside it will be:
$$\sum_{i=1}^a (a-i+1)(b-i+1)(c-i+1)$$
This uses the same reasoning as above.

Observe that for $a=b=c$ this reduces to the formula for when the containing shape is a cube.

WHOOPS! I just noticed the question is asking to count the cuboids/rec prisms within a cube rather than the other way around, which is what I did above in this post. I'll think again and edit this.

EDIT: For a cube with side length $m$, the number of rec prisms that can fit inside will be:
$$\sum_{i=1}^m\sum_{j=1}^m\sum_{k=1}^m (m-i+1)(m-j+1)(m-k+1)
$$
$$= \left(\sum_{i=1}^m (m - i + 1) \right)
\left(\sum_{j=1}^m (m - j + 1) \right)
\left(\sum_{k=1}^m (m - k + 1) \right)
$$
$$
=
\left(\sum_{k=1}^m (m - k + 1) \right)^3
=
\left(m(m+1) - m(m+1)/2 \right)^3
=
\left(m(m+1)/2 \right)^3
=
\frac18 m^3(m+1)^3
$$
I checked this for containing cubes of sides 1, 2 and 3 it seems to be correct for those.

Yes, I get the exact same final answer $(m(m+1)/2)^3$ using $m$ for the size of the cube. Not sure how you got {$m - k +1$} term in $$\left(\sum_{k=1}^m (m - k + 1) \right)$$

My series was simply $$\left(\sum_{k=1}^m k \right)^3$$ and since $$\sum_{k=1}^m k \ =(m(m+1)/2)$$ then $$\left(\sum_{k=1}^m k \right)^3 =(m(m+1)/2)^3$$

My first four values are 1, 27, 216 and 1000 for cubes for 1x1x1 to 4x4x4. I'll post a longer response later describing it after I digest your work. Thanks for doing it!

EDIT: I see where you got that {$m - k +1$} term. That's what I did to get the number of what I called degrees of freedom to multiply out to get the number of occurrences of each size but that step became unnecessary when I noticed all those degree of freedom terms were just the list of sizes in reverse so I just multiplied the sizes directly and they added up to the same total. And it can easily be shown that; $$\ \sum_{k=1}^m (m - k + 1) \ = \ \sum_{k=1}^m k \ $$

 

[bob012345]

Here was my original logic for how many cuboids can be drawn in a cube.

We need the number of possible cuboid sizes, the number of orientations of each size and the number of positions each cuboid of such size and orientation can take. Then we need to put that in a compact form. Note also that the total number of cuboids includes all the possible cubes as well but it is trivial to subtract those out if you wanted to know only how many non-cubes there were. In this case, they are included because they are also cuboids.

First, the number of possible sizes. For an $n$x$n$x$n$ cube, this is $n^3$. So, there are $n^3$ possible sizes which include both the size and all orientations of each size. The list is just all the permutations of a set $(i,j,k)$ where each integer ranges from 1 to $n$. But how do we figure out how many of each size exists? We consider how many degrees of freedom in each direction each size has by noticing that the number of positions each box has is related to the length in each direction. For example, if the length is equal to n along some direction, there is only one position it can take in that direction so we can call the degree of freedom 1. If the length is $n - 1$ there are 2 positions so the freedom is 2. The degree of freedom is always $n+1 - length$ in a given direction. For example, for a 4x4x4 cube with a certain cuboid of length 2 units in the $x$ direction, the degrees of freedom in the $x$ direction is 4+1-2=3. There are 3 positions it can take along the $x$ axis. The number of cuboids of a certain size and orientation is given by the product of it's degrees of freedom. For example, in the previous cube of edge length 4, a cuboid of size {2,2,3} has degrees of freedom of {3,3,2} thus 3x3x2=18 cuboids of that size and orientation. There will also be 18 for each orientation. (Note that the number of orientations of a given size depends on whether there are 1, 2or 3 planes with square faces. For 3 it's a cube and there is only 1 orientation. For 2 there are 3 orientations and for 1 there are 6 orientations.)Next we notice that the list of degrees of freedom is just the list of sizes upside down. We can just save a step and multiply the list of sizes out. Now all we have to do is add them all up.

Thus the products of all possible sizes is;

$\left(\sum_{k=1}^n k \right)$ x$\left(\sum_{k=1}^n k \right)$ x$\left(\sum_{k=1}^n k \right)$ =$\left(\sum_{k=1}^n k \right)^3$​

This is in contrast to sum of $\ \sum_{k=1}^n k^3 \$ for the number of cubes with a cube.

We further note that $\ \sum_{k=1}^n k \$ can be expressed in closed form as;
$$\ \sum_{k=1}^n k \ = n(n+1)/2$$ (which happens to also be the number of integer line segments in a line of length $n$)

giving our final formula for the total number of cuboids in a cube as; $$\left(\sum_{k=1}^n k \right)^3 = (n(n+1)/2)^3$$ in contrast to the number of cubes in a cube as; $$\ \sum_{k=1}^n k^3 \ = (n(n+1)/2)^2$$

Similarly, the number of squares in a square is; $$\ \sum_{k=1}^n k^2 \ = n(n+1)(2n+1)/6$$ while the number of rectangles in a square is; $$\left(\sum_{k=1}^n k \right)^2 = (n(n+1)/2)^2$$

Likewise, extending these to the forth dimension, the number of hypercuboids in a hypercube is;
$$\left(\sum_{k=1}^n k \right)^4 = (n(n+1)/2)^4$$ in contrast to the number of hypercubes in a hypercube as @andrewkirk pointed out goes as; $\ \sum_{k=1}^n k^d \$
which in this case for $d=4$ is; $$\ \sum_{k=1}^n k^4 \ = (n(n+1)(2n+1)(3n^2 +3n -1)/30)$$

 

[bob012345]

As an aside, the closed form for @andrewkirk's series solution for cubes within a cuboid of sides {$a,b,c$} where $a≤b≤c$ is;
$$\ \sum_{i=1}^a (a - i + 1)(b - i + 1)(c - i + 1) \ = a(a + 1)[a(a - 1) + 2(b + c) + 2(3bc - ab - ac) ]/12$$ For small $a$ it might be easier to work out the series directly but for $a≥7$ the formula may be easier.