Laying Paving Stones

Date: 11/28/2001 at 09:04:25
From: Brian
Subject: Sequences - problem

My son is stuck on his course work. Can you help with finding the 
relation for the following sequence that relates to the number of ways 
that paving stones can be laid to make a 3-foot-wide path using 3-foot 
by 1-foot stones?

Length of path  5  6  7   8  9
Number of ways  4  6  9  13 19

We are unable to find the relation and hence can not move on 
generalising the relation for the nth term. Have we got the number of 
ways right? Any ideas on how to proceed?

Date: 11/28/2001 at 13:09:12
From: Doctor Peterson
Subject: Re: Sequences - problem

Hi, Brian.

I always prefer to look not just at the numbers you get, but at HOW 
you got the numbers. A good way of counting often contains within 
itself a rule that can be used to describe the relation. If you just 
tried randomly to find all the ways you could make a path, then you 
can't be sure of your numbers, and have not learned much about where 
they come from. But if you looked for an orderly method, then you are 
close to a solution.

We might do better starting with a one-foot path, because the rule 
often shows up best with the simplest numbers (though it might get a 
little more complicated for larger numbers):

    Length: 1  2  3  4
    Ways:   1  1  2  

I haven't worked out the number for a 4-foot path yet. How can I make 
this counting easy? I would take it one stone at a time: once I've 
placed the first stone, how many ways are there to place the rest? The 
first stone can be either lengthwise or crosswise:

    +-+-+-+-+      +-+-+-+-+
    |=====  |      ||      |
    |=====  |  or  ||      |
    |=====  |      ||      |
    +-+-+-+-+      +-+-+-+-+

If it is lengthwise, the space next to it can only be filled with 
two more lengthwise stones, as shown. In either case, you now have a 
smaller path left to fill in, either 1 foot or 3 feet long. But we 
already know how many ways there are to do that! So the number of 
ways to make a 4-foot path is the sum of the ways to make a 1-foot 
and a 3-foot path. I can fill in the missing space with "3":

    +-+-+-+-+      +-+-+-+-+      +-+-+-+-+
    |===== ||      || =====|      || | | ||
    |===== ||  or  || =====|  or  || | | ||
    |===== ||      || =====|      || | | ||
    +-+-+-+-+      +-+-+-+-+      +-+-+-+-+
    \_______/      \______________________/
        1                      2

Now, can you see a way to use this method, first to check the numbers 
you have, and then to find a recursive formula for the sequence?

Work this out, and then look at this answer to a similar problem:

   Brick Patterns
   http://mathforum.org/dr.math/problems/jessi9.17.97.html   

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/