Post Number:**#5** by **Masum** » Mon Dec 23, 2013 8:39 pm

I found two solutions for this problem. One is direct combinatorial and the other uses recursion. For both, we just need to consider $m=\dfrac n5$ instead of $n$. Just divide all lengths by $5$. Thus, the length of a minibus is $1$ and a bus has $2$. And, we have to find $f(m)$.

Using recursion: Let's say we have all the values $f(0),f(1),...,f(m-1)$. Now we find the value of $f(m)$. Then, we have two choices, we can use a minibus(length $1$) or bus(length $2$). If we use a minibus, then we have to find the number of ways with length $m-1$ i.e. this gives us $f(m-1)$ and since there are $k$ colors to paint a minibus, this options yields $kf(m-1)$. Now, similarly, if we use a bus, there are $l$ colors to paint a bus and it takes length $2$ leaving to find $f(m-2)$. So this option yields $lf(m-2)$. Thus, $f(m)=kf(m-1)+lf(m-2)$.

Direct combinatorial solution: Let's say we will take $x$ minibus(es) and $y$ bus(es). Then obviously $x+2y=m$. All solutions to this are of the type $(m-2t,t)$. So for a fixed $i$, we have to take $m-2i$ minibus(es) and $i$ bus(es). Now the minibus(es) can be colored in $k^{m-2i}$ ways(why?). And the buses can be colored in $l^i$ colored(same reasoning). Thus for a fixed permutation of the buses they can be colored in $k^{m-2i}l^i$ ways. Again, since they can be permuted themselves in

\[\dfrac{(m-2i+i)!}{(m-2i)!i!}=\binom{m-i}i\]

ways, for a fixed $i$, we have a total of $\binom{m-i}ik^{m-2i}l^i$ coloring. Since $i$ can run through $0,1,...,q$ where $q=\left\lfloor\dfrac m2\right\rfloor$(why?) the total number of coloring we have is \[\sum_{i=0}^{q}\binom{m-i}ik^{m-2i}l^i\]

One one thing is neutral in the universe, that is $0$.