How many ways to make sequence with 3A's, 3B's, 3C's such that A's are not allowed to be standing next to a C

Question

I have been thinking about a nice combinatorial problem:

In how many ways can we make sequences of 3A's, 3B's and 3C's such that A's and C's are not allowed to be standing next to eachother. I came up with this myself trying to challenge my students, since I'm a high school math teacher now. However I found out that I challenged myself with this one instead.

An easier variation I thought of is easy to solve: In how many ways can we make a sequence where A's are not allowed next to eachother. It's quite a nice argument: You can make sequences of 3B's and 3C's in $ 6 \choose 3 $ ways, after that you have $6+1=7$ spots to slide in the A's in $7 \choose 3$ ways. So in total $6 \choose 3$ $\cdot $ $7 \choose 3 $ $= 700$ sequences.

I was hoping to come up with a nice argument for the harder question, but unfortunately I failed to do so. So I was hoping anyone here had some ideas.

Answer 1

First place the 3 B's. There is only 1 way to do this. Then place the 3 A's in the 4 spots. There are ${{3+4-1}\choose{4-1}}=20$ ways to do this, by stars and bars. 4 with all A's in the same spot, 12 with two A's in one spot and one A in another spot, and 4 with all three A's in different spots. Now place the C's, depending on how the A's were arranged.

If the three A's are all together, then there are three remaining spots the three C's could be arranged. The could be as a group of three (=3 possibilities), as a group of two and a singleton (=6), or all separate (=1). Or, using stars and bars again, ${{3+3-1}\choose{3-1}} = 10$.

If the A's are in a group of two and a singleton, then there are two spots left and the C's can be arranged as a group of three (=2), or as a group of two and a singleton (=2). ${{3+2-1}\choose{2-1}} = 4$

If the A's are all separate, then the C's must all be together in the last spot (=1).

Adding them all together,

$$ 1\times\big(4\times(10) + 12\times(4) + 4\times(1) \big) = 92 $$

Answer 2

I considered using Inclusion-Exclusion. That approach is do-able and straightforward, and does generalize well. However, in this particular problem, the Inclusion-Exclusion approach that I considered is very messy. So, I will take the direct approach instead.

For what it's worth, I can't help but wonder if     
generating functions, which I am totally ignorant 
of, offers an easier approach.

The A's are placed as - A - A - A - , where there may or may not be open positions before/after each of the A's. What I am going to do is manually identify each way that the 3 B's can be placed in conjunction with the A's, and attach position numbers $P_1, P_2, \cdots, $ to each such placement. Then, for each $P_k$, I will let $f(P_k)$ denote the number of ways that the C's can be placed, so that there are no A:C neighbors.

So, the desired enumeration will be

$$f(P_1) + f(P_2) + \cdots . \tag1 $$

One possibility is that all of the B's are together. So

• $P_1 ~: ~$ - BBB - A - A - A -
• $P_2 ~: ~$ - A - BBB - A - A -
• $P_3 ~: ~$ - A - A - BBB - A -
• $P_4 ~: ~$ - A - A - A - BBB -

By symmetrical considerations, $f(P_1) = f(P_4), f(P_2) = f(P_3).$

For $P_1$, all $3$ C's must occur before the rightmost B. So, the last $4$ elements in the $9$ character sequence must be ...BAAA. So, there are $5$ left-side slots to be filled by the $2$ B's and $3$ C's.

Therefore, $~\displaystyle f(P_1) = \binom{5}{2} = 10.$

For $P_2$, all $3$ C's must occur inside the group of $3$ B's. Therefore, the sequence must have pattern AB....BAA.

So, for $P_2$, there is $1$ remaining B that can go in any of $4$ positions.
Therefore, $~\displaystyle f(P_2) = \binom{4}{1} = 4.$

Therefore,

$$f(P_1) + \cdots + f(P_4) = 2 \times (10 + 4) = 28. \tag2 $$

---

The next possibility in positioning the B's and A's is that exactly two of the B's are together. There are $4$ regions before/after each of the A's. Therefore, there are $(4 \times 3)$ distinct ways of positioning the pair of B's and the lone B.

Consider the sequences

• $P_5 ~: ~$ BB - A - B - A - A -

• $P_6 ~: ~$ BB - A - A - B - A -

• $P_7 ~: ~$ BB - A - A - A - B -

• $P_8 ~: ~$ B - A - BB - A - A -

• $P_9 ~: ~$ - A - BB - A - B - A -

• $P_{10} ~: ~$ - A - BB - A - A - B -

So, $P_5,P_6,P_7$ represent the 2 B's in the first position, and $P_8, P_9, P_{10}$ represent the 2 B's in the second position. Assuming that you similarly let $P_{11}, \cdots, P_{16},$ represent the reversals of $P_5, \cdots, P_{10}$, then by symmetrical considerations, you have that

$$f(P_{11}) + \cdots + f(P_{16}) = f(P_5) + \cdots f(P_{10}).$$

For $P_5$, the sequence must end BABAA, with the $3$ C's preceding the 2nd B. Therefore, $f(P_5) = 4.$ Similarly, $f(P_6) = 4.$

Analysis of $P_7$ is more complicated, since there are two isolation areas: Before the 2nd B, or after the 3rd B.

The number of C's in the 1st isolation area can be any element $(r) \in \{0,1,2,3\}.$ Then, there will be $(r + 1)$ positions, before the 2nd B, one of which must be the 1st B.

Therefore $~\displaystyle f(P_7) = \sum_{r=0}^3 (r + 1) = 10.$

$P_8$ is similar to $P_7$ except that the BB grouping is not on an end. Therefore, any C's that do not precede the 1st B must be strictly between the 2nd and 3rd B.

Therefore $~\displaystyle f(P_8) = \sum_{r=0}^3 (1) = 4.$

Similarly, $f(P_{10}) = 4.$

For $P_9,$ since the lone B is not on an end, all $3$ C's must be inside the pair of B's. Therefore, $f(P_9) = 1.$

Putting this all together:

• $f(P_5) + \cdots + f(P_{10})$ equals
  $4 + 4 + 10 + 4 + 1 + 4 = 27.$

Therefore,

$$f(P_5) + \cdots + f(P_{16}) = 2 \times 27 = 54. \tag3 $$

---

The last possibility, is represented by

• $P_{17} ~: ~$ - B - A - B - A - B - A -
• $P_{18} ~: ~$ - B - A - B - A - A - B -
• $P_{19} ~: ~$ - B - A - A - B - A - B -
• $P_{20} ~: ~$ - A - B - A - B - A - B -

Clearly, with $P_{17}, P_{20}$ each having only $1$ isolation area, $f(P_{17}) = f(P_{20}) = 1.$

$P_{18},$ which has $2$ isolation areas has $f(P_{18}) = 4.$

Similarly, $f(P_{19}) = 4.$

Therefore,

$$f_{17} + \cdots + f_{20} = 1 + 4 + 4 + 1 = 10. \tag4 $$

---

Final computation:

Using (2),(3), and (4) above, the enumeration is

$$28 + 54 + 10 = 92.$$