13
$\begingroup$

In how many ways can we colour $n$ baskets using up to $r$ colours such that no two consecutive baskets have the same colour and the first and the last baskets also have different colours?

For example, if we take $N=5$ and $r = 4$, and represent the colours by $R,B,Y$ and $G$, then $\langle R,Y,B,G,Y\rangle$ is a valid arrangement whereas $\langle R,R,B,G,Y \rangle$ and $\langle G,B,R,Y,G\rangle$ aren't.

It's is not difficult to solve this one by brute force; however, I would like to see a combinatorial approach. Any thoughts?

$\endgroup$
  • $\begingroup$ can someone give a brute force approach?? $\endgroup$ – user43585 Oct 4 '12 at 10:38
12
$\begingroup$

Let $a_n$ be the number of arrangements in which the first and last basket have different colours, and $b_n$ the number of arrangements in which they have the same colour, where in either case adjacent baskets can't have the same colour. Then by adding an admissible basket at the end of such an arrangement we obtain the recurrence

$$ \begin{align} a_{n+1}&=(r-2)a_n+(r-1)b_n\;,\\ b_{n+1}&=a_n\;, \end{align} $$

and substituting the second equation into the first yields

$$ a_{n+1}=(r-2)a_n+(r-1)a_{n-1}\;. $$

The characteristic equation is

$$ \lambda^2-(r-2)\lambda-(r-1)=0\;, $$

with solutions $\lambda=-1$ and $\lambda=r-1$. Thus we have

$$ a_n=c_1(-1)^n+c_2(r-1)^n\;, $$

and the initial conditions $a_1=0$ and $a_2=r(r-1)$ yield

$$ -c_1+c_2(r-1)=0\;,\\ c_1+c_2(r-1)^2=r(r-1) $$

with solution $c_1=r-1$, $c_2=1$. The desired number of arrangements is therefore

$$ a_n=(-1)^n(r-1)+(r-1)^n\;. $$

To get the number of arrangements that use all $r$ colours, you can use inclusion/exclusion:

$$ \sum_{k=0}^r(-1)^{r-k}\binom rk\left((-1)^n(k-1)+(k-1)^n\right)\;, $$

and the sum over the first term vanishes, leaving

$$ \sum_{k=0}^r(-1)^{r-k}\binom rk(k-1)^n\;. $$

$\endgroup$
  • $\begingroup$ Why? To get the number of arrangements that use all r colours, you can use inclusion/exclusion: $$\sum_{k=0}^r(-1)^{r-k}\binom rk\left((-1)^n(k-1)+(k-1)^n\right)\;,$$ I don't understand. $\endgroup$ – Schwarz Nov 7 '12 at 13:09
  • $\begingroup$ @Schwarz: Do you understand inclusion/exclusion in general? $\endgroup$ – joriki Nov 7 '12 at 22:15
  • $\begingroup$ I don't understand inclusion/exclusion in general $\endgroup$ – Schwarz Nov 8 '12 at 2:29
  • 1
    $\begingroup$ @Schwarz: It would have been more efficient to say that in the first place instead of letting me guess what it is about that statement that you don't understand. This isn't the right place to explain inclusion/exclusion to you; I'd suggest that you read the Wikipedia article, and if you still have a question afterwards, you can ask it on this site as a separate question. $\endgroup$ – joriki Nov 8 '12 at 5:59
  • $\begingroup$ This is now the subject of a separate question. $\endgroup$ – joriki Nov 8 '12 at 12:35

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.