Number of sequences that contain a certain subsequence

Question

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.

Answer 1

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