2
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Could you give an example of what you mean when you speak roughly? That might help convey the idea. $\endgroup$ Oct 7, 2014 at 21:14
  • $\begingroup$ Thank you for your comments. I tried to get the problem clearer. In the example above, we obtain $m=6$ different subsets in an "alternating" string of length $2n=8$, which is obtained by alternating letters from two strings of length $n=4$ each. $\endgroup$ Oct 8, 2014 at 6:59
  • $\begingroup$ Yes. Thank you. (Now edited in the main text.) $\endgroup$ Oct 8, 2014 at 7:17

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.