2
$\begingroup$

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.

picture

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – JMoravitz Aug 25 '16 at 8:55
0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.