Mike N. answered • 10/09/14

Tutor

5
(3)
Professional Mathematician with homeschool experience

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_{0}= 1, but we can at least agree that A_{1}= 2 (F or C) and A_{2}= 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 byA

_{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_{1}and A_{2}.I hope that helps,

Cheers,

Mike N.

Mike N.

Yes, exactly. Well done!

Report

10/10/14

Marianne A.

10/10/14