给定序列中的子序列数

Question

如果给我一个序列X = {x1,x2,....xm},那么我将有(2^m)后续序列.任何人都可以解释我如何直观地得出这个公式？我可以从3个元素开始,然后是4个然后是5个并且达到这个公式,但我认为我不理解.'2'来自哪里？我不是在这里分成两半或任何东西.感谢您的帮助.

Answer 1

对于实际上正在寻找子字符串的任何人(因为标题或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)

Answer 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)二进制数字,可以生成多少个二进制数(子集)？你现在应该回答这个问题;)

Answer 3

值x_i可以在子序列中,也可以不在子序列中.这有点像.有2^m用于打开/关闭m序列中数字的组合.

Answer 4

2是哪里来的？每次增加一个元素，可能性就会增加一倍。

Answer 5

对于任何序列 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

Answer 6

对于长度顺序中的每个元素m，您可以选择或保留它。因此，有两种方式处理每个元素。因此，总编号。处理所有m元素的方式是2*2*2...... m时间= 2^m时间。