X = {x1,x2,....xm}，那么我将拥有 (2^m) 个子序列。
能否有人解释一下如何直观地得出这个公式？
我可以从3个元素开始，然后是4个，最后是5个，推导到这个公式，但我不认为我理解了。这个“2”是从哪里来的？我没有进行任何除以二之类的操作。
谢谢您的帮助。首先，你所谈论的是一个集合。其次，确实可以从一个集合中生成的不同子集数量等于2^m，其中m是该集合中元素的数量。我们可以通过以3个元素为例来得出这个结果：
S = {a, b, c}
现在，为了生成每个子集，我们可以使用二进制数字来表示元素的存在：
xxx where x is either 0 or 1
现在让我们枚举所有可能性：
000 // empty sub-set
001
010
011
100
101
110
111 // the original set it self!
011为例。第一个数字是0，那么a不在这个子集中，但是b和c存在，因为它们各自的二进制位是1。现在，给定m（例如上面例子中的3）个二进制位，可以生成多少个二进制数（子集）？你应该现在就能回答这个问题 ;)对于那些真正寻找子字符串的人（如标题或URL所示）：
Subset: 2^n (Order doesn't matter in sets)
Subsequence: 2^n (Since we keep the original ordering, this is the same.)
Substring: n(n+1) * 1/2 (Elements must be consecutive)
2 * 2 * 2 ...... m 次= 2 ^ m 次。变量 x_i 可能在子序列中，也可能不在。这就像一个比特位。在序列中，有 2^m 种组合来打开/关闭序列中的 m 个数字。
对于任何序列X = {x1，x2，....xm}，都会有(2^m)个子序列，因为您可以“选择”长度为0、1、2、...、m的子序列，也就是说，在数学上，它是
"C(m,0) + C(m,1) + ... C(m,m)" ，这导致了2^m。
例如，假设字符串是“abc”，那么
C(3,0) = 1， ""
C(3,1) = 3， "a"， "b"， "c"
C(3,2) = 3， "ab"， "bc"， "ac"
C(3,3) = 1， "abc"
子序列的数量为8，即2^3。
有关更多详细信息，请访问http://en.wikipedia.org/wiki/Binomial_coefficient#Series_involving_binomial_coefficients。
=> C(3, 0) + C(3, 1) + C(3, 2) + C(3, 3) = 1 + 3 + 3 + 1 = 8 (2^3).
C(3, 0) = '', // Taking 0 letters at a time out of the given string.
C(3, 1) = 'A', 'B', 'C', // Taking 1 letter at a time.
C(3, 2) = 'AB', 'AC', 'BC', // Taking 2 letters at a time.
C(3, 3) = 'ABC'. // Taking 3 letters at a time.
(Total count = 8)
From Binomial theorem,
(x + y)^n = C(n, 0) x^n y^0 + .... + C(n, n) x^0 y^n
Using x = 1, y = 1,
(1+1)^n = C(n, 0) 1^n 1^0 + .... + C(n, n) 1^0 1^n
=> 2^n = C(n,0) + C(n,1) + .... + C(n,n)