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