Number of distinct subSEQUENCES to a set that has repeated values I have tried searching for answers to this seemingly simple problem but I can't find any results. This is very similar to my previous question about number of distinct subSETS to a set that has previous values. However, subsequences are different from subsets. If $S$ is a finite set of numbers, a subsequence of $S$ consists of some terms of $S$ in its original order. For example, using my example in my previous question, the subsequences to the set $\{1, 2, 2, 1\}$ will be $$\emptyset,\{1\}, \{2\}, \{1,2\}, \{1, 1\}, \{2,2\}, \{2,1\}, \{1,2,2\},\{1,2,1\}, \{2,2,1\} ,\{1,2,2,1\}$$ for a total of $11$ subsequences. However, unlike counting subsets, I don't find an intuitive way to count the distinct subsequences of $\{1,2,2,1\}.$ Some of the subsequences of $\{1, 2, 2, 1\}$ have the exact elements in them, except I'm not sure how to determine which subsequences will have other arrangements. (For example, $\{1, 2\}$ and $\{2, 1\}$ would be considered different subsequences, though they are considered the same subset.) May I have some help approaching this? Thanks in advance.
 A: This one has a very elegant recursive solution.  Let $s_1, \ldots, s_n$ be the elements of $S$ (in order of appearance).  Let $S[1\ldots k]$ denote the partial sequence $s_1, \ldots, s_k$.  Let $a_k$ be the number of distinct subsequences of $S[1\ldots k]$, and suppose we already have calculated the values of $a_0, a_1, a_2, \ldots, a_{n-1}$ (note that $a_0 = 1$ for the trivial subsequence).

*

*If $s_n$ is different from all elements of $S\setminus \{s_n\}$, then
easily $a_n = 2 a_{n-1},$ since to get a subsequence of $S$ we
either append $s_n$ to a subsequence of $S[1\ldots n-1]$ or we leave
it as-is.  There are no duplicates within the first category or
within the second category, and there is no intersection between the
two since any subsequence containing $s_n$ cannot be a subsequence of
$S[1\ldots n-1]$.  Hence in this case, $$a_n = 2a_{n-1}.$$


*If $s_n$ is equal to some previous $s_j$ with $j<n$, then we will
have a non-trivial intersection, as exist some subsequences of
$S[1\ldots n-1]$ that remain subsequences of $S[1\ldots n-1]$
after we append $s_n$.  Still, we only need to count the number of
such redundancies.
Let $j$ be the highest index $j<n$ such that $s_j = s_n$.  Then any subsequence of $S[1\ldots n-1]$ that ends in $s_n$ must be a subsequence of $S[1\ldots j]$.  In fact the number of (distinct) such subsequences is exactly $a_{j-1}$: for any subsequence of $S[1\ldots j-1]$, appending $s_j$ gives a subsequence of $S[1\ldots n-1]$.  So we overcount by exactly $a_{j-1}$, which means that
$$a_n = 2a_{n-1} - a_{j-1}.$$
Let's work out this for your example $\{1,2,2,1\}$:
$$\begin{align}
a_0 &= 1, \\
a_1 &= 2 a_0 = 2, &\text{(first case)} \\
a_2 &= 2 a_1 = 4, &\text{(first case)} \\
a_3 &= 2 a_2 - a_1 = 6, &(s_3 = s_2) \\
a_4 &= 2 a_3 - a_0 = 11. &(s_4 = s_1)
\end{align}$$
It is relatively easy to turn this into a linear time algorithm (assuming that arithmetic is constant-time, which can be a strong assumption for an exponentially growing sequence), as the search for the highest matching index can be done very efficiently with hash tables.
