Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.