Permutations and combinations – pens of same color

If you have five blue, five red and five black pens (which show the differences by the colors), in how many ways you can put the pens in a row where there is never same color next to each other?

I've made a solution but I'm not sure it's the correct answer. Here is my solution: $$3\binom{10}5=756$$ $$756756 - 756 = 756000$$

Solution 1:

This is a more basic explanation on how to build Blatter's generation function. Following the reasoning and convention in his answer, pretend the we have an unlimited supply of blue balls $($represented by $x)$ and of red balls $($represented by $y)$. A valid filling for one of the middle slots has one of the forms:

$\qquad(1)$: a (possibly empty) sequence of $xy$'s followed by an $x$. This result in terms like $x, xyx, xyxyx, \dots$

$\qquad(2)$: a (possibly empty) sequence of $xy$'s preceded by $y$. This result in terms like $y, yxy, yxyxy, \dots$

$\qquad(3)$: a (possibly empty) sequence of $xy$'s preceded by an $xy$. This result in terms like $xy, xyxy, xyxyxy, \dots$

$\qquad(4)$: a (possibly empty) sequence of $xy$'s followed by $x$ and preceded by $y$. This result in terms like $yx, yxyx, yxyxyx, \dots$

These $4$ cases cover all possibilities.

When building a generating function, terms representing a required choice $\big($like choosing what to fill a blank $\_$ with, or following $\text{SEQ}(xy)$ with an $x$ in case $(1)\big)$ are multiplied, while term representing mutually exclusive possibilities are added.

With this mind, for any symbol $z$ a (possibly empty) sequence of $z$'s is given (in terms of formal power series/generating functions) by

$$1+z+z^2+z^3+\dots = \frac1{1-z}.\tag{$**$}$$

Hence, the corresponding term for each possibility above is

\begin{array}{c|c} \text{Case}&\text{Term}\\ \hline 1&\frac{x}{1-xy}\\\hline 2&\frac{y}{1-xy}\\\hline 3&\frac{xy}{1-xy}\\\hline 4&\frac{yx}{1-xy}\\ \end{array}

Of course the terms for $(3)$ and $(4)$ are equal, but I wrote their numerators in different orders to highlight that they represent different objects: $xy*\text{SEQ}(xy)$ for $(3)$ and $y*\text{SEQ}(xy)*x$ for $(4)$.

It thus follows that the general term for a middle slot

$$\frac{x}{1-xy}+\frac{y}{1-xy}+\frac{xy}{1-xy}+\frac{yx}{1-xy}=\frac{x+y+2xy}{1-xy}, \tag{$\triangle$}$$

and since we must fill $4$ of those slots our generating function will feature $(\triangle)$ to the fourth power.

Now, the endpoint slots also admit one possibility that is unaccounted for, namely that it is empty $($represented by $x^0y^0=1)$. Like we said before, one way of doing this is simply adding $1$ to $(\triangle)$:

$$1+\frac{x+y+2xy}{1-xy}=\frac{1+x+y+xy}{1-xy}=\frac{(1+x)(1+y)}{1-xy}, \tag{$\square$}$$

Another possibility would have been to consider a modified version of case $(3)$ that accounts for the empty possibility:

$\qquad(3')$: a (possibly empty) sequence of $xy$'s. This result in terms like $1, xy, xyxy, xyxyxy, \dots$

You see, the requirement in $(3)$ for there to be a preceding $xy$ was included specifically to prevent an empty result, so removing it adds the term we were missing. Like we calculated in $(**)$, the term corresponding to case $(3')$ is hence $\frac1{1-xy}$.

Cases $(1)$, $(2)$ and $(4)$ still apply, so our final term for an endpoint slot is

$$\frac{x}{1-xy}+\frac{y}{1-xy}+\frac{1}{1-xy}+\frac{yx}{1-xy}=\frac{1+x+y+xy}{1-xy}=\frac{(1+x)(1+y)}{1-xy},$$

yielding the same answer as before, of course. Since we must fill $2$ endpoint slots, this will be squared in our final generating function.

This covers all slots we had to fill, and hence our generating function is

$$p(x,y)=\frac{\big((1+x)(1+y)\big)^2(x+y+2xy)^4}{(1-xy)^6}$$

Now we turn back to the start. We don't actually have an unlimited supply of blue or red balls -- we are only interested in the case of exactly $5$ blue balls and $5$ red bals. It suffices hence to extract the coefficient of $x^5y^5$ in the power series of $p$ about $(0,0)$.

Solution 2:

Let $\mathsf{B}$, $\mathsf{R}$, and $\mathsf{K}$ denote a Blue, Red, and blacK pen respectively. Then you're looking for “words” over the alphabet $\{\mathsf{B}, \mathsf{R}, \mathsf{K}\}$ in which no two consecutive letters are the same.

These are called Smirnov words, and there's a really cool trick you can do here. Consider the following: given any arbitrary word over the alphabet $\{\mathsf{B}, \mathsf{R}, \mathsf{K}\}$, suppose you “collapse” every run of identical letters into a single occurrence of that letter. Then you get a Smirnov word (word in which no two consecutive letters are the same). In the other direction, suppose you start with a Smirnov word, and replace each letter with some (positive) number of repetitions of that letter. Then, by starting with the appropriate Smirnov word and making the appropriate replacements, you can get absolutely any word.

In terms of generating functions, let $W(x, y, z)$ be the generating function for (arbitrary) words over the alphabet $\{\mathsf{B}, \mathsf{R}, \mathsf{K}\}$, where $x, y, z$ “mark” the occurrences of $\mathsf{B}$, $\mathsf{R}$, $\mathsf{K}$ respectively. (That is, the coefficient of $x^{n_1}y^{n_2}z^{n_3}$ in $W(x, y, z)$ is the number of words with $n_1$ $\mathsf{B}$s, $n_2$ $\mathsf{R}$s, and $n_3$ $\mathsf{K}$s.) And let $S(x, y, z)$ denote the generating function for Smirnov words. Then, what the previous paragraph shows is that (using the fact that the generating function for repeating something a positive number of times looks like $x + x^2 + x^3 + \dots = x/(1-x)$): $$W(x, y, z) = S\left(\frac{x}{1-x}, \frac{y}{1-y}, \frac{z}{1-z}\right)$$ which can be inverted to give: $$S(x, y, z) = W\left(\frac{x}{1+x}, \frac{y}{1+y}, \frac{z}{1+z}\right)$$

Of course, we know from first principles that $$W(x, y, z) = \frac{1}{1 - (x + y + z)}$$ so this gives $$S(x, y, z) = \frac{1}{1 - \frac{x}{1+x} - \frac{y}{1+y} - \frac{z}{1+z}}$$ in which we want the coefficient of $x^5y^5z^5$. This we can find with a computer-algebra tool like WolframAlpha, giving the answer: $$7188$$

Note that the same generating function works if you want the answer for $n_1$ blue pens, $n_2$ red pens, and $n_3$ black pens, whatever the values of $(n_1, n_2, n_3)$.

I learned this trick from pages 204–205 of the wonderful book Analytic Combinatorics by Flajolet and Sedgewick (available online here and here). (I wrote about something related a while ago.)