0
$\begingroup$

There is a question from my problem set that I am facing difficulty in solving.

It says to find the number of ways to arrange $A, A, A, B, C, C$ so that no $2$ consecutive letters are the same.

Some of the comments are suggesting this is a duplicate but in that question, the frequency of the letters was the same making it easier to solve by inclusion-exclusion principle. Not the case here, however.

My approach:

I tried to formulate cases where no $2$ consecutive letters would be the same. I tried using the gap method wherein I created a scenario like this,
$- A- A - A- $
Now we can see that there are $4$ spaces and three letters left to fill, and no restrictions, so we get $\binom{4}{3}\cdot 3! = 24$.
However, this is obviously not the only case where this is possible. I think this might be solvable with the inclusion-exclusion principle.

Approach 2:

If we take cases for the consecutive letters being the same, then we can perhaps subtract from the total number of cases, for example, we can take
$2 A$'s being consecutive and then $3A$'s and then $2B$'s and so on...
This is where I require help.
Any help would be appreciated.

$\endgroup$
  • 1
    $\begingroup$ Possible duplicate of Arrangements of a,a,a,b,b,b,c,c,c in which no three consecutive letters are the same $\endgroup$ – Jam Aug 17 '18 at 8:56
  • $\begingroup$ @Jam: That one is significantly more complicated than this. $\endgroup$ – Henning Makholm Aug 17 '18 at 9:01
  • 2
    $\begingroup$ Your approach 1 goes wrong, first because you're treating the two Cs as distinguishable (this overcounts by a factor of two), second because the middle two positions in -A-A-A- must be filled with something (this counts some invalid soluions such as CAABAC), third because you can fill one of those positions with two letters if you have enough letters, which you will have if you leave both the ends blank (this misses some valid positions such as ABCACA). $\endgroup$ – Henning Makholm Aug 17 '18 at 9:13
  • $\begingroup$ I was just about to say the same thing, I had the same thought as I was checking my solution. Thank you so much. $\endgroup$ – Prakhar Nagpal Aug 17 '18 at 9:14
3
$\begingroup$

First determine the order of the B, C, C, ignoring the As. There are $3$ possibilities for that.

Now you have, for example, -C-B-C- and you need to fill three of the four open slots with As. There are $4$ ways to do that -- you just have to choose which slot you don' fill.

The cases where this won't produce a valid sequence is if the two Cs were adjacent in the initial sequence and don't get an A between them. That is, we need to subtract two for exactly the sequences ABACCA amd ACCABA, and our final count is $$ 3\cdot 4 - 2 $$

$\endgroup$
  • $\begingroup$ Are you sure that this is the only case because according to what I have tried my count is higher than this and I don't feel like I have included all the cases too? $\endgroup$ – Prakhar Nagpal Aug 17 '18 at 9:06
  • $\begingroup$ @PrakharNagpal: If I'm wrong, it shouldn't be hard to produce a concrete list of 11 different valid sequences. (Or just one sequence that isn't counted by my analysis). $\endgroup$ – Henning Makholm Aug 17 '18 at 9:07

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.