Find a recurrence relation..

Question

Find a recurrence relation for the number of ways to arrange cars in a row with spaces if we can use Cadillacs or Hummers or Fords. A Hummer requires two spaces,whereas a Cadillac or a Hummer requires just one space.

Answer 1

Hi Thorgerdur,

 

I think I will assume that a Hummer requires two spaces, whereas a Cadillac or Ford only requires one.  I think you have a typo in your question.

 

We'll use induction here.  Let's denote a Ford by F, Cadillac by C, and Hummer by H.  So FCHC, for example would correspond to a Ford, Cadillac, Hummer, and Cadillac in that order.  Let's give ourselves A_i for i = {0,1,...}.  A_i will correspond to the number of ways to arrange cars in a row with i spaces.  Technically we should start with A₀ = 1, but we can at least agree that A₁ = 2 (F or C) and A₂ = 5 (FC, FF, CF, CC, or H).

 

Now then, what about A_i?  Well, we will ask ourselves what the last car in the row is.  If the last car in the row is F then there are i-1 cars arranged somehow, followed by an F.  How many ways are there for that to happen?  Well, the i-1 cars can be arranged in A_i-1 ways, followed by an F.  Thus, there are A_i-1 arrangements where the last car is an F.  Similarly, there are A_i-1 arrangements where the last car is a C.  The remaining case is an H.  Since an H takes up two spaces, there are i-2 cars arranged somehow, followed by an H.  There are Ai-2 ways that could happen.  So the A_i, the total number of possible arrangements is the total ways an F, C, or H could occur as the last car, which is given by

A_i-1 + A_i-1 + A_i-2

= 2Ai-1 + Ai-2

 

To start off the recursion, you need to know two A_i's in a row, which is why we specified A₁ and A₂.

 

I hope that helps,

 

Cheers,

Mike N.