Given a binary string of length $n$, how many distinct binary strings have Hamming distance at most $k$ from it?

There are ${n \choose k}$ sets of $k$ locations to flip a bit but many of those overlap. Is there a simple closed form for the value I am looking for?


You would have to count every bitstring that has edit distance $x$ from your original bitstring $b$ for all $x \leq k$. So the sum you're looking for is $$S = \sum_{x=0}^k {n \choose x}$$ which has no closed-form expression in general, unfortunately.

| cite | improve this answer | |
  • $\begingroup$ Do you mean edit distance or Hamming distance? $\endgroup$ – fomin Jan 25 at 22:04
  • $\begingroup$ Yes - in this post I use Hamming distance and edit distance synonomously. $\endgroup$ – paulinho Jan 25 at 22:09

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.