4
$\begingroup$

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)$?

$\endgroup$
  • $\begingroup$ Hint: Fix some $k$ (e.g. $k = 2$ or $k=3$) and some $r$ and compute your numbers for consecutive $m$. Then, fix e.g. $m$ and let $r$ vary. Put the sequences you find into OEIS and look what turns up. $\endgroup$ – Dirk Jun 2 '17 at 10:12
3
$\begingroup$

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*}

$\endgroup$
  • $\begingroup$ @N.Younger: Thanks! Good to see, the answer is useful! :-) $\endgroup$ – Markus Scheuer Jul 20 '17 at 12:57
  • 1
    $\begingroup$ @N.Younger: You're welcome! It is correct, since $\frac{1}{1-a+b}=\frac{1}{1-(a-b)}=\sum_{n=0}^\infty (a-b)^n$ whenever $|a-b|<1$. $\endgroup$ – Markus Scheuer Jul 21 '17 at 9:40
  • 1
    $\begingroup$ @N.Younger: Binomial theorem. . . . Maybe you should take a small rest? .. . :-) $\endgroup$ – Markus Scheuer Jul 21 '17 at 10:16
  • 1
    $\begingroup$ @N.Younger: A standard reference is this paper by D.E. Knuth. See also section 3.6 in Sprugnolis Introduction to Mathematical Methods in Combinatorics. $\endgroup$ – Markus Scheuer Jul 21 '17 at 14:03
  • 1
    $\begingroup$ Yeah, I got the same result. I had an mistake. ;-) $\endgroup$ – N. Younger Jul 25 '17 at 8:00
1
$\begingroup$

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".

Consec_zeros_1

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.