Minimum size of insertion/deletion/substitution balls

Abstract

Let $n,q,t,s,p$ be non-negative integers where $n\ge s$ and $q\ge 1$. For $\mathbf{x}\in A_q^n\triangleq \{0,1,\dots ,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})|\ge {\sum }_{i=0}^{t+p}\left(\genfrac{}{}{0ex}{}{n+t-s}{i}\right)(q-1{)}^i$, with equality holding if and only if $t=s=0\vee s=p=0\vee s+p\ge 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.