Subject: Combinations of Numbers.
Name: Shea
Who are you: Student

Hello,
Here is the problem:
A "train of length 5" is a row of blocks whose combined
length is 5. Here are some examples: 1-2-2, 2-1-2, 1-3-1, 5, 1-4.
If you use identical blocks in a different order,
this is a separate train. How many trains of length 5 are there? Come up
with a formula for the number of trains of length n.

I know all the lengths:

N Combinations
1 1
2 2
3 4
4 8
5 16
6 32

I know the relationship is that the number of your combinations
for the next number will be the combination before doubled. My question
is,...how do I write a formula for that?

-Shea

Shea,

First in the combinations column in your table write each number in terms of its prime factorization.

As for how to develop an expression l et me give you a couple of hints; the first requires knowledge of combinations and the Binomial Theorem, the second answers the problem recursively.

1. Look at the case n = 6. These 6 blocks have 5 spaces between
them. You want to divide the 6 blocks up into consecutive strrings
adding up to 6 in length. To do this think of placing dividers in the
5 gaps. If pCr is the number of ways to choose r things from p things
then you can pick places to insert dividers in the following number of
ways:

0 dividers: 5C0 = 1 way
1 divider: 5C1 = 5 ways
2 dividers: 5C2 = 10 ways
3 dividers: 5C3 = 10 ways
4 dividers: 5C4 = 5 ways
5 dividers: 5C5 = 1 way

In total there are 32 ways. Also note that 5C0 +5C1 + ... +5C5 = 2^5
=32 (recalling the Binomial Theorem). This leads to the general
solution.

2. Again lets do n = 6. (We know the answer for n = 5 is 16.) Again
these 6 blocks have 5 spaces between them. You want to divide the 6
blocks up into consecutive strrings adding up to 6 in length. To do
this think of placing dividers in the 5 gaps. With 5 blocks we had to
place dividers in the 4 gaps. Think of the train of length 5 with the
sixth car as a caboose on the end. For every soluton to the n = 5
problem the caboose is giving us a solution to the n = 6 problem.
Note that you never place a divider right before the caboose in these
16 solutions. Now think of placing a divider between the caboose and
the previous car and consider possibilities fro dividers in the
previous 4 gaps. Why are there 16 again? If you see through this you
will see how to recursively solve the problem.

Penny