Number of sub-sequences in a given sequence

Question

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.

Answer 1

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} 

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! 

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 ;)