m symbols, then
X has 2m possible subsequences.
Where does the base (
2) come from?
The origin of this question is the following paragraph:
We are given two ordered sequences of symbols, and we wish to find a longest common subsequence of $X$ and $Y$.
A subsequence of $X$ is just $X$ with some (or possibly all or none) of its elements removed. For example, one subsequence of
A; B; C; D; E; F; Gwould be
B; C; E; G.
The length of a longest common subsequence of $X$ and $Y$ gives one measure of how similar these two sequences are. For example, if the two sequences are base pairs in DNA strands, then we might consider them similar if they have a long common subsequence.
If $X$ has $m$ symbols and $Y$ has $n$ symbols, then $X$ and $Y$ have $2^m$ and $2^n$ possible subsequences respectively.