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

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

Associated Topics:
High School Permutations and Combinations
High School Sequences, Series

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