I am considering the set of all finite and binary strings. In the following I am interested on the number $N(m,k,r)$ of strings with length $m$ and Hamming weight $r$ which do not contain $k$ consecutive zeros.
The Hamming weight $r$ is defined as the number of non-zero positions in a string.
Example: The binary string $x=1001101$ is given. The Hamming weight of $x$ is $r=4$, since $x$ contains 4 non-zero entries.
Is there a general formulary for computing $N(m,k,r)$?
Let $N(m,k,r)$ denote the number of binary strings with length $m$ and Hamming weight $r$ which do not contain zero-runs of length $k$.
The following is valid for $m\geq 1, k\geq 1, 0\leq r\leq m$ \begin{align*} N(m,k,r)&=\sum_{j= 0}^{\min\left\{r,\left\lfloor \frac{m}{k}\right\rfloor\right\}}\binom{m-kj}{j}\binom{m-(k+1)j}{r-j}(-1)^j\\ &\qquad-\sum_{j= 0}^{\min\left\{r,\left\lfloor \frac{m-k}{k}\right\rfloor\right\}}\binom{m-k-kj}{j}\binom{m-k-(k+1)j}{r-j}(-1)^j\tag{1} \end{align*}
In order to determine the number $N(m,k,r)$ we consider words with no consecutive equal characters at all.
These words are called Smirnov words or Carlitz words. (See example III.24 Smirnov words from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for more information.)
A generating function for the number of Smirnov words over a binary alphabet is given by \begin{align*} \left(1-\frac{2z}{1+z}\right)^{-1}\tag{2} \end{align*}
The number $N(m,k,r)$:
In order to set up for the binary strings we are looking for, we replace occurrences of $0$ in a Smirnov word by one up to $k-1$ zeros. This corresponds to a substitution of \begin{align*} z&\longrightarrow z+z^2+\cdots+z^{k-1}=\frac{z\left(1-z^{k-1}\right)}{1-z}\tag{3}\\ \end{align*} We replace occurrences of $1$ in a Smirnov word by any run of $1$'s with length $\geq 1$. \begin{align*} z&\longrightarrow z+z^2+z^3+\cdots=\frac{z}{1-z}\tag{4}\\ \end{align*}
We obtain a generating function $A(z,t)$ by substituting (3) and (4) in (2) and additionally marking each occurrence of one with $t$ in order to keep track of the Hamming-weight \begin{align*} A(z,t)&=\left(1-\frac{\frac{zt}{1-zt}}{1+\frac{zt}{1-zt}}-\frac{\frac{z\left(1-z^{k-1}\right)}{1-z}}{1+\frac{z\left(1-z^{k-1}\right)}{1-z}}\right)^{-1}\\ &=\frac{1-z^k}{1-(t+1)z+tz^{k+1}}\\ \end{align*}
We denote with $[z^n]$ the coefficient of $z^n$ in a series.
We obtain using the geometric series expansion:
\begin{align*} \color{blue}{N(m,k,r)}&=[z^mt^r]A(z,t)\\ &=[z^mt^r]\frac{1-z^k}{1-(t+1)z+tz^{k+1}}\\ &\color{blue}{=[z^mt^r](1-z^k)\sum_{j=0}^\infty z^j\left((t+1)-tz^k\right)^j}\tag{5} \end{align*}
According to the factor $(1-z^k)$ in (5) we split the expression into two sums.
We start with
\begin{align*} \color{blue}{[z^mt^r]}&\color{blue}{\sum_{j=0}^\infty z^j\left((t+1)-tz^k\right)^j}\\ &=[t^r]\sum_{j=0}^m[z^{m-j}]\sum_{l=0}^j\binom{j}{l}(-1)^lt^lz^{kl}(t+1)^{j-l}\tag{6}\\ &=[t^r]\sum_{j=0}^m[z^j]\sum_{l=0}^{m-j}\binom{m-j}{l}(-1)^lt^lz^{kl}(t+1)^{m-j-l}\tag{7}\\ &=[t^r]\sum_{j=0}^{\lfloor m/k\rfloor}[z^{kj}]\sum_{l=0}^{m-kj}\binom{m-kj}{l}(-1)^lt^lz^{kl}(t+1)^{m-kj-l}\tag{8}\\ &=[t^r]\sum_{j=0}^{\lfloor m/k\rfloor}\binom{m-kj}{j}(-1)^jt^j(t+1)^{m-(k+1)j}\tag{9}\\ &=\sum_{j=0}^{\min\left\{r,\left\lfloor \frac{m}{k}\right\rfloor\right\}}\binom{m-kj}{j}(-1)^j[t^{r-j}](t+1)^{m-(k+1)j}\tag{10}\\ &\color{blue}{=\sum_{j=0}^{\min\left\{r,\left\lfloor \frac{m}{k}\right\rfloor\right\}}\binom{m-kj}{j}\binom{m-(k+1)j}{r-j}(-1)^j}\tag{11}\\ \end{align*}
Comment:
In (6) we use the linearity of the coefficient of operator and apply the rule $[z^{p-q}]G(z)=[z^p]z^{q}G(z)$. We also set the upper limit of the sum to $m$ since the exponent of $z^{m-j}$ is non-negative.
In (7) we change the order of summation $j\rightarrow m-j$.
In (8) we note the exponent of $z$ has to be a multiple of $k$ due to the factor $z^{kl}$ in the inner sum. We set $j\rightarrow kj$ accordingly.
In (9) we select the coefficient of $z^{kj}$.
In (10) we do a similar job with $[t^r]$ as we did with $[z^m]$ in (6).
In (11) we select the coefficient of $t^{r-j}$.
Conclusion: We observe the sum in (11) is the first sum stated at the right hand side of (1). According to the factor $(1-z^k)$ in (5) we obtain the second sum by replacing $m$ with $m-k$ and the claim follows. $$\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\Box$$
Finally we look at an example.
Example: $N(m,k,r)$ with $m=7,k=3$ and $r=4$
In accordance with OPs example string we calculate \begin{align*} \color{blue}{N(7,3,4)}&=\sum_{j}\binom{7-3j}{j}\binom{7-4j}{4-j}(-1)^j-\sum_{j}\binom{4-3j}{j}\binom{4-4j}{4-j}(-1)^j\\ &=\left(\binom{7}{0}\binom{7}{4}-\binom{4}{1}\binom{3}{3}\right)-\left(\binom{4}{0}\binom{4}{4}-\binom{4}{1}\binom{0}{3}\right)\\ &=(35-4)-(1-0)\\ &\color{blue}{=30} \end{align*}
The corresponding $30$ strings with length $7$, Hamming distance $4$ and no zero-runs of length $3$ are \begin{array}{ccccc} 0010111&0011011&0011101&0011110&0100111\\ 0101011&0101101&0101110&0110011&0110101\\ 0110110&0111001&0111010&0111100&1001011\\ 1001101&1001110&1010011&1010101&1010110\\ 1011001&1011010&1011100&1100101&1100110\\ 1101001&1101010&1101100&1110010&1110100 \end{array}
Note: Here is some more detailed information to (6) due to OPs comment \begin{align*} \color{blue}{[z^mt^r]}&\color{blue}{\sum_{j=0}^\infty z^j\left((t+1)-tz^k\right)^j}\\ &=[t^r]\sum_{j=0}^m[z^m]z^j\left((t+1)-tz^k\right)^j\\ &=[t^r]\sum_{j=0}^m[z^m]z^j\left(-tz^k+(t+1)\right)^j\\ &=[t^r]\sum_{j=0}^m[z^m]z^j\sum_{l=0}^j\binom{j}{l}(-tz^k)^l(t+1)^{j-l}\\ &=[t^r]\sum_{j=0}^m[z^{m-j}]\sum_{l=0}^j\binom{j}{l}(-1)^lt^lz^{kl}(t+1)^{j-l}\tag{6}\\ \end{align*}
So you are looking for $N(m,k,r)=$ number of binary strings with:
length $=m$, Hamming weight $=$ number of ones$=r$, and which
"do not contain $k$ consecutive zeros".
Taking the complement of the string (exchanging the zeros and ones), that is the same as:
length $=m$, Hamming weight $=$ number of ones$=m-r$, and which
"do not contain $k$ consecutive ones".
Consider a binary string with $s$ "$1$"'s and $q$ "$0$"'s in total. Let's put an additional (dummy) fixed $0$ at the start and at the end of the string. We individuate as a run the consecutive $1$'s between two zeros, thereby including runs of null length. With this scheme we have a fixed number of $q+1$ runs. If we sequentially enumerate the length of each run so individuated, we construct a bijection with the number of ways of putting $s$ (undistinguishable) balls into $q+1$ (distinguishable) bins. Now consider the case in which runs have a max length of $t$ ones, or that the bins have a limited capacity of $t$ balls, or otherwise the $$ \bbox[lightyellow] { N_b (s,r,q + 1) = {\rm No}{\rm .}\,{\rm of}\,{\rm solutions}\,{\rm to}\;\left\{ \matrix{ {\rm 0} \le {\rm integer}\;x_{\,j} \le r \hfill \cr x_{\,1} + x_{\,2} + \; \cdots \; + x_{\,q + 1} = s \hfill \cr} \right. }$$ which as explained in this other post is expressed as $$ \bbox[lightyellow] { N_b (s,t,q + 1)\quad \left| {\;0 \le {\rm integers }s,q,t} \right.\quad = \sum\limits_{\left( {0\, \le } \right)\,\,j\,\,\left( { \le \,{s \over t}\, \le \,q + 1} \right)} {\left( { - 1} \right)^j \left( \matrix{ q + 1 \cr j \cr} \right)\left( \matrix{ s + q - j\left( {t + 1} \right) \cr s - j\left( {t + 1} \right) \cr} \right)} }$$ (which essentially is derived from the inclusion-exclusion principle).
Then, using your symbols, the number of strings with
length $=m$, Hamming weight $=$ number of ones$=r$, and which
" contain runs with max $k-1$ consecutive zeros", equivalent to
length $=m$, Hamming weight $=$ number of ones$=m-r$, and which
" contain runs with max $k-1$ consecutive ones", is given by
$$ \bbox[lightyellow] {
N(m,k,r)=N_b (m - r,k - 1,r + 1)
}$$
And, as an example $N(7,3,4)=30$, as in the answer above.
Of course the number of strings with runs whatever is $N_b(m-r,m-r,r+1)={m \choose r}$.
So it is easy to compute also the number of strings with "(at least) one run of exactly $k$ consecutive ones"
etc.
See also this other related post.
|
asked |
|
|
viewed |
360 times |
|
active |
