Number of sequences that contain a certain subsequence Consider a given sequence of length $k$. I want to calculate the number of sequences of length $n$ that contains the given sequence as a subsequence. The alphabet used to generate the string consists of $|A|$ values.
For example, a sequence "120" is given. in this case, k=3. Consider the alphabet to be $A=\{0,1,2,3\}$ and $n=5$. In this case, two of the possible sequences are:
10230
12320

And the question becomes the total number of sequences of length 5 which contain "120" as a subsequence. The important part here is that the given subsequence is not necessarily contained in the sequence, which is clear by the provided examples.
I know this problem can be solved by using the principle of inclusion-exclusion. However, I was looking for a more straightforward and probably a closed-form equation for this problem.
Thank you in advance for your help.
 A: Let $T$ be your given sequence of length $k$, and $d$ the size of the alphabet.  Let $A(k,n)$ be the set of sequences $S$ of length $n$ such that  $T$ forms a subsequence of $S$. 
It looks to me like $$|A(k,n)| = \sum_{j=0}^{n-k} {n \choose j+k} (d-1)^{n-k-j}$$ 
EDIT:  This can be seen as follows.  Let $p_k$ be the position of the last occurrence of $T_k$
in $S$, and for $1 \le j < k$ let $p_j$ be the last occurrence of $T_j$ before $p_{j+1}$.  In order for $S \in A(k,n)$ we need all $p_j \ge 1$.  Conversely, given a choice of $p_1, \ldots, p_k$ with $1 \le p_1 \le \ldots \le p_k \le n$, 
there are $ d^{p_1-1} (d-1)^{n-k-p_1}$ members of $A(k,n)$ where
$S_{p_j} = T_j$, for $p_j < i < p_{j+1}$ (or $n$ in the case $j=k$) $T_i$ can be any symbol except $T_j$, and for $1 \le i < p_1$, $T_i$ can be any symbol. To get a sum just involving a power of $d-1$ rather than both $d$ and $d-1$, we also look
at the occurrences of $T_1$ before $p_1$. The term ${n \choose j+k} (d-1)^{n-k-j}$ comes from the case where there are $j$ occurrences of $T_1$ in $S_{1..p_1-1}$. 
