Cuisenaire Rod Combinations
Date: 11/13/2001 at 09:24:44 From: Betty Subject: Cuisenaire rods My math class is working on a problem using Cuisenaire rods. We are to record 512 different combinations of each level (or color) of rod with the orange rod (the largest) being the last. After 4 hours of manipulating the rods, we have come up with only 359 combinations. My question is: Does a formula exist that can help to find these combinations without literally manipulating the rods? Our hands and eyes would be eternally grateful if you would tell us the secret. Thank you.
Date: 11/13/2001 at 12:03:43 From: Doctor Peterson Subject: Re: Cuisenaire rods Hi, Betty. The question confuses me a little. There is an easy way to get that number 512, which I'll give in a moment in case you want it; but you don't use a "formula" to make an actual list of combinations. You would call this an "algorithm," an orderly method for going through all the possibilities, such as a computer program might use. Therefore, it's not clear to me whether you want the number or the list. But now that I think about it, we can find an algorithm for making the list in the same way I calculate the number, so let's start there, and we'll have both. We want to find, as I understand it, the number of ways to put rods of integral lengths together to form a rod of length N (in your case, 10), counting different orders of the same set of rods as different. We can think about this in reverse: rather than taking a bunch of rods and trying to fit them together, we'll take an N-unit rod and find ways to cut it up into integral-length pieces. There will be N-1 places where you can cut it: 1 2 3 4 5 6 7 8 9 10 +---+---+---+---+---+---+---+---+---+---+ | : : : : : : : : : | +---+---+---+---+---+---+---+---+---+---+ 1 2 3 4 5 6 7 8 9 To choose a way to cut, we simply have to look at each possible place and decide whether to cut there or not. That gives us two ways to answer each of N-1 questions, so there are 2^(N-1) ways to make the cuts. With N = 10, this is 2^9 = 512. Now, do you see the algorithm in this? We can write down a choice of cuts by writing, say, 0 where we cut and 1 where we don't, making a binary number of N-1 digits; we can organize this list by just counting in binary. For N = 4, this gives the following ways to cut, for each of which we can list the lengths of the pieces: binary cuts lengths ------ ------- ------- 000 x x x x 4 001 x x x|x 3+1 010 x x|x x 2+2 011 x x|x|x 2+1+1 100 x|x x x 1+3 101 x|x x|x 1+2+1 110 x|x|x x 1+1+2 111 x|x|x|x 1+1+1+1 If you're not comfortable with counting in binary, you can think of it as a tree: #1 #2 #3 cuts lengths ----- ----- ----- ------- ------- cut x|x|x|x 1+1+1+1 / cut / \ / don't x|x|x x 1+1+2 cut / \ cut x|x x|x 1+2+1 / \ / / don't / \ / don't x|x x x 1+3 ? \ cut x x|x|x 2+1+1 \ / \ cut \ / \ \ / don't x x|x x 2+2 don't \ cut x x x|x 3+1 \ / don't \ don't x x x x 4 You can do the same for your bigger problem; the tree method would be too bulky to actually write down, but might spark some ideas in the class. Another way to make your list would be to choose the first rod (anything from 1 to 10), and for each case try each possible second rod (from 1 to whatever is left), and so on. This will in fact give the same order as my example above. You would think, "If the first rod is 4, we're done. If the first rod is 3, the second must be 1, so we're done. If the first rod is 2, the second can be 2 or 1; ...". This may be easier to get kids to think of themselves; you can make a somewhat different tree to represent it. My cutting trick is typical of the way mathematicians think, turning a hard problem into a more familiar one, but it requires more background knowledge. - Doctor Peterson, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.