3
$\begingroup$

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?

  • 0
    @Nick I have merged your question into this one, since the question is essentially the same.2011-07-18

6 Answers 6

-1

Its not necessay that evey number has total subsequence is equal to 2^n. For e.g: number 12345 has following subsequence equal to 25 only. 2^n are number of subsets... --> 1 2 3 4 5 --> 12 13 14 15 23 24 25 34 35 45 --> 123 124 125 234 235 345 --> 1234 1235 1245 1345 2345 --> 12345

  • 0
    @pkm You've missed something. It took me a while to realize that subsequences were subsets. Try at it again.2018-03-30
8

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$.

3

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.

In your example, the powerset of your sequence A contains

$\{\}, \{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.

  • 0
    Isn't this subsets, not subsequences since sequences are well.. sequential?2018-02-19
3

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.

1

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.

1

Another way of thinking about this problem:

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.