On the Number of Subsequences in the Nonbinary Deletion Channel
This work provides theoretical bounds for deletion channels, relevant to coding theory and information theory, but is incremental as it extends binary results to non-binary strings.
The paper studies the number of subsequences of non-binary strings under t deletions, showing that the maximum number depends on the number of runs. It characterizes a family of r-run non-binary strings achieving the maximum and provides a polynomial-time computation method.
In the deletion channel, an important problem is to determine the number of subsequences derived from a string $U$ of length $n$ when subjected to $t$ deletions. It is well-known that the number of subsequences in the setting exhibits a strong dependence on the number of runs in the string $U$, where a run is defined as a maximal substring of identical characters. In this paper we study the number of subsequences of a non-binary string in this scenario, and propose some improved bounds on the number of subsequences of $r$-run non-binary strings. Specifically, we characterize a family of $r$-run non-binary strings with the maximum number of subsequences under any $t$ deletions, and show that this number can be computed in polynomial time.