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$.
 A: 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}$$
Added 5 March 2022: If this matrix is read off by antidiagonals, reading downwards, the resulting sequence
$$1,2,2,4,5,4,8,12,12,8,16,28,33,28,16,\ldots$$
is OEIS A341867. The entry has a little more information, notably a simple proof that the odd values are precisely those for which $m=n$.
