The answer is it depends in the sequence. Suppose we want to find the probability that the word 11 is inside a 3-letter word in an alphabet of 3 letters.There are 5 such words that contain it. Now lets look at the probability the word 12 is inside a 3-letter word. there are 6 words that contain it. Not all words have the same probability.
Now for a fixed word:
let w be your m-letter string in a k letter alphabet. Let $x_n$ be the number of words of lenth $n$ (also in x letter alphabet) containing w.
At first sight we would consider the following recurrence relation:
$x_n=kx_{n-1}+k^{n-m}-x_{n-m}$ Since every word of length n can be created in the following way: for a n-1 word that contains w just add any of the k letters at the end $kx_{n-1}$. For a $k-n$length word just add w at the end to get one that does work. This seems really great. There's just one problem:
Sometimes when you add w at the end of a n-k word that doesn't contain w you get a word that contains w even if you remove some of the last digits. Let me explain: for example consider $w=1,2,1$ then the word $3,1,2$ clearly doesn't contain $w$ so we add w to this letter to get $3,1,2,1,2,1$ notice that this word is obtained through both the process of taking an (n-1) word that contains w and taking and n-k word that does not. Thus we are counting it twice? Can you refine the recursion so it works?
This question is kinda weird since you didn't say anything about repetition. Supposing our sequence of length n allows repetition, here is how I would approach it:
We want to create sequences of length n from a set of $k$ characters allowing repetition with the constraint that at most two adjacent characters can be the same.
Let's use the inclusion-exclusion principle.
First, the number of sequences of length $n$ from $k$ elements allowing repetition is: $k^n$.
Now let's define the following sets for $ 3 \leq p \leq n$:
$$
S_p=\{\text{Sequences of length n with p adjacent characters the same}\}
$$
Therefore our final answer is: $k^n- |\bigcup_{p=3}^n S_p|$. Let's then calculate the cardinality of that union.
Clearly those sets are all disjoint, therefore:
$$
|\bigcup_{p=3}^n S_p| = |S_3| + |S_4| + \cdots + |S_n|
$$
And we can use the following strategy to calculate the cardinality of $|S_p|$: From our $k$ characters, select $1$ and place it in $p$ adjacent positions. There are $n-p+1$ possibilities to choose adjacent positions. Now we need to let the remaining $n-p$ positions to select, without repetition, characters from the $k-1$ remaining, and that can be done in $(k-1)(k-2)\cdots (k-n+p)=\frac{(k-1)!}{(k-n+p-1)!}$ ways. Therefore, by multiplication principle we get:
$$
|S_p|=k\cdot (n-p+1) \cdot \frac{(k-1)!}{(k-n+p-1)!} = \frac{k!(n-p+1)}{(k-n+p-1)!}
$$
which follows that:
$$
|\bigcup_{p=3}^n S_p| = \sum_{p=3}^{n} \frac{k!(n-p+1)}{(k-n+p-1)!}
$$
Finally, our answer is:
$$
k^n - \sum_{p=3}^{n} \frac{k!(n-p+1)}{(k-n+p-1)!}
$$
Sanity Check: Suppose $n=4$ and $K=\{a,b\}$. Therefore all sequences are:
\begin{align*}
(a,a,a,a)&\\
(a,a,b,b)&,(a,b,a,b)\\
(a,a,a,b)&,(a,a,b,a),(a,b,a,a),(b,a,a,a)\\
(b,b,b,b)&\\
(b,b,a,a)&,(b,a,b,a)\\
(b,b,b,a)&,(b,b,a,b),(b,a,b,b),(a,b,b,b)\\
(b,a,a,b)&,(a,b,b,a)
\end{align*}
There are $2^4=16$ sequences. Removing the ones that we don't want to count, that is, sequences with three or more adjacent repetitions, we have the remaining sequences:
$$
(a,a,b,b),(a,b,a,b)\\
(a,a,b,a),(a,b,a,a)\\
(b,b,a,a),(b,a,b,a)\\
(b,b,a,b),(b,a,b,b)\\
(b,a,a,b),(a,b,b,a)
$$
There are $10$ sequences. Now let's check if our answer is going to validate to the same number:
\begin{align*}
k^n - \sum_{p=3}^{n} \frac{k!(n-p+1)}{(k-n+p-1)!} &= 2^4 - \frac{2!(4-3+1)}{(2-4+3-1)!} - \frac{2!(4-4+1)}{(2-4+4-1)!}\\
&= 16 - \frac{2!(2)}{(0)!} - \frac{2!(1)}{(1)!}\\
&= 16 - 4 - 2 = 10
\end{align*}
So it seems to make sense. I'm not sure if it's 100% correct, but that's what I've done to try to solve it. Hope it helps!
Best Answer
Given your example, both elements of the pair are distinct. I am going by that.
Choose $1$ from $n$ alphabets and make word of $m$ letters. Make other word of the pair from $(n-1)$ remaining letters.
Number of such word pairs $ = \, {n \choose 1} \times 1 \times (n-1)^m$.
Now, choose $2$ from $n$ alphabets and make words of $m$ letters but now we need to be careful as all words just with one letter are already made. So we need to subtract that. We make second word of the pair from remaining (n-2) letters.
Number of such word pairs $ = {n \choose 2} \times (2^m - 2) \times (n-2)^m$.
Similarly when we choose $3$ letters, we would have to exclude all words with just two letters and with $1$ letter. As we try and exclude words with $2$ letters, we would subtract words with $1$ letter more times than we should so we have to keep applying P.I.E.
Now choose $2$ from $n$ alphabets and make words of $m$ letters but now we need to be careful as all words just with one letter are already made. So we need to subtract that.
Number of such word pairs $ = {n \choose 3} \times (3^m - {3 \choose 2} 2^m + {3 \choose 1}) \times (n-3)^m$.
We can convert this into using Stirling Number of the second kind and multiply by number of ways to arrange the letters.
So total number of possible word pairs
$ = \displaystyle \sum \limits_{i = 1}^m {n \choose i} \times (i)! \times S2(m,i) \times (n-i)^m$