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:
- How to find $P_n$ in a way that is faster than generating all $C_n$ permutations and counting the unique ones?
- 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?