{
  "annotation_id": "cbd66cc9-bea7-4d49-b367-482049e47eb4",
  "date_created": "2026-02-17T05:53:08.035000Z",
  "date_modified": "2026-02-17T05:53:08.035000Z",
  "file_hash": "bf773dcea127895391ed0ccb2a0c7630aba7052af249107e19baba2c98a97a5e",
  "private": false,
  "record": {
    "abstract": "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.",
    "arxiv_id": "2601.06493",
    "authors": [
      "Han Li",
      "Xiang Wang",
      "Fang-Wei Fu"
    ],
    "categories": [
      "cs.IT",
      "math.CO",
      "math.IT"
    ],
    "license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
    "title": "On the Number of Subsequences in the Nonbinary Deletion Channel",
    "url": "https://arxiv.org/abs/2601.06493",
    "version": "v1"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "20aaffdb-e932-43c9-8aab-425e3a7bce77",
    "id": "arXiv Dataset",
    "type": "Model",
    "variant": "snapshot-2026-01-17",
    "version": "0.1.0"
  },
  "user_id": 1000002
}