Probability of subsequence occuring in a sequence Imagine you have an alphabet available with three letters denoted by 'A', 'B', and 'C'.
You are allowed to form a sequence (or word) with $n_A\in\mathbf{N}$ 'A's, $n_B\in\mathbf{N}$ 'B's, and $n_C\in\mathbf{N}$ 'C's. Each sample sequence is considered to be equally probable.
For example, set $n_A=6$, $n_B=2$, and $n_C=2$. Thus, the resulting sequences all have length $n_A+n_B+n_C=10$. An example for a sequence is then 'ABAACBACAA'.
Question: Depending on $n_A,n_B,n_C$, what is the probability that letters 'B' and 'C' occur (at least once) next to each other in a sample sequence, i.e., 'BC' or 'CB' occurs?
Approaches or keywords for further searches are very welcome.
 A: Simplify the notation: let there be $b$ copies of B, $c$ copies of C, and $n\ge b+c$ letters altogether (entailing $a=n-b-c$ copies of A).  Switch the roles of B and C if necessary and suppose there exist some of each of those letters to ensure $b\ge c\ge 1.$
There are $$\binom{n}{n-b-c;\,b;\,c} = \frac{n!}{(n-b-c)!\,b!\,c!}$$ distinct, equally probable configurations $\omega$ of these letters ("words").  We can therefore find the chance that BC or CB is a substring of $\omega$ by counting the number of words in which neither BC nor CB is a substring.  Let's call these the "separated" words, because no B is adjacent to a C.
Let $\omega$ be a separated word.  Its "places" are $n$ in number, corresponding to the locations of the $n$ letters.  Erasing all A's in $\omega$ produces a word $\omega_{\hat A}$ of length $b+c$ in the alphabet $\{\text{B},\text{C}\}.$  Scanning from the beginning, reinsert a single A every time a B and C are adjacent.  Suppose $k$ such insertions are made.  The possible words corresponding to any such value of $k$ are determined by the positions of the $n-b-c-k$ reinserted A's relative to the string of B's and C's, which number $$\binom{n-b-c-k + (b+c)}{b+c} = \binom{n-k}{b+c} = \frac{(n-k)!}{(b+c)!\,(n-b-c-k)!}.$$  Therefore they contribute a probability

$$p(k;n,b,c) = \frac{\binom{n-k}{b+c}}{\binom{n}{n-b-c;\,b;\,c}}= \frac{\binom{n-k}{b+c}}{\binom{n}{a;\,b;\,c}}.$$

We need to consider four similar cases depending on (a) whether B or C is the first letter in $\{\text{B},\text{C}\}$ that appears in $\omega$ and (b) whether $k$ is odd or even.  The analysis is similar in each case.

*

*Let's take the first combination, where B appears first and $k=2m$ is even. (Equivalently, $\omega_{\hat A}$ contains $2m+1$ runs of B's and C's.)  To count the possibilities, index the B's from $1$ through $b$ in the order in which they appear and index the C's in the same manner from $1$ through $c.$  Let the first run of B's end at $b_1,$ the first run of C's end at $c_1,$ the second run of B's end at $b_2,$ and so on.  The last run of B's is the $m+1^\text{st}$ run, ending at $b_{m+1}=b,$ and the last run of C's is the $m^\text{th}$ run, ending at $c_n=c.$
The word $\omega_{\hat A}$ is determined by the sequences $(b_1,b_2,\ldots, b_m)$ and $(c_1,c_2,\ldots, c_{m-1}).$  These correspond to subsets of sizes $m$ and $m-1$ within the index sets $\{1,2,\ldots,b-1\}$ and $\{1,2,\ldots,c-1\},$ respectively.  Since they can be independently chosen, the total number of possibilities is $$\binom{b-1}{m}\,\binom{c-1}{m-1}.$$


*When C appears first, the roles of B and C are switched, giving $$\binom{c-1}{m}\,\binom{b-1}{m-1}$$ for the total number of possible such words $\omega_{\hat A}$.


*When $k=2m-1$ is odd and B is the first letter in $\omega_{\hat A},$ there are $m$ runs of each letter.  The formula in (1) is now $$\binom{b-1}{m-1}\,\binom{c-1}{m-1}.$$


*When $k=2m-1$ is odd and C is the first letter, switching B and C in (3) yields the same count, $$\binom{b-1}{m-1}\,\binom{c-1}{m-1}.$$
Because the word $\omega$ determines $k,$ we find the probability of separated words by summing over $k,$ which can be done by summing over the values of $m$ appearing in (1) through (4):

$$\begin{aligned}
\Pr(\omega\text{ separated}) &= \sum_{m\ge 1} p(2m;n,b,c)\left(\binom{b-1}{m}\,\binom{c-1}{m-1} + \binom{b-1}{m-1}\,\binom{c-1}{m}\right)\\
 &+ 2 \sum_{m\ge 1} p(2m-1;n,b,c)\binom{b-1}{m-1}\,\binom{c-1}{m-1}.
\end{aligned}$$

(The sums terminate at $c$ or $c-1$ because (by definition) the Binomial coefficients $\binom{c}{i}$ for negative values of $i$ are zero.)  Subtract this from $1$ to find the chance that $\omega$ is not separated: that is, that it contains at least one BC or CB.
Note that when $n=b+c$ there are no A's.  A minor alteration of this analysis shows how to determine the null distribution of the number of runs ($k+1$) in the Wald-Wolfowitz Runs Test.  (Surprisingly, it is hard to find a derivation of this result on the Web: all the references I find only quote it.)

Example
In the question, $b=c=2$ and $n=2+2+6=10.$  There are $\binom{10}{6;\,2\,2}=1260$ distinct words. The first sum in the formula (for $k=2m$) covers the case $k=2$ and contributes $70+70.$  The second sum in the formula (for $k=2m-1$) covers the cases $k=1$ and $k=3,$ contributing the terms $252+70.$  The total number of separated words therefore is $462$ and the chance of not being separated--of BC or CB occurring--therefore is $1 - 462/1260=0.6\bar3.$
An exhaustive listing of all $1260$ cases confirms this.

Computing
To avoid double precision overflow, it is essential to use logarithms in computing these values whenever $a,$ $b,$ or $c$ grows into three (decimal) digits.  Here is an illustration in R.
#
# Chance that all B's and C's are separated.  Need n >= b+c and b, c >= 1.
#
p <- function(n, b, c) {
  lp <- function(k,n,b,c)
    suppressWarnings(lchoose(n-k, b+c) - lfactorial(n) + 
                     lfactorial(n-b-c) + lfactorial(b) + lfactorial(c))
  
  m <- c(seq_len(min(b, c)))
  lp.2m <- lp(2*m, n, b, c)
  sum(exp(lp.2m + lchoose(b-1,m) + lchoose(c-1,m-1)) +
            exp(lp.2m + lchoose(b-1,m-1) + lchoose(c-1,m)) + 
            2 * exp(lp(2*m-1,n,b,c) + lchoose(b-1,m-1) + lchoose(c-1,m-1)))
}

For example, here is a plot of the separation probability as a function of $n$ for medium values of $b$ and $c.$  Beneath it is the code to produce it.

f <- Vectorize(function(x) p(x,200,100), "x")
curve(f(x), 1e3, 1e7, ylim=c(0,1), n=1001, log="x", lwd=2,
      xlab="n", ylab=expression(paste("Pr(", omega, " separated)")),
      main="Separation Probability for b=200, c=100")

