A certain diner has parallel parking along the street. Being so popular with mot

Question

A certain diner has parallel parking along the street. Being so popular with motorcyclists, the
parking spots are marked to accommodate the length of a motorcycle. A car can also park there,
and ts just right in two consecutive spots.

(6) A certain diner has parallel parking along the street. Being so popular with motorcyclists, the parking spots are marked to accommodate the length of a motorcycle. A car can also park there, and fits just right in two consecutive spots Let tn denote the number of ways that such a parking strip with n motorcycle spaces can be filled with cars and motorcycles. For example, t 3: (mlm lm), CCC lm), (mICCC). Find a recurrence relation (base case(s) and recurrence) for ttnt. (Hint: consider the last vehicle parked in the strip

Explanation / Answer

Let tn be the number of ways in which n motor cycle spaces can be filled with cars and motor cycles.

therefore, t1 = (m) =1, t2 = (m,m), (cc) = 2, t3 = (m,m,m),(cc,m),(m,cc) =3.

In a similar way, we have t4= 5, t5= 8.

From the above statements, we can write,

t1=1, t2 =2

t3 = t2 + t1

t4 = t3+t2

t5= t4+t3

......

........

tn = tn-1 + tn-2.

now consider there are n+2 spaces to park the vehicles. If the last space is filled by a motorcycle, then the remaining n+1 spaces can be filled in tn+1 ways. Similarly if the last two spaces are filled by a car, the remaining n spaces are occupied by tn ways.

Therefore tn+2 = tn+1 + tn.

This is true for any value of n.

Hence {tn} =1 for n=1,

{tn} = 2 for n=2

{ tn} = tn-1 + tn-2, for n >2.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.