Given two sequence of strings, one with $n$ elements the other with $m$ elements and $m\geq n$.
We are interesting to align those two sequence, and select $k$ out of $m$ and $n$ respectively for matching, and incorporate with another operations "inserting gap" E.g( following is one of possible alignment select $3$ out of $7$ and $3$ out of $6$)
$$123-x_1x_2x_3-x_4-$$
$$123y_1---y_2-y_3$$
Below is another possible alignment select $3$ out of $7$, $3$ out of $6$ and with different inserting gap$$123x_1--x_2-x_3x_4$$
$$123-y_1y_2-y_3--$$
The lecturer gives a inequality as follows $$\text{Total possible number of alignment}\ >\sum\limits_{k=0}^n {m\choose k}{n\choose k} $$
Can any one tell me the interpretation of ${m\choose k}{n\choose k}$, I don't see the meaning of number of ways to select $k$ in $m$ multiply the number of ways to select $k$ in $n$.
Any comments will be appreciated
I'm now thinking you're asking about the number of ways to shuffle a string $s$ of length $m$ and a string $t$ of length $n$, assuming all letters are distinct. This is just $\binom{n+m}{m}$: for the $n+m$ locations in the combined word, choose $m$ of them to come from the first word (with the rest coming from the second word). It turns out $$\binom{n+m}{n} = \sum_{k=0}^{\min\{n, m\}} \binom{n}{k} \binom{m}{k}.$$ (You wrote > instead of = apparently in error?)
This is a special case of the Vandermonde convolution identity and can be proven using any of the usual techniques. You can for instance let $k$ be the number of letters coming from the first string $s$ among the first $m$ positions of the combined word.