Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.07132 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929751482957824 |
|---|---|
| author | Pi, Yuhang Zhang, Zhifang |
| author_facet | Pi, Yuhang Zhang, Zhifang |
| contents | Let $n,q,t,s,p$ be non-negative integers where $n\geq s$ and $q\geq 1$. For $\mathbf{x}\in A_{q}^{n}\triangleq\{ 0,1,\ldots,q-1 \}^{n}$, let the $t$-insertion $s$-deletion $p$-substitution ball of $\mathbf{x}$, denoted by $\mathcal{B}_{t,s,p}(\mathbf{x})$, be the set of sequences in $A_{q}^{n+t-s}$ which can be obtained from $\mathbf{x}$ by performing $t$ insertions, $s$ deletions, and at most $p$ substitutions. We establish that for any $\mathbf{x}\in A_{q}^{n}$, $|\mathcal{B}_{t,s,p}(\mathbf{x})|\geq\sum_{i=0}^{t+p}\binom{n+t-s}{i}(q-1)^{i}$, with equality holding if and only if $t=s=0\vee s=p=0\vee s+p\geq n\vee r(\mathbf{x})=1$. Here, $r(\mathbf{x})$ denotes the number of runs in $\mathbf{x}$, and a run in $\mathbf{x}$ is a maximum continuous subsequence of identical symbols. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_07132 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Minimum size of insertion/deletion/substitution balls Pi, Yuhang Zhang, Zhifang Combinatorics Let $n,q,t,s,p$ be non-negative integers where $n\geq s$ and $q\geq 1$. For $\mathbf{x}\in A_{q}^{n}\triangleq\{ 0,1,\ldots,q-1 \}^{n}$, let the $t$-insertion $s$-deletion $p$-substitution ball of $\mathbf{x}$, denoted by $\mathcal{B}_{t,s,p}(\mathbf{x})$, be the set of sequences in $A_{q}^{n+t-s}$ which can be obtained from $\mathbf{x}$ by performing $t$ insertions, $s$ deletions, and at most $p$ substitutions. We establish that for any $\mathbf{x}\in A_{q}^{n}$, $|\mathcal{B}_{t,s,p}(\mathbf{x})|\geq\sum_{i=0}^{t+p}\binom{n+t-s}{i}(q-1)^{i}$, with equality holding if and only if $t=s=0\vee s=p=0\vee s+p\geq n\vee r(\mathbf{x})=1$. Here, $r(\mathbf{x})$ denotes the number of runs in $\mathbf{x}$, and a run in $\mathbf{x}$ is a maximum continuous subsequence of identical symbols. |
| title | Minimum size of insertion/deletion/substitution balls |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2503.07132 |