Associated Topics || Dr. Math Home || Search Dr. Math

### 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?

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/
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search