4
$\begingroup$

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.

  • 0
    Note: there's an implicit assumption in these formulae that the strings don't contain repeated characters, e.g. "aab", and that the two strings contain different characters, e.g. "abc" and "ade".2012-10-13

0 Answers 0