关于子序列- CLRS

Question

我正在阅读CLRS的第15章，并找到了子序列的定义：

给定序列的子序列只是一个给定的序列，忽略了零个或多个元素。

后来有人说：

X的每个子序列对应于X的指数{1，2，3.m}的子集，因为X有2^m子序列.

我不明白X怎么能有2^m子序列。据我所知，如果是X = {A, B}，那么X的子序列可以是{A}，{B}和{A, B}，所以我们有3个子序列，而不是2^2。有人能给我看看我在这里错过了什么吗？

Answer 1

只有一个空子集。

对于任意集合S，S的幂集是可能的子集数，为2^x-S_x，其中s_x为集合的基数，即集合中元素的个数。

在您的例子中，序列只不过是一个集合，可能的子序列数相当于序列的幂集。

在您的示例X= {A，B}中，可能的子序列是{空的，A，B，AB}