Parking bicycles and cars of many colours

Question

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.

Answer 1

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?

Answer 2

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}.$$

Answer 3

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$$