I am interested in the number of binary strings of length $m$ and Hamming weight $r$, which do not contain $k$ consecutive zeros. A nice derivation of that number is in Number of binary and constant-weight strings of length m which do not contain k consecutive zeros.

In particular, the bivariate ordinary generating function of this number is $$ F(z,t) = \frac{1-z^k}{1-(t+1)z+tz^{k+1}}$$ where $z$ is assigned with the string length and $t$ is assigned with the Hamming weight.

Now I am interested on the asymptotic behaviour of this number, when $m$ is very large. I hope that there is some simpler expression $g(m,k,r)$ for the asymptotic case, i.e $f_{m,r} \sim g(m,k,r)$ for $m \rightarrow \infty$, where $r$ is the Hamming weight. $k<m$ and we can assume that the given $k$ is very small relatively to $m$, when $m$ becomes very large.

Can someone help me with this problem?

  • $\begingroup$ Did you check OEIS? $\endgroup$ – Aryabhata Aug 1 '17 at 6:36
  • $\begingroup$ No, but I think I need a approximative expression as function of the length $m$ and Hamming weight $r$ and $k$. $\endgroup$ – N. Younger Aug 1 '17 at 6:38
  • $\begingroup$ OEIS typically gives a lot of references, which could potentially include asymptotic expressions etc. $\endgroup$ – Aryabhata Aug 1 '17 at 6:39
  • $\begingroup$ Interesting, I will look it up! $\endgroup$ – N. Younger Aug 1 '17 at 6:40

Your Answer

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

Browse other questions tagged or ask your own question.