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.

  • 1
    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.2012-08-02
  • 0
    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.2012-08-02
  • 0
    Oh, now I see where is your problem2012-08-02
  • 0
    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?2012-08-02
  • 0
    Nice catch. I did not notice that. I have edited the question to correct for this.2012-08-03
  • 0
    Have I understood the question correctly, it should be possible to write it as $ \sum_{l_1 = 1}^{n_1} \sum_{l_2 = 1}^{n_2} \binom{n_1}{l_1} \binom{n_2}{l_2} \binom{l_1+l_2}{l_1} $, which I can not immediately simplify further.2012-08-03
  • 0
    Where you wrote $l_1 = [1, n_1]$, did you mean $l_1 \in [1, n_1]$?2012-08-03
  • 0
    @utdiscant: That's exactly what the $C$ notation for the binomial coefficients is supposed to denote in the question.2012-08-03
  • 0
    @joriki that is correct. sorry for the confusion.2012-08-03
  • 0
    @mythealias: Why did you edit the question without correcting the mistake?2012-08-03
  • 0
    I think it is possible to at least reduce it to $\sum_{l_1 = 1}^{n_1} \sum_{l_2 = 1}^{n_2} \frac{n_1!n_2!(l_1+l_2)!}{l_1!^3 l_2!^3} $2012-08-03
  • 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