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

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

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/
```
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