Arrangements of a,a,a,b,b,b,c,c,c in which no three consecutive letters are the same

Q: How many arrangements of a,a,a,b,b,b,c,c,c are there such that

$\hspace{5mm}$ (i). no three consecutive letters are the same?

$\hspace{5mm}$ (ii). no two consecutive letters are the same?

A:(i). 1314. ${\hspace{5mm}}$ (ii). 174.

I thought of using the General Principle of Inclusion and Exclusion along with letting $p_i$ denote a property that.. , and doing so, I will evaluate $E(0)$, which gives us the number of arrangements without any of the properties.

How do I go about doing that? I am trying to use the method stated above in solving this question, but I am unable to generalize the properties $p_i$.

(i)

For the first question, your idea of using the Inclusion-Exclusion Principle is the correct approach.

The number of distinguishable arrangements of the letters $a, a, a, b, b, b, c, c, c$ is $$\frac{9!}{3!3!3!}$$ where the factors of $3!$ in the denominator are attributable to the fact that interchanging identical letters in a given arrangement does not produce an arrangement that is distinguishable from the original arrangement. Alternatively, we can choose to fill three of the nine positions with $a$'s, three of the remaining six positions with $b$'s, and the remaining three positions with $c$'s, which can be done in $$\binom{9}{3}\binom{6}{3}\binom{3}{3} = \frac{9!}{3!6!} \cdot \frac{6!}{3!3!} \cdot \frac{3!}{3!0!} = \frac{9!}{3!3!3!}$$ ways.

From these, we must exclude those arrangements in which there are three consecutive identical letters.

Next, we count the number of arrangements in which a block of three consecutive identical letters appears. There are three ways to choose which letter appears in the block of three consecutive letters. Treating the block of three identical letters as one object, we have seven objects to arrange, the block and the other six letters. Since those six letters contain two sets of three identical letters, the number of arrangements containing a block of three consecutive letters is $$\binom{3}{1}\frac{7!}{3!3!}$$

However, we have counted arrangements in which two blocks of consecutive identical letters appear twice.

Next, we count arrangements in which two blocks of three consecutive identical letters appear. There are three ways to choose which two letters appear in blocks of three consecutive letters. If we treat each block as an object, we have five objects to arrange, the two blocks and the other three letters. Since the other three letters are identical, the number of arrangements containing two blocks of three consecutive letters is $$\binom{3}{2}\frac{5!}{3!}$$

If we subtract the number of arrangements in which two blocks of three identical letters appear from our initial count of the number of arrangements in which a block of three identical letters appears, we will not have counted arrangements in which three blocks of three identical letters appear since we first counted them three times, then subtracted them three times.

The number of arrangements with three blocks of three consecutive identical objects is $3!$.

By the Inclusion-Exclusion Principle, the number of arrangements in which at least one block of three consecutive letters appears is

$$\binom{3}{1}\frac{7!}{3!3!} - \binom{3}{2}\frac{5!}{3!} + \binom{3}{3}3!$$

so the number of arrangements in which no three consecutive letters are identical is $$\frac{9!}{3!3!3!} - \binom{3}{1}\frac{7!}{3!3!} + \binom{3}{2}\frac{5!}{3!} - \binom{3}{3}3!$$

(ii)

The second problem can also be handled by Inclusion-Exclusion Principle.

We wish to exclude pairs of identical letters.

One pair of consecutive identical letters:

There are three ways to choose the repeated letter. Treating that pair of identical letters as a block leaves us with eight objects, including two sets of three identical letters. The number of ways these objects can be arranged is $$\binom{3}{1}\frac{8!}{3!3!}$$

Two pairs of consecutive identical letters:

There are two cases. We can have three consecutive identical letters (two overlapping pairs) or two distinct pairs of consecutive identical letters (such as $aa$ and $bb$). We found above that there are $$\binom{3}{1}\frac{7!}{3!3!}$$ arrangements with three consecutive identical letters.

For the other case, there are three ways of choosing the letters of the alphabet from which the pairs of consecutive identical letters are chosen. This leaves us with seven objects, the two blocks of consecutive identical letters, the third letter from each chosen type, and the three letters of the third type. Since the three letters of the third type are indistinguishable, the number of such arrangements is $$\binom{3}{2}\frac{7!}{3!}$$ In total, the number of arrangements with two pairs of consecutive identical letters is $$\binom{3}{1}\frac{7!}{3!3!} + \binom{3}{2}\frac{7!}{3!}$$

Three pairs of consecutive identical letters:

Again, there are two cases. We could choose three pairs of consecutive identical letters from different letters of the alphabet or three consecutive identical letters (two overlapping pairs) and a pair of consecutive identical letters from a different letter of the alphabet.

If each pair of consecutive identical letters is from a distinct letter of the alphabet, we have six objects to arrange, $aa$, $bb$, $cc$, $a$, $b$, and $c$. This can be done in $$6!$$ ways.

For the other case, there are three ways of selecting the letter of the alphabet from which three consecutive identical letters are selected, and two ways of selecting the letter of the alphabet from which two consecutive identical letters are selected. Again, we have six objects, the block of three consecutive identical letters, the block of two consecutive identical letters, and the other four letters. Three of those other four letters are indistinguishable, so the number of such arrangements is $$\binom{3}{1}\binom{2}{1}\frac{6!}{3!}$$ Therefore, the total number of arrangement with three consecutive identical letters is $$6! + \binom{3}{1}\binom{2}{1}\frac{6!}{3!}$$

Four pairs of consecutive identical letters:

Again, we have two cases. We have two blocks of three consecutive identical letters (two sets of two overlapping pairs), or we have one block of three consecutive identical letters (two overlapping pairs) with a pair of consecutive identical letters from each of the other letters of the alphabet.

We found above that the number of arrangements with two blocks of three consecutive identical letters is $$\binom{3}{2}\frac{5!}{3!}$$ For the remaining case, there are three ways of choosing the letter of the alphabet with three consecutive identical letters. We have five objects, the block of three consecutive identical letters, the two blocks of two consecutive identical letters, and the two remaining single letters. They can be arranged in $$\binom{3}{1}5!$$ ways. The total number of arrangements with four pairs of consecutive identical letters is then $$\binom{3}{2}\frac{5!}{3!} + \binom{3}{1}5!$$

Five pairs of consecutive identical letters:

For this to occur, there must be two blocks of three consecutive identical letters (two sets of two overlapping pairs) and a block of two consecutive identical letters drawn from the other available letter. There are three ways of selecting the two letters from which the blocks of three identical consecutive letters are drawn. We now have four objects to arrange, the two blocks of three consecutive identical letters, the block of two consecutive identical letters, and the remaining letter. The number of such arrangements is $$\binom{3}{2}4!$$

Six pairs of consecutive identical letters:

The only ways for this to occur is if we have three blocks of three consecutive identical letters (three sets of two overlapping pairs). We saw above that there are $$3!$$ such arrangements.

By the Inclusion-Exclusion Principle, the number of arrangements of the letters $a, a, a, b, b, b, c, c, c$ in which no two identical letters are consecutive is $$\frac{9!}{3!3!3!} - \binom{3}{1}\frac{8!}{3!3!} + \left[\binom{3}{1}\frac{7!}{3!3!} + \binom{3}{2}\frac{7!}{3!}\right] - \left[6! + \binom{3}{1}\binom{2}{1}\frac{6!}{3!}\right] + \left[\binom{3}{2}\frac{5!}{3!} + \binom{3}{1}5!\right] - \binom{3}{2}4! + \binom{3}{3}3! = 174$$

This answer is based upon a generating function of generalized Laguerre polynomials \begin{align*} L_k^{(\alpha)}(t)=\sum_{i=0}^k(-1)^k\binom{k+\alpha}{k-i}\frac{t^i}{i!} \end{align*}

The Laguerre polynomials have some remarkable combinatorial properties and one of them is precisely suited to answer problems of this kind. This is nicely presented in Counting words with Laguerre series by Jair Taylor. We find in section $3$ of this paper:

Theorem: If $m_1,\ldots,m_k,n_1,\ldots,n_k$ are non-negative integers, and $p_{m,n}(t)$ are polynomials defined by \begin{align*} \sum_{n=0}^\infty p_{m,n}(t)x^n=\exp\left(\frac{t\left(x-x^m\right)}{1-x^m}\right) \end{align*} then the total number of $k$-ary words that use the letter $i$ exactly $n_i$ times and do not contain the subwords $i^{m_i}$ is \begin{align*} \int_0^\infty e^{-t}\prod_{j=1}^k p_{m_j,n_j}(t)\,dt \end{align*}

Here we consider a $3$-ary alphabet $\{a,b,c\}$ and words built from the characters $$a,a,a,b,b,b,c,c,c$$

First case: Bad words $\{aaa,bbb,ccc\}$

We have $m_1=m_2=m_3=3, n_1=n_2=n_3=3$

We obtain with some help of Wolfram Alpha

\begin{align*} p_{3,3}(t)&=[x^3]\exp\left(\frac{t\left(x-x^3\right)}{1-x^3}\right)\\ &=[x^3]\left(1+tx+\frac{1}{2}t^2x^2+\left(\frac{1}{6}t^3-t\right)x^3+\cdots\right)\\ &=\frac{1}{6}t^3-t \end{align*}

It follows

\begin{align*} \int_0^\infty e^{-t}\left(\frac{1}{6}t^3-t\right)^3\,dt=1314 \end{align*}

Second case: Bad words $\{aa,bb,cc\}$

We have $m_1=m_2=m_3=2, n_1=n_2=n_3=3$ and obtain

\begin{align*} p_{2,3}(t)&=[x^3]\exp\left(\frac{t\left(x-x^2\right)}{1-x^2}\right)\\ &=[x^3]\left(1+tx+\left(\frac{1}{2}t^2-t\right)x^2+\left(\frac{1}{6}t^3-t^2+t\right)x^3+\cdots\right)\\ &=\frac{1}{6}t^3-t^2+t \end{align*}

It follows

\begin{align*} \int_0^\infty e^{-t}\left(\frac{1}{6}t^3-t^2+t\right)^3\, dt=174 \end{align*}