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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.