子序列在给定的序列号 [英] Number of sub-sequences in a given sequence

问题描述

如果我给一个序列 X = {X1，X2，... XM} ，那么我将有（2 ^ M ）序列。 任何人都可以请解释我怎么能在这个公式直观地到达？ 我可以开始用3个元素，然后4，然后5，并到达这个公式，但我不认为我明白了。哪儿来的2是从哪里来的？我不是分裂成两半或任何东西。 感谢您的帮助。

If I am given a sequence X = {x1,x2,....xm}, then I will have (2^m) subsequences. Can anyone please explain how can I arrive at this formula intuitively? I can start with 3 elements, then 4 and then 5 and arrive to this formula, but I don't think I understand. Where did the '2' come from? I am not dividing in half or anything here. Thank-you for the help.

推荐答案

首先，你所谈论的是叫做设置。其次，它是正确的，可以生成出的一组不同的子组的数量等于2 ^ m，其中m是在该组的元素的数量。我们可以在这个结果到达如果我们把3个元素的例子：

First of all, what you are talking about is called a set. Second, it is correct that the number of distinct sub-sets that can be generated out of a set is equal to 2^m where m is the number of elements in that set. We can arrive at this result if we take an example of 3 elements:

S = {a, b, c}

现在来生成每个子集，我们可以使用一个二进制数字建模元素的presence：

Now to generate every sub-set we can model the presence of an element using a binary digit:

xxx where x is either 0 or 1

现在，让我们列举所有可能：

Now lets enumerate all possibilities:

000 // empty sub-set
001
010
011
100
101
110
111 // the original set it self!

让我们 011 作为一个例子。第一个数字是0，那么， A 是不是在这个子集，但 B 和Ç 确实存在，因为它们各自的二进制数均为1。现在，给定的米（例如3在上面的例子中）的二进制数字，多少二进制数（子集）可以生成？你应该回答这个问题，到现在;）

Lets take 011 as an example. The first digit is 0 then, a is not in this subset, but b and c do exist because their respective binary digits are 1's. Now, given m(e.g 3 in the above example) binary digits, how many binary numbers(sub-sets) can be generated? You should answer this question by now ;)

这篇关于子序列在给定的序列号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！