Last night I encountered the problem (p. 481) that paraphrases as follows:<\/p>\n
Imagine a car takes two spaces, a motorbike one. Find a recursive function that determines the number of ways to fill n parking slots with motorbikes and cars (assuming no empty slots).<\/p>\n
I played around with the problem for a while, then tried this approach:<\/p>\n
| Number of slots<\/td>\n | Ways to fill them<\/td>\n<\/tr>\n |
| 0<\/td>\n | 1 (no parking at all)<\/td>\n<\/tr>\n |
| 1<\/td>\n | 1 (one motorbike)<\/td>\n<\/tr>\n |
| 2<\/td>\n | 2 (2 mbs or 1 car)<\/td>\n<\/tr>\n |
| 3<\/td>\n | 3 (3 mbs or 1 car, 1 mb (two ways))<\/td>\n<\/tr>\n |
| 4<\/td>\n | 5 (4 mbs or 1 car, 2mbs (three ways) or 2 cars)<\/td>\n<\/tr>\n<\/table>\n The right column in the table above is the Fibonacci (F) sequence: an+2<\/sub>=an+1<\/sub>+an<\/sub>. However, it’s advanced by 1: Typically, F(0)=0, while for this case, F(0)=1. Fibonacci takes the previous number in the sequence, then adds it to the one before that, to give the current one.<\/p>\n In a coming post I’ll discuss the general solution to the sequence above:)<\/p>\n Source:<\/p>\n Grimaldi, Ralph P. Discrete and Combinatorial Mathematics<\/u>. Don Mills: Addison-Wesley, 1994.<\/p>\n |