Counting the number of permutations of string with given repeated interwoven subsequence

Question

Given string $S$ of length $n$, count the number of distinct permutations $P_n$ of a string of length $2n$ such that each of them contains $S$ twice as an interwoven subsequence.

Example. $S=abc$. There are 5 permutations: $abcabc$, $abacbc$, $ababcc$, $aabcbc$, $aabbcc$.

If each character of $S$ appears only once, the problem becomes easier. Consider all binary strings of length $2n$ with $n$ zeros and $n$ ones. Zeros represent the first subsequence and ones represent the second subsequence. Whenever there is a binary string with some prefix that contains more ones than zeros, we may repaint the binary string in a way that both the original binary string and the repainted binary string represent the same permutation, and that no prefix of the repainted binary string has more ones than zeros.

Therefore we may restrict ourselves to the binary strings where for each prefix the number of zeros equals or is greater than the number of ones. Because each character of $S$ appears only once, each such binary string represent a distinct permutation. There is a simple recursive method to generate such binary strings, and by applying dynamic programming it is possible to calculate $P_n$ in $O(n^2)$ time. Apparently for this special case $P_n$ eqals the n'th Catalan number $C_n$, so it should be possible to get it done with $O(n)$ multiplications.

When some characters of $S$ appear more than once, or there are common substrings, $P_n<C_n$. For $S=aaa$ the number is 1, for $S=aab$ it is 3, and for $S=aba$ it is 4. So now my questions are:

1. How to find $P_n$ in a way that is faster than generating all $C_n$ permutations and counting the unique ones?
2. The general case. Given $S$,$n$,$k$, count the number of distinct permutations of a string of length $kn$ such that each of them contains $S$ $k$ times as an interwoven subsequence. How to do this faster than generating all the plausible permutations and counting the unique ones?

Answer 1

It's possible to count the number of such strings in something like $O(2^{n})$ time. This is faster than generating all permutations (as $n! \sim 2^{n \log n + O(n)}$), but it's still not polynomial time. I don't know if the number of such strings can be counted in polynomial time.

Here's how to do it. You can build a NFA that accepts all such strings of length $2n$, and only such strings. The NFA will have $O(n^2)$ states and be acyclic: it has $2n$ levels, and each level has $\le n$ states in it, and each transition goes from one level to the next level. Each state in the NFA is of the form $(i,j)$, representing that we've already consumed the first $i$ characters of the first copy of $S$ and the first $j$ characters of the second copy of $S$.

So now the task reduces to counting the number of strings accepted by this (acyclic) NFA. Unfortunately, counting the number of strings accepted by an (acyclic) NFA is #P-complete in the general case, so there's no polynomial-time algorithm that works for all (acyclic) NFAs. (This doesn't rule out the possibility of a specialized algorithm that somehow takes advantage of the special structure of this particular NFA, but personally, I don't see any way to construct such an algorithm.)

That said, there are two techniques that are available here:

1. We can count the number of strings accepted by this NFA in exponential time. First, convert the NFA to a DFA via the product construction. You obtain an acyclic DFA with at most $2n \times 2^n$ states. Since this DFA is acyclic, you can then count the number of words accepted by it in time linear in the number of states using dynamic programming. Therefore, the total running time will be something like $O(n \cdot 2^n)$.

   See also https://cstheory.stackexchange.com/q/8200/5038.

2. Alternatively, you can compute an approximation to the number of such strings, much more efficiently -- but the approximation will be rather inexact. See Counting the number of words accepted by an acyclic NFA for details of how to do that.

I don't know if there are better techniques for your problem, or if there's any method to solve your problem in polynomial time.