# Number of ways to combine two strings

I am trying to determine how many ways one can combine two string of length $n_1$ and $n_2$ such that order of characters in two strings is preserved.

E.g. if I have string "ab" and "12" I can get "ab12" or "a1b2" but not "ba12".

If the final string should combine all characters then I get $^{(n_1+n_2)}C_{n_2}$ combinations.

However if I select sub-string of length $l_1 \in [1, n_1]$ and $l_2 \in [1,n_2]$ I end up with the following expression,

$\sum_{l_1=1}^{n_1} \sum_{l_2=1}^{n_2} {}^{n_1}C_{l_1} {}^{n_2}C_{l_2} {}^{(l_1+l_2)}C_{l_2}$

I was wondering if this expression can be reduced further?

Edit: Wolfram alpha is not much help to me here.

-
I don't know whether this is a correct answer, so I put it as a comment. Consider string of length $n_1+n_2$. There are ${n_1+n_2 \choose n_1}$ ways to choose positions for letters of the first string. Once this positions are chosen, placement of letters of both strings is uniquely determined. – Norbert Aug 2 '12 at 20:36
that is correct if the lengths are fixed at $n_1$ and $n_2$. I now want to consider all possible lengths from 1 to $n_1$, that leads me the the summation. – mythealias Aug 2 '12 at 20:42
Oh, now I see where is your problem – Norbert Aug 2 '12 at 20:50
From your summation expression for what you want, it looks as if you are only allowing contiguous substrings obtained by taking initial substrings of your two words. Is that what is really intended? – André Nicolas Aug 2 '12 at 23:48
Nice catch. I did not notice that. I have edited the question to correct for this. – mythealias Aug 3 '12 at 1:47