Rectangular Solids from Blocks

Date: 09/25/98 at 02:43:32
From: David Purins
Subject: Rectangular Solids made from "n" blocks?

I am a mathematics teacher in Alice Springs (Central Australia). I 
have set a maths project, the solution to which evades me. 

How many rectangular solids can be made from "n" cube shaped blocks?

For example, with 30 blocks there are:

   1 x 1 x 30
   1 x 2 x 15
   1 x 3 x 10
   1 x 5 x 6
   2 x 3 x 5

We are looking for a formula. I'm thinking that it will be based on 
prime factors and combinations:

   Number of prime factors       1   2   3   4
   Number of rectangular solids  1   2   5  14

I got these from using different prime numbers (2 x 3 x 5 x 7 for 
example) to produce numbers of blocks (210 in this case). Then put the 
prime numbers in to three different columns to represent the three 
dimensions.

Date: 09/25/98 at 10:57:19
From: Doctor Mitteldorf
Subject: Re: Rectangular Solids made from "n" blocks?

Dear David,
 
Just a message before we begin. Even if you don't know the solution to 
a problem, you can still present your thinking process to the class - 
it's far more advanced and more sophisticated than theirs, and they 
can learn from the way you approach a problem and the way you follow a 
lead until it reaches a dead end, then go back and try another lead.
Real mathematicians working on real problems are constantly trying 
this and that. They wouldn't get anywhere if they weren't allowed to 
make false starts. Students need to be encouraged to follow their 
thinking where it leads, constantly evaluating and re-evaluating to 
see if they are on the right track.  

On to prime factors. I'm going to take you through my thought process, 
and I've made some progress, but I don't have a complete solution for 
you.

If a number has n prime factors, no duplicates, then each side of the 
rectangular solid can use none of these (length 1) or all of these 
(length p1*p2*...*pn) or any combination in between. The number of 
ways of doing this is the same as the answer to the question, "how 
many ways are there to apportion n objects among 3 separate bins?"  
Each bin may contain any number of the objects (including zero) but 
every one of the n objects must be in one of the bins. Well, the first 
object can be in any of the n bins, the second object can be in any of 
the n bins, etc - that's 3^n different ways of apportioning the 
objects. However, the bins themselves need to be regarded as 
indistinguishable - that corresponds to the fact that a block with 
dimension r*s*t is not different from a block s*t*r. So you need to 
divide by the number of orderings of 3 objects, namely 6. The answer 
this leads to is 3^n/6.  But wait a minute, (thought I). 3^n isn't 
even divisble by 6. What's going on? I tried a simple example, (2 
factors: 6 = 2*3) and saw what it was.

Here's the problem: Even though I took care to say "all different" 
factors, there's still the possibility that there are two empty bins 
(two sides = 1), and these haven't really been counted six times, 
though we're dividing by 6 as if they had been. Fortunately, this case 
is easy to isolate: There are never 3 sides equal to 1. Two sides = 1 
can happen in only 3 ways: each of the 3 sides can be the one that's 
not = 1. So there are 3 cases that should have been counted as 1 when 
instead they were divided by 6 and counted as 1/2. The solution is to 
add 1/2. So I get (3^n+3)/6 as an answer for the case where all the 
factors are different. This is an integer, and it seems to work for 
the case n = 2 and n = 3, so I have some confidence in it.
 
Now let's jump to the case where all the n prime factors are the same 
- say, for example, 2^n or 7^n. This becomes the problem of 
apportioning n indistinguishable objects in 3 indistinguishable bins. 
I learned how to do this just the other day from one of Doctor 
Anthony's answers on this Web site:

   http://mathforum.org/dr.math/problems/chris9.16.98.html   

Think of putting your n objects on the belt at the grocery checkout, 
along with two dividers.  

   ooo|oo|ooooooo

There are n+2 objects on the belt, and they can be ordered in (n+2)! 
different ways.  But the ordering of the n objects doesn't matter 
(remember - they're factors that are all the same). Also, the ordering 
of the 2 dividers doesn't matter. So you should divide by n!2!. The 
result is (n+2)(n+1)/2.   

But this isn't right either. We have the same ordering problem as 
above, which makes us want to divide by 6, but we can't divide by 6 
because (n+2)(n+1)/2 isn't necessarily divisible by 6, and on closer 
inspection we see that we haven't overcounted all possibilities by a 
factor of 6, just the ones where all three sides are of different 
lengths. It's harder now to count which cases have two sides (or 
possibly 3 sides) that are the same.

I'm going to go back now to try a different approach. Suppose we count 
ways to insert the dividers between the o's such that the number of 
o's is decreasing monotonically from left to right. For example, take 
n = 7 o's: then the first group could hold 3, 4, 5, 6, or 7. If it 
held 3, then the second group could only be 3; if it held 4, then the 
second group could be 3 or 2; if it held 5, the second group could be 
2 or 1; if it held 6, the second group must be 1; and if it held 7 
then the second group must be 0. This means that for 2^7 blocks, there 
are 7 different ways to make rectangular solids. But it's not clear to 
me yet what the pattern is, or how to generalize to 2^n blocks. 
Furthermore, when we've finished that, we still have to deal with 
those in-between cases where the prime factors aren't all different 
and aren't all the same.

I'm going to stop here for now. For the present, I hope this has been 
as stimulating for you as it has been for me. 

- Doctor Mitteldorf, The Math Forum
  http://mathforum.org/dr.math/