Deje $a_n$ el número de acuerdos en los cuales la primera y la última canasta de tener diferentes colores, y $b_n$ el número de acuerdos en los cuales tienen el mismo color, donde en cualquier caso adyacentes cestas no puede tener el mismo color. A continuación, mediante la adición de la admisibilidad de una canasta al final de un arreglo se obtiene la recurrencia
$$
\begin{align}
a_{n+1}&=(r-2)a_n+(r-1)b_n\;,\\
b_{n+1}&=a_n\;,
\end{align}
$$
y sustituyendo en la segunda ecuación en la primera rendimientos
$$
a_{n+1}=(r-2)a_n+(r-1)a_{n-1}\;.
$$
La ecuación característica es
$$
\lambda^2-(r-2)\lambda-(r-1)=0\;,
$$
con las soluciones de $\lambda=-1$$\lambda=r-1$. Así tenemos
$$
a_n=c_1(-1)^n+c_2(r-1)^n\;,
$$
y las condiciones iniciales $a_1=0$ $a_2=r(r-1)$ de rendimiento
$$
-c_1+c_2(r-1)=0\;,\\
c_1+c_2(r-1)^2=r(r-1)
$$
con la solución $c_1=r-1$, $c_2=1$. El número deseado de arreglos es, por tanto,
$$
a_n=(-1)^n(r-1)+(r-1)^n\;.
$$
Para obtener el número de arreglos que uso todos los $r$ colores, se puede utilizar de inclusión/exclusión:
$$
\sum_{k=0}^r(-1)^{r-k}\binom rk\left((-1)^n(k-1)+(k-1)^n\right)\;,
$$
y la suma del primer término desaparece, dejando a
$$
\sum_{k=0}^r(-1)^{r-k}\binom rk(k-1)^n\;.
$$
