5
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ You're doing well. Google "inclusion and exclusion". $\endgroup$ – saulspatz Jan 23 at 15:35
  • $\begingroup$ @saulspatz Thanks for the answer! I think I was able to solve the question after reading about that principle! $\endgroup$ – robeng Jan 23 at 16:42
  • $\begingroup$ Welcome to MSE! $\endgroup$ – saulspatz Jan 23 at 18:13
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanks for the answer! I have a quick question if you have time to answer. How did you decide on all of your chooses, 3 choose 0, etc. When I calculate their respected values, I understand why I would have those values. But I do not understand the reasoning behind the specific chooses. $\endgroup$ – robeng Jan 24 at 18:02
  • $\begingroup$ @robeng This is because of the symmetry beween the colors. The coefiicient $\binom nk$ just counts the number of ways to choose $k$ colors out of $n$ (in this case $k$ colors joined in a sequence of 5). Look also here. $\endgroup$ – user Jan 24 at 18:17
2
$\begingroup$

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*}

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