Arrangements of $a,a,b,b,b,c,c,c,c$ in which no four/three/two consecutive letters are the same

combinationscombinatoricsinclusion-exclusionpermutations

I have the following problem:

We are going to generate permutations from $a, a, b, b, b, c, c, c, c.$
Please compute the number of permutations such that:
(a) for any consecutive $4$ elements, they are not all the same;
(b) for any consecutive $3$ elements, they are not all the same;
(c) for any consecutive $2$ elements, they are not all the same.


For part a, I think it is $1200$
$$\frac {9!}{2!3!4!} – \binom{1}{1} \frac {6!}{3!2!} =1260-60 =1200$$
what I did here is to exclude those arrangements in which there are four consecutive identical letters.

For part b, I can not quite figure out the plan. I go through some solutions here
Arrangements of a,a,a,b,b,b,c,c,c in which no three consecutive letters are the same
but still don't know how to do it.

Even though these two cases are quite similar, the $c,c,c,c$ and $c,c,c$ difference make me so confused. I try to work on it and my answer for part b is $483$
Here are my steps:
I calculate the permutation with one consecutive pair first. I think it is $$S_1 = \binom {2}{1}\frac {6!}{2!3!} + \frac {7!}{2!4!} =945$$ for two consecutive pairs, I think it is $$S_2 = \binom {2}{1} \binom{3}{3}\frac {5!}{2!} + \binom {2}{2} \frac {6!}{2!3!}=180$$ for three consecutive pairs, I think it is $$S_3 = \binom {3}{3} \frac{4!}{2!}=12$$ I think there are at most three consecutive pairs. the $b,b,b$ pair, and the overlapping pairs $c,c,c,c$. My final answer is $$1260 – S_1 +S_2- S_3 = 1260 -945+160-12 = 483$$ but I don't think it is correct.
Could anyone please help?
For part c, I got a weird answer which is a negative value that is impossible to be correct. The method I used in part c is the same as in part b. Therefore, I doubt my part b is also incorrect.

Best Answer

Your answer to the first question is correct.

How many permutations of $a, a, b, b, b, c, c, c, c$ are there such that no three consecutive elements are the same?

The total number of arrangements is $$\binom{9}{2}\binom{7}{3}\binom{4}{4} = \frac{9!}{2!7!} \cdot \frac{7!}{3!4!} \cdot \frac{4!}{4!0!} = \frac{9!}{2!3!4!0!} = \frac{9!}{2!3!4!}$$ since we must choose two of the nine positions for the $a$s, three of the remaining seven positions for the $b$s, and fill all four of the remaining four positions with the $c$s. We can express the number of elements in the sample space using a multinomial coefficient $$\binom{9}{2, 3, 4} = \frac{9!}{2!3!4!}$$

From these, we must subtract those arrangements in which there is at least one block of three consecutive identical letters.

A block of three consecutive identical letters: Since there are only two $a$s, this can only happen in two ways, either there is a block of three consecutive $b$s or a block of three consecutive $c$s.

There is a block of three consecutive $b$s: Then we have seven objects to arrange: $a, a, bbb, c, c, c, c$. Choose two of the seven positions for the $a$s, one of the remaining five positions for the block, and fill all four of the remaining four positions with the $c$s, which can be done in $$\binom{7}{2, 1, 4}$$ ways.

There is a block of three consecutive $c$s: Then we have seven objects to arrange: $a, a, b, b, b, ccc, c$. Choose two of the seven positions for the $a$s, three of the remaining five positions for the $b$s, one of the remaining two positions for the block of three $c$s, and fill the remaining position with the remaining $c$. There are $$\binom{7}{2, 3, 1, 1}$$ such arrangements.

Two blocks, each containing three consecutive identical letters: There are two ways this can occur, either there are three consecutive $b$s and three consecutive $c$s or there are four consecutive $c$s (two overlapping blocks of three consecutive $c$s, the first three and the last three).

A block of three consecutive $b$s and a block of three consecutive $c$s: We have five objects to arrange: $a, a, bbb, ccc, c$. Choose two of the five positions for the $a$s, one of the remaining three positions for the block of $b$s, one of the remaining two positions for the block of $c$s, and fill the remaining position with the remaining $c$. There are $$\binom{5}{2, 1, 1, 1}$$ such arrangements. It looks like you counted this case twice in $S_2$, so you added too much to your answer.

A block of four consecutive $c$s: We have six objects to arrange: $a, a, b, b, b, cccc$. Choose two of the six positions for the $a$s, three of the remaining five positions for the $b$s, and fill the remaining position with the block of $c$s, which can be done in $$\binom{6}{2, 3, 1}$$ ways.

Three blocks, each containing three consecutive identical letters: For this to occur, we must have three consecutive $b$s and four consecutive $c$s. Hence, we have four objects to arrange: $a, a, bbb, cccc$. Choose two of the four positions for the $b$s, one of the remaining two positions for the block of $b$s, and then fill the remaining position with the block of $c$s. There are $$\binom{4}{2, 1, 1}$$ such arrangements.

By the Inclusion-Exclusion Principle, the number of arrangements of $a, a, b, b, b, c, c, c, c$ in which no block of three consecutive identical letters appears is $$\binom{9}{2, 3, 4} - \binom{7}{2, 1, 4} - \binom{7}{2, 3, 1, 1} + \binom{5}{2, 1, 1, 1} - \binom{6}{2, 3, 1} + \binom{4}{2, 1, 1}$$

What mistakes did you make?

All of your counts match mine except a block of three consecutive $c$s, which you subtracted twice, and a block of three consecutive $b$s and three consecutive $c$s, which you added twice. When you have four $c$s and three of them are consecutive, you must treat the four $c$s as two objects: $ccc$ and $c$. The two objects may or may not be adjacent. If they are adjacent, they form two blocks of three consecutive $c$s: $\color{red}{ccc}c$ and $c\color{red}{ccc}$.

How many permutations of $a, a, b, b, b, c, c, c, c$ are there such no that two consecutive letters are the same.

When you attempt this question, keep in mind that three consecutive $b$s count as two pairs of adjacent $b$s, three consecutive $c$s count as two pairs of consecutive $c$s, four consecutive $c$s count as three pairs of consecutive $c$s, and that you can also have two disjoint pairs of adjacent $c$s, which may or may not be adjacent.

You may want to reread my answer to the linked question before you attempt this question.