ABC String

How many strings of A's, B's, and C's are there that satisfy the following conditions:

1. There are $n$ A's and $2n$ total of B's and C's.

2. Every two adjacent letters are different.

Solution

In order to create such string, we could first arrange $n$ A's and $2n$ D's such that no two A's are adjacent. Then, we can color the D's with B's and C's to satisfy the problem constraint. Note that in order for the coloring to be valid, each contiguous segment of D can only be colored in two ways: BCBCBC.... or CBCBCB...

So now the question is, how many such linings of A's and D's are possible? We first lay down the A's. We then have $n-1$ spots in between that must be filled by non-empty segments of D's, and two spots at both edges that contain possibly-empty segments of D's. Further more, the sum of the length of the segments must equal $2n$, and each segment may be colored in 2 ways.

So, we claim that the number of ways is the coefficient of $x^{2n}$ in the expansion of:

$(1+2x+2x^2+....)(2x+2x^2+2x^3+...)^{n-1}(1+2x+2x^2+...)$

Each term of $x^{2n}$ in the above expansion comes from multiplication of $x^k$ terms in each factor whose sum of power is $2n$. The contribution of $x^k$ from a given factor corresponds to the length of segment corresponding to that factor. The first and last factor correspond to the outer segments which may be empty. The middle segments may not be empty, and that's why we require that they contribute at least one power of $x$. The coefficients are also set up so that each nonempty segments contribute 2 to the number of possible colorings while empty segments do not contribute.

From here, it's just a matter of algebraic manipulation. Let $y=2x+2x^2+... = \frac{2x}{1-x}$

Then $S = (1+y)^2y^{n-1} = y^{n-1} + 2y^n + y^{n+1}$

Also note that, according to Binomial Theorem:

$\frac{1}{(1-x)^k} = (1-x)^{-k} = 1 + kx +\frac{(k+1)k}{2!}x^2 + \frac{(k+2)(k+1)k}{3!}x^3 + ... = \sum_{i=0}^{\infty} \binom{k+i-1}{i} x^i$

So, the coefficient of $x^{2n}$ in $y^{n-1} = 2^{n-1} x^{n-1} \frac{1}{(1-x)^{n-1}}$ is $2^{n-1}$ times the coefficient of $x^{n+1}$ in $\frac{1}{(1-x)^{n-1}}$

that is $2^{n-1} \binom {2n-1}{n+1}$

Similarly, the coefficient of $x^{2n}$ in $2y^n$ is $2^{n+1}\binom{2n-1}{n}$

And the coefficient of $x^{2n}$ in $y^{n+1}$ is $2^{n+1}\binom{2n-1}{n-1}$

So the total coefficient is $2^{n-1} \binom {2n-1}{n+1} + 2^{n+1}\binom{2n-1}{n} + 2^{n+1}\binom{2n-1}{n-1}$

$= 2^{n-1} \frac{(2n-1)!}{n!(n-2)!} \left( \frac{1}{n+1} + \frac{4}{n-1}+ \frac{4}{n-1} \right)$

$= \binom{2n+1}{n} \frac{2^{n-2}(9n+7)}{n(2n+1)}$