I am reading chapter 15 from CLRS and came across this definition of a subsequence:
A subsequence of a given sequence is just the given sequence with zero or more elements left out.
Later it is said that:
Each subsequence of X corresponds to a subset of the indices {1, 2, 3...m} of X. Because X has 2^m subsequences...
I don't see how X can have 2^m subsequences. From what I understand, if
X = {A, B}, then the subsequences of X can be {A}, {B} and {A, B} so we have 3 subsequences and not 2^2. Could someone please show me what I am missing here?
There is one empty subset.
For any set S the power set of S is the number of subsets possible which is 2^|S| where |s| is the cardinality of the set, i.e number of elements in the set.
In your case the sequence is nothing but a set and the number of subsequence possible is equivalent to the power set of the sequence.
In your example X = {A, B} the possible sub sequences are {empty, A, B ,AB}