# Parking bicycles and cars of many colours

Suppose there is a parking space with $N$ lots. A bicycle takes up 1 lot, while a car takes up 2 consecutive lots. There are $a$ colours for bicycles and $b$ colours for cars. How many ways are there to park cars and bicycles in the parking space if the order and colour matter?

For $N=a=b=2$ there are 6 ways; if $N$ is changed to 1 there are 2 ways. See the picture below. • Have you had any experience with recurrence relations? Would you believe me if I told you it follows the recurrence $f_n = a\cdot f_{n-1} + b\cdot f_{n-2}$? with $f_0=1$ and $f_{-1}=0$ as initial conditions? Depending on the values of $a$ and $b$, nice simplifications can be made for the closed form solution. I will leave it to you to justify why the proposed recurrence relation is in fact the correct one. – JMoravitz Aug 25 '16 at 8:55

So you have that:

For $N=1$ there are $a$ ways to select colour for the one bike.

For $N=2$ there are $a^2$ ways to select colours for two bikes, and $b$ ways to select a colour for one car.   That is $a^2+b$ options in total.

Continuing in this vein we can see:

For $N=3$ you can have three bikes, or a car and a bike.   So there are $a^3+2ab$ options.   (Because there are $\tbinom 20$ ways to select placement for two objects.)

For $N=4$ you can have four bikes, a car and two bikes, or two cars, for a total of $a^4+3 a^2b+ b^2$ options.

In summary, of $\mu(N)$ is the count of options for $N$ parking spaces.

$$\mu(N) =\begin{cases}a &:& N=1 \\ a^2+b &:&N=2\\ a^3+2ab &:& N=3\\ a^4+3a^2b+b^2 &:& N=4 \\ a^5+4a^3b+3ab^2 &:& N=5 \\ a^6+5a^4b+6a^2b^2+b^3 &:& N=6 \\ \vdots &\vdots& \vdots \\ \sum_{j=0}^k\bbox[pink,0.25ex,border:0.1ex dashed magenta]{\qquad\qquad?} & : & N=2k, k\in\Bbb N_+ \\ \sum_{j=0}^k\bbox[pink,0.25ex,border:0.1ex dashed magenta]{\qquad\qquad?} & : & N=2k+1, k\in\Bbb N_+ \end{cases}$$

Can you see the pattern?

While this problem is quite simple it can nonetheless perhaps serve as motivation to learn more about generating functions. We have by inspection using $z$ for lots, $u$ for bicycles and $v$ for cars that these are represented by the generating function

$$(1+uz+u^2z^2+\cdots) \left(\sum_{q\ge 0} (vz^2+v^2z^4+\cdots)^q (uz+u^2z^2+\cdots)^q\right) \\ \times (1+vz^2+v^2z^4+\cdots).$$

This simplifies to

$$\frac{1}{1-uz} \left(\sum_{q\ge 0} \frac{(vz^2)^q}{(1-vz^2)^q} \frac{(uz)^q}{(1-uz)^q}\right) \frac{1}{1-vz^2} \\ = \frac{1}{1-uz} \frac{1}{1-uvz^3/(1-vz^2)/(1-uz)} \frac{1}{1-vz^2} \\ = \frac{1}{(1-uz)(1-vz^2)-uvz^3} = \frac{1}{1-uz-vz^2}.$$

Now instantiating $u$ to $a$ and $v$ to $b$ we get the generating function

$$\frac{1}{1-az-bz^2}.$$

The characteristic equation of the corresponding recurrence is obtained from $1-a/z-b/z^2 = 0$ or $z^2 = az+b.$ Hence the answer is given by the recurrence $f_n= a f_{n-1} + b f_{n-2}$ matching the result that was obtained by inspection in the comments, which simply says that the rightmost occupant is either a bicycle or a car. Initial values are $f_0=1$ and $f_1=a.$

If we are interested in a closed form we get

$$[z^n] \frac{1}{1-z(a+bz)}.$$

This is $$\sum_{q=0}^n [z^n] z^q (a+bz)^q = \sum_{q=0}^n [z^{n-q}] (a+bz)^q = \sum_{q=0}^n {q\choose n-q} b^{n-q} a^{2q-n}.$$

Let $x,y$ be the number of bicycles and cars resp.

Then, we must have $0\le y \le N/2$ and $N=x+2y$

The number of ways of placing $y$ cars and $x$ bicycles, without considering the colors (that is, considering them identical) is

$${x+y \choose y}={N-y \choose y}$$

If we can choose $a$ colors for the $x$ bicycles and $b$ colors for the $y$ cars, the number of ways is now

$${x+y \choose y} a^x b^y={N-y \choose y}a^{N-2y} b^y$$

Hence the total count is

$$\sum_{y=0}^{\lfloor N/2 \rfloor}{N-y \choose y}a^{N-2y} b^y$$