1
$\begingroup$

Suppose, two strings $A$ and $B$ of length $x$ and $y$ are given. Now, I have to find out number of possible combination of sub-sequences of these two strings.

For example, let A="abc"; clearly the set of sub-sequences of A is {"" , "a" , "b" , "c", "ab", "bc", "ac", "abc" }. For any string $x$ with length $y$ will have $2^x$ sub-sequences.

Now if we assume "abc" and "de" are two $sub-sequences$ and we combine them then we get, "abcde", "abdce", "abdec", "adbce", "adbec", "adebc", "dabce", "dabec", "daebc" and "deabc". So, combining two sub-sequences means a string which contains all the characters of two strings and both are sub-sequences of these combinations.

Now, how to find out number of possible combinations of all sub-sequences of $A$ and $B$.

$\endgroup$
3
$\begingroup$

Let $m=|A|$ and $n=|B|$. Suppose that you choose a subsequence of $A$ of length $k$ and a subsequence of $B$ of length $\ell$. When you combine them into a sequence of length $k+\ell$, that sequence is completely determined once you know which $k$ positions in it come from the $A$ subsequence. Thus, there are $\binom{k+\ell}k$ different ways to combine the two subsequences. There are $\binom{m}k$ ways to choose the $A$ subsequence and $\binom{n}\ell$ ways to choose the $B$ subsequence, so the answer to your question is

$$\sum_{k=0}^m\sum_{\ell=0}^n\binom{m}k\binom{n}\ell\binom{k+\ell}k\;.$$

So far I’ve not found any way to simplify this. Assuming no computational errors on my part, the first few values are shown below:

$$\begin{array}{c|cc} m\backslash n&0&1&2&3\\ \hline 0&1&2&4&8\\ 1&2&5&12&28\\ 2&4&12&33&86\\ 3&8&28&86&245 \end{array}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.