Cardinality of the set of all subsequences of a sequence What is the cardinality of the set of all distinct subsequences of (an infinite) sequence?
Roughly speaking, how many distinct subsequences of a sequence are there?
 A: If all the terms are distinct, then it is necessarily the same as the cardinality of the collection of all strictly increasing sequences of natural numbers. This is the same as the cardinality of the collection of all sequences of natural numbers. Intuitively this is because no matter how large the $k$th term of our sequence is, we still have denumerably many choices for the value of the $(k+1)$th term. The same goes through if there is any particular subsequence consisting entirely of distinct terms (i.e. if there are infinitely many distinct elements in the original sequence).
However you prove the above, it is easy to see that $|\mathbb{N}^{\mathbb{N}}| \geq |2^{\mathbb{N}}|$, and so you just need to show that $|\mathbb{N}^{\mathbb{N}}| \leq |2^{\mathbb{N}}|$ in order to conclude (by Cantor-Schroder-Bernstein) that your set has the cardinality of the continuum.
A: As has been hinted at, there is essentially one problem case: when the sequence is constant after some finite time. In other words, when a single value $a$ is the value in all but finitely many entries. The combinatorics of this case are a bit beyond me, but the size of the collection of subsequences will be finite. 
In all other cases, it has cardinality $2^{\aleph_0}$, the cardinality of the continuum (assuming your sequences have countable length). Note first that the collection of subsequences has at most the cardinality of the set of all subsets of $\mathbb{N}$. If there are infinitely many distinct values in the sequence, then restrict consideration to a subsequence with all values distinct, all infinite subsets correspond to a distinct sequence, and there are only countably many finite subsets. If the sequence takes on only finitely many distinct values, but doesn't fall into the case from the first paragraph, then there are two values $a, b$ both occuring infinitely many times. You can check that this implies every sequence of $a$'s and $b$'s is a subsequence of our sequence, and thus again, we achieve cardinality $2^{\aleph_0}$.
