Combinatorics - letters forbidden sequence.

Question

I am trying to solve a question. I have 15 pens, where 5 are colored in Red, 5 in Green, and 5 in Blue. How many combinations can I order these pens so that there is no sequence of 5 pens with the same color? For instance, the combination RRRRG GGGBB BBRGB is okay because there is no sequence of pens where 5 colors are after each other. The combination RRRRR ... would need to be excluded because 5 red pens are in a row.

My initial strategy was to count the total number of combinations to build with these pens and then subtract the total number of combinations where at least 5 colors are in sequence.

The total number of combinations:

$$\frac{15!}{(5!*5!*5!)} = 756756$$

The issue I am having is how to create all the combinations where 5 colored pens are in order. I have tried to do something like this:

Group the sequence RRRRR into one symbol. Now, calculate every combination with this RRRRR symbol and the other symbols.

$$\frac{11!}{5!*5!}=2772$$

The problem here is that if I multiplied this with 3 to get the combinations from every color, there would be many duplicated combinations.

Any help on how I could solve this is much apprecited.

Answer 1

Here is a generating function approach. Words with no consecutive equal characters at all are called Smirnov words or Carlitz words. See example III.24 Smirnov words in Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for more information.

A generating function for the number of Smirnov words over a ternary alphabet is given by \begin{align*} \left(1-\frac{3z}{1+z}\right)^{-1}\tag{1} \end{align*} Since each letter may occur in runs with length $\leq 4$ we substitute \begin{align*} z\to z+z^2+z^3+z^4=\frac{z\left(1-z^4\right)}{1-z}\tag{2} \end{align*}

We substitute (2) in (1) and obtain the generating function $f(z)$: \begin{align*} \color{blue}{f(z)}=\left(1-\frac{3\,\frac{z\left(1-z^4\right)}{1-z}}{1+\frac{z\left(1-z^4\right)}{1-z}}\right)^{-1} \color{blue}{=\left(1-\frac{3}{1+\frac{1-z}{z\left(1-z^4\right)}}\right)^{-1}}\tag{3}\\ \end{align*}

The coefficient $[z^{15}]f(z)$ gives the number of all words of length $15$ built from the alphabet $\mathcal{V}=\{R,G,B\}$ which do not contain characters with runs of length $5$. Since we are interested in the number of words which contain five $R$s, five $G$'s and five $B$'s we parametrize the function $f(z)$ and obtain from (3) with some help of Wolfram Alpha the number of valid words:

\begin{align*} \color{blue}{[R^5G^5B^5z^{15}]f(z;R,G,B)} &=[R^5G^5B^5z^{15}]\left(1-\sum_{q\in\{R,G,B\}}\frac{1}{1+\frac{1-qz}{qz\left(1-(qz)^4\right)}}\right)^{-1}\\ &\,\,\color{blue}{=748\,560} \end{align*}

Answer 2

You are very close to the correct solution. The metod of choice for solving such problems is the principle of inclusion and exclusion. Applying it to the problem and taking into account the symmetry between the colors one obtains: $$ \binom30\frac{15!}{5!5!5!}-\binom31\frac{11!}{5!5!1!}+\binom32\frac{7!}{5!1!1!}-\binom33\frac{3!}{1!1!1!}=748560. $$