Counting the number of permutations of string with given repeated interwoven subsequence
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:

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.

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.