How many ways are there to park cars and motorcycles in a parking lot with 100 spaces, ordered in a row, knowing that a car occupies two spaces and a motorcyle occupies one? (all spaces must be occupied)
All cars and motorcycles are considered equal. When they are parked does not matter, where they are does
I'm trying to build this as a recurrence relation. For small numbers it looks like a Fibonacci sequence, but it's not obvious to me how the number of ways for $n $
spaces builds up on $(n-1)$ and $(n-2)$ spaces
Best Answer
Let $x$ denote the number of cars and $y$ the number of motorcycles in a configuration. Then we have the condition: $$ 2x+y=n $$ where $x,y\geq 0$. This has solutions $x=0,1,...,\lfloor n/2\rfloor$ and $y=n-2x$. For each such solution there will be $$ \binom{x+y}{x}=\frac{(x+y)!}{x!y!} $$ ways to distribute the sequence of $x$ cars among $x+y$ vehicles. Hence the figure becomes $$ P(n)=\sum_{x=0}^{\lfloor n/2\rfloor}\binom{n-x}{x} $$ since $y=n-2x$ implies $x+y=n-x$. Perhaps this can be expressed in some different form which is more neat.
Heureka! It is indeed the Fibonacci sequence: $$ P(n)=P(n-1)+P(n-2) $$ Since you can form all new configurations ending in a motorcycle by adding a motorcycle to the end of one of the $(n-1)$-configs, and similarly all ending in a car by adding a car to the end of one of the $(n-2)$-configs. Those two are necessarily distinct because they end in a different kind of vehicle. Hence we just add them together.