Problem 6. UTD Parking (10 points) To help with parking issues, UTD has just cre

Question

Problem 6. UTD Parking (10 points) To help with parking issues, UTD has just created a new parking lot consisting of n spaces in a single long row. Rather than creating separate spots for motorcycles and cars, management decided to make all n spaces small, such that motorcycles will occupy one space and cars will occupy two. Write a recurrence P(n), counting the number of possible ways to park cars and motorcycles in this parking lot such that the lot is full. Specifically for a full lot we can write a string mccmmmcmc.... representing the left to right ordering of appearance of 'm'otorcycles and 'c'ars, and we wish to count the number of distinct strings which represent a full lot. For simplicity, you can assume P(0) = 1. Hint: The recurrence should have a simple form. Also, don't forget to include base cases.

Explanation / Answer

It is similar to problem regarding number of ways to climb n steps on a stair with either one steps or 2 steps at a time.

Base cases :

P(1) = 1 (Only motorcycle can be parked)

P(2) = 2 (Either 2 motorcycles or a car can be parked)

P(3) = P(2) + P(1) (Because either we can park a car in the existing space or we can park a bike)

So, recurrence relation would be :

P(n) = P(n-1) + P(n-2)

Hence our problem looks like :

P(n) = P(n-1) + P(n-2), n > 0

1, n = 0

0, n < 0

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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