# Number of possible combination of all subsequences of two strings

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$.

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\;.$$
$$\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}$$