子序列计数中的基数从何而来？

Question

如果序列 X 有 m 符号，那么 X 有 2^米 可能的子序列。

基地在哪里（2） 来自？

这个问题的由来是下面这段话：

给定两个有序的符号序列，我们希望找到最长公共子序列 $X$ 和 $Y$.

的一个子序列 $X$ 只是 $X$ 删除了一些（或可能全部或无）的元素。例如，一个子序列 A; B; C; D; E; F; G 将会 B; C; E; G.

最长共同子序列的长度 $X$ 和 $Y$ 给出了这两个序列的相似程度的一种量度。例如，如果这两个序列是DNA链中的碱基对，那么如果它们具有很长的共同子序列，我们可能会认为它们相似。

如果 $X$ 有 $百万$ 符号和 $Y$ 有 $n$ 符号，那么 $X$ 和 $Y$ 有 $2^米$ 和 $2^n$ 可能的子序列分别。

Answer 1

你可以想出一个子序列 $Y$ 的 $X$ 作为特征向量 $\chi_Y$ 具有 $百万$ 元素，每个元素一个 $X$. 。这 $i$第-个元素 $\chi_Y$ 是 $1$ 如果 $i$第-个元素 $X$ 也在 $Y$ 和 $0$ 否则。

很容易看出这是一个双射：每个子序列 $Y$ 具有明显的特征向量 $\chi_Y$, ，以及每个特征向量 $\chi_Y$ 与不同的序列相关联 $Y$.

这意味着子序列的数量 $Y$ 等于向量的数量 $\chi_Y$. 。由于每个向量 $\chi_Y$ 有 $百万$ 元素，每个元素可以具有以下之一 $2$ 可能的值，这个数字是 $2^米$.

序列的具体示例 $X$, 一个子序列 $Y$, ，及其特征向量 $\chi_Y$ 如下：