Combinations of Cubes

Date: 11/07/96 at 12:52:13
From: W.Whistler
Subject: Cuboids and cubes

How many different cuboids can be made from one million connectable 
cubes, using all the cubes?  For instance, there is 1 by 1 by 1000000,
1 by 2 by 500000 etc. etc. Is there an equation to work it out for any 
number of cubes?

Looking forward to your reply,

William Whistler

Date: 11/08/96 at 11:47:12
From: Doctor Tom
Subject: Re: Cuboids and cubes

Hi William,

Well, there's not really a formula to work out the problem, but it is 
a rather standard combinatorial problem.  I can't answer it unless I 
know a little more.  For example, is the 1x1x1000000 cube different 
from a 1x1000000x1 or a 1000000x1x1 cube?  The answer clearly depends 
on what you mean by "different".  Nonetheless, the same techniques can 
be used no matter what.

First, factor the number you're interested in into its prime factors.  
For 1000000, that's 2x2x2x2x2x2x5x5x5x5x5x5.

Now, any solution will consist of three numbers that multiply to give 
1000000, so the three factors have to include all the 2s and 5s above.

An equivalent way of thinking of this is that there are 3 boxes and 
you have six 2s and six 5s to put in the boxes.  How many ways can 
this be done?

Since the 2s and 5s are independent, you can just multiply the number 
of ways to distribute the 2s with the number of ways to distribute the 
5s.

Let's do an exhaustive enumeration of the 2's:

 1 2 3  (box number)
 -----
 6 0 0
 5 1 0
 5 0 1
 4 2 0
 4 1 1
 4 0 2
 3 3 0
 3 2 1
 3 1 2
 3 0 3
 2 4 0
 2 3 1
 2 2 2
 2 1 3
 2 0 4
 1 5 0
 1 4 1
 1 3 2
 1 2 3
 1 1 4
 1 0 5
 0 6 0
 0 5 1
 0 4 2
 0 3 3
 0 2 4
 0 1 5
 0 0 6

There are 28 ways in all.  So there are also 28 ways to distribute the 
5s and thus there are 28x28 = 784 ways.

Actually, the number of ways to put k things in n boxes is given by 
(n+k-1) choose (n-1). In this case, 8 choose 2 = 8x7/2x1 = 28.

The way I think of this is to imagine the k things in a row, and then 
insert n-1 box edges somewhere in the row.  In the illustration below, 
the 'x's represent things, and the '|'s represent box edges.  If there 
are 8 things in 5 boxes, one way to do it looks like this:

   xxx||xx|xxx|

Everything to the left of the first bar is in the first box. 
Everything between the first and second bars is in the second box, and 
so on, until everything to the right of the last bar is in the last 
box.  The figure above indicates 3 in the first, zero in the second, 2 
in the third, 3 in the fourth, and none in the fifth.

Every representation has n-1 bars and k 'x's.  Each arrangement of 
bars and 'x's represents a different assortment.  So there are n+k-1 
characters in the representation, and you have to pick n-1 of them to 
be box edges.  There are n+k-1 choose n-1 ways to do this.

I don't know any simple way to solve the problem if the distribution
6 0 0 is to be treated the same as 0 6 0 or 0 0 6.  The only approach 
I know of involves looking at "orbits" in a certain permutation group, 
which is something suitable for a senior math major in college.  (Of 
course I mean to solve the problem in general.  You can always 
enumerate the solutions as I did above for a particular number.)

-Doctor Tom,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/