It is a classical problem that of finding the generating function (GF) of the number of strings with length $n$ having $m$ different letters (basically, the problem reduces to that of writing the regular expression for the string). I call this GF $G(z)$. (It is $G(z)=\prod_{k=1}^m \frac{z}{1-kz}$, where $z$ marks the length, hence the sought number is $G_n=[z^n]G(z)$.)
Suppose now that I have two strings with same length $n$ and with letters from two different alphabets. I generate a new string with length $2n$ by alternating letters from the first and the second strings. For example, if I have ‘$aaba$’ and '$ABAC$'—I just make a difference between the two alphabets by using lowercase and uppercase letters—the new “alternating” string is ‘$aAaBbAaC$’.
Roughly speaking, I want to count the number of "alternating" strings of length $2n$ with $m$ different pairs of next letters (circularly).
To be more precise: consider the set of all subsets formed by two next letters. In the example above, I would have $\{\{a,A\}, \{A,a\}, \{a,B\}, \{B,b\},\{b,A\}, \{A,a\}, \{a,C\}, \{C,a\} \}$. I want to count the number of alternating strings with length $2n=8$ with $m$ different subsets. The trouble for me here is that any next two letters belong to different alphabets (in the opposite case, it would be a classical problem reducing to that of Smirnov words).
P.S. It may be probable that I am not aware of some works on similar topic, but I was not able to find a good reference.