Number of $AB$,$BA$ in permutations of $AAAAABBBB$

Question

Find the number of $AB$ and $BA$ in the permutations of $AAAAABBBB$ (Ex: AABBAAABB contains 3).

So far, I could only solved it by principle of inclusion and exclusion. As far as I know, there is a better way.

Answer 1

Here is a probabilistic approach. Consider a random permutation of $AAAAABBBB$; there are $9!$ such permutations, all of which are equally likely. Define $$X_i = \begin{cases}1 \qquad \text{if there is an AB starting at location i of the permutation}\\ 0 \qquad \text{otherwise} \end{cases}$$ and $$Y_i = \begin{cases}1 \qquad \text{if there is a BA starting at location i of the permutation}\\ 0 \qquad \text{otherwise} \end{cases}$$ for $1 \le i \le 8$. Then we have $$P(X_i = 1) = P(Y_i = 1) = \frac{4 \cdot 5}{9 \cdot 8}$$ so $$E \left( \sum_{i=1}^8 (X_i +Y_i) \right) = \sum_{i=1}^8 E(X_i) + \sum_{i=1}^8 E(Y_i) = 2 \cdot 8 \cdot \frac{4 \cdot 5}{9 \cdot 8} \tag{1}$$ by linearity of expectation. On the other hand, $$E \left( \sum_{i=1}^8 (X_i +Y_i) \right) = \frac{N}{9!} \tag{2}$$ where $N$ is the total number of occurrences of $AB$ and $BA$ in the complete set of $9!$ permutations.

Solve $(1)$ and $(2)$ for $N$ and you're done.

Edit, Dec. 20 2019:

Based on Milo Brandt's comment, below, if we are dealing with "distinguishable permutations", then the $9!$ in equation $(2)$ should be replaced with $\binom{9}{4}$.