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/