How to calculate how many alignments are there between two strings with length n? The definition of that can be found at here sequence alignment problem. In my opinion, given two string, like "AC" and "GC", there are four possible alignments:
four alignments
But how calculate the total number of the possible alignments given strings with length n?
I search through google, found some result like $2n\choose n$, but in nowhere explain how to get this.
Any help?
Thanks!
 A: There are actually $6$ possible alignments of strings AB and CD.

*

*It may be that B matches C, but nothing else matches.

*It may be that A matches C, and B matches D.

*It may be that A matches C, but nothing else matches.

*It may be that B matches D, but nothing else matches.

*It may be that A matches D, but nothing else matches.

*Or it may be that nothing matches.

These possibilities can be diagrammed as follows:
AB           AB            A B            AB             AB            AB  
 CD          CD            CD            C D            CD           CD

Some of these could be diagrammed differently. For instance, the third and fourth could also be as follows:
AB           A B  
C D           CD

We can pin down a specific diagram by requiring that an element of the bottom string that does not match any element of the top string must appear as far to the left as possible. In the third possibility, for instance, D matches neither A nor B, so we put it as far to the left as it can go: it must come after C, but it can (and therefore must) come before B.
It turns out that the $6$ possibilities correspond to the $6$ ways in which the string AB can be merged with the string CD so that each string retains its original order: ABCD, ACBD, ACDB, CABD, CADB, and CDAB. Moreover, the requirement that I just introduced makes it easy to go back and forth between these merged strings and the diagrams above. To get the string from the diagram, start with the symbol at the upper left, and then read down, diagonally up to the right, down, diagonally up to the right, and so on, in this pattern:
$$\begin{array}{ccc}
*&&*&&*&&*&&*\\
\downarrow&\nearrow&\downarrow&\nearrow&\downarrow&\nearrow&\downarrow&\nearrow&\downarrow\\
*&&*&&*&&*&&*
\end{array}$$
Ignore blank spaces. As a further example suppose that we have the following alignment of strings ABC and DEF:
      A BC  
      DEF

We read it off in the pattern shown above, i.e., like this:
$$\begin{array}{ccc}
A&&-&&B&&C\\
\downarrow&\nearrow&\downarrow&\nearrow&\downarrow&\nearrow&\downarrow\\
D&&E&&F&&-
\end{array}$$
The result is the merged string ADEBFC. To reverse the correspondence, first locate every adjacent pair in the merged string in which an element from the top string is immediately followed by an element of the bottom string: these are the actual matches in the alignment. In the case of ADEBFC these pairs are AD and BF. Set up a partial alignment:
     A  B  
     D  F

We know that E must fall between D and F and is not part of a match:
     A B  
     DEF

And we know that C must follow B:
     A BC  
     DEF

A bit of thought should convince you that I really have described a bijection between possible alignments and merged strings. Thus, to count the alignments we need only count the merged strings. If the top and bottom strings both have $n$ elements, the merged string will have $2n$ elements. Once we know the $n$ positions occupied by the elements of the top string, we know everything: those $n$ elements must go in their proper order, and the other $n$ positions must be occupied by the $n$ elements of the bottom string, also in their proper order. There are $\binom{2n}n$ ways to choose the $n$ positions for the elements of the top string, so there are $\binom{2n}n$ possible merged strings and the same number of possible alignments.
