# Why is the number of possible subsequences $2^n$?

If anyone here is familiar with the Lowest Common Subsequence problem, they probably know that the number of posibble subsequences in a sequence is $2^n$; $n$ being the length of the sequence.

Another way of phrasing the statement is: given the sample space $\{a,b,c,d\}$, there are $2^4 = 16$ possible events (each event being defined as a subset of the whole sample space).

I know it sounds a fairly basic question, but can anybody please explain why is this so?

-
Any element either is or isn't in a subsequence. –  Qiaochu Yuan Feb 24 '11 at 11:05
The number of subsets of an $n$-element set is $2^n$. –  Ｊ. Ｍ. Jul 17 '11 at 15:57
More elaborately: $\sum_{k=0}^n\binom{n}{k}=2^n$ (hint: binomial theorem). –  Ｊ. Ｍ. Jul 17 '11 at 16:02
@J.M. Thanks for commenting. The chapter that this problem is in is leading up to the binomial theorem. I suspect they ask this question early on in order to help me develop an intuition for the binomial theorem. To that end, can you answer the question in a way that doesn't invoke the binomial theorem? –  Nick Jul 17 '11 at 16:04
Well then, have binomial coefficients been introduced to you at this point? –  Ｊ. Ｍ. Jul 17 '11 at 16:05

If the order of the elements in each subsequence does not matter, then every subsequence is an element of the powerset of the given sequence.

$\{\}, \{a\}, \{b\}, \{c\}, \{d\}, \{a, b\}, \{a, c\}, \{a, d\}, \{b, c\}, \{b, d\}, \{c, d\}, \{a, b, c\}, \{a, b, d\},$ $\{a, c, d\}, \{b, c, d\}, \{a, b, c, d\}$

each one being considered as a subsequence.

Consider then the cardinality of the powerset: if a set A contains n elements, then the powerset of A contains $2^n$ elements.

-
@Metz : I was actually searching for a proof of the 2^n result. I was familiar with the possible outcomes. But anyways, you gave me the hint I needed, and I turned back to my discreet mathematics text. Turns out, this involves binomial theorem. Thanks for the help. :) –  user7453 Feb 24 '11 at 11:33
You do not need the binomial theorem to prove this. It follows directly from the multiplication principle. –  Qiaochu Yuan Feb 24 '11 at 11:45
@Qiaochu Yuan : The number of sets with k elements in the power set of a set with n elements will be a combination C(n,k), also called a binomial coefficient. nC0 + nC1 + nC2 ....nCn = 2^n-1 which is essentially n is this case as we're talking about algorithm complexity. –  user7453 Feb 24 '11 at 11:59
@Manish: i think what Qiaochu mean is that in this case to involve binomial theorem is just... too much:) I think the proof you propose in your comment becomes useful (and meaningful) if you consider also the order of the elements in each subsequence. Which is not the case. –  Metz Feb 24 '11 at 12:14
I mean, in this case in which you don't consider the order of the elements in each subsequence, the proof Manoj R provides suffice. Otherwise, for each subset of length k you also consider the number of its permutations: so you have C(n,0)*0! + C(n,1)*1! + C(n,2)*2! + ... + C(n,n)*n!. –  Metz Feb 24 '11 at 12:29

Either include A or exclude A. 2 possibilities.

Either include B or exclude B. 2 possibilities.

Either include C or exclude C. 2 possibilities.

Either include D or exclude D. 2 possibilities.

So the answer is $2\times2\times2\times2$.

-

Let us take as an example a somewhat larger problem, with a sample space of $6$ rather than your $4$. Bhaskara, more than $800$ years ago, posed and solved a similar problem. There are $6$ basic flavours, sweet, sour, salty, bitter, pungent, and astringent. How many different combinations of flavours are possible?

Let us imagine that bowls of these flavouring ingredients are lined up in front of a cook. Call the bowls A, B, C, D, E, and F.

The cook wants to create a combination of flavours by taking a tablespoon of flavouring ingredient out of some (possibly all, possibly none) of the bowls, and not using the remaining flavouring ingredients. So (s)he stops in front of each bowl, going from left to right, and makes a decision.

Let us summarize what the cook chooses to do by using a $6$-letter word over the alphabet that consists of the "letters" $0$ and $1$.

For example, $011001$ will mean that the cook did not use ingredient A, used B and C, did not use D and E, but used F.

It should be clear that there are exactly as many ways to choose a combination of flavourings as there are "words" of length $6$ over the alphabet $\{0,1\}$. You may already know that there are $2^6$ such words. But let us look at things from the viewpoint of the cook.

The cook stops briefly in front of bowl A. The cook has $2$ choices as to what to do: use A or not use A. For each such choice, the cook has $2$ choices about whether to use flavour B. For every choice about what to do with A and B, the cook has $2$ choices about what to do about C. And so on.

Thus in total the cook has $$2\times 2\times 2\times 2 \times 2 \times 2$$ ways of deciding about the flavourings.

This is $2^6$, or $64$. Actually, Bhaskara got an answer of $63$, for he did not count the possibility of saying no to each flavouring, that is, of choosing the empty set of flavourings. I guess he had not heard about English cooking.

-

The proof can be given by induction. For set of n elements, the number of subsets are $2^n$. For the set of n + 1 elements, you can take the previous $2^n$ elements and add the (n + 1)th element in each of these sets. So now you have $2^n$ (original subsets) + $2^n$ (new subsets). It is simple to see the result now. I haven't mentioned base case as it is elementary.

-

For any given sub-sequence a specific element can either be included or excluded. This means you have 2 possibilities for each element and a total of n-elements. Thus there are $2^n$ possible ways to generate a sub-sequence.
Another possible way to wrap your head around the concept. Think of every sub-sequence as containing $n$ blank spaces, each corresponding to one of the elements of your original sequence. You can then fill each of these blanks with either a 1 to denote the inclusion of that element or a 0 to denote the exclusion of that element. That gives 2 possibilities for each blank. There are n blanks, thus $2^n$ possible sub sequences.
You have listed 28 subsequences, not 25, and you are missing 134, 135, 145, 245. That makes $32 = 2^5$. –  Nate Eldredge Aug 1 '12 at 21:52