Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $\Sigma$ be an alphabet of size $s$, with which we build strings of length $n$.

The Hamming ball of radius $d$ centered at $x\in\Sigma^n$ is the set $B(x, d)$ of words in $\Sigma^n$ that differ from $x$ in at most $d$ positions.

Similarly, the Hamming circle of radius $d$ centered at $x\in\Sigma^n$ is the set $C(x, d)$ of words in $\Sigma^n$ that differ from $x$ in exactly $d$ positions (note: "Hamming ball" is a standard term, but I do not know whether the expression "Hamming circle" exists at all).

Are there closed expressions for $|B(x, d_1)\cap B(y, d_2)|$ and $|C(x, d_1)\cap C(y, d_2)|$, given any two distinct strings $x,y\in\Sigma^n$ and any two $d_1,d_2\in\mathbb{N}$?

share|improve this question
2  
I would use the term "Hamming sphere" instead of "Hamming circle", as the term sphere is used in the context of metric spaces. –  Florian Nov 9 '10 at 10:18
    
Thanks for the suggestion, but a quick Google search indicates that many authors already confuse those terms: "spheres" and "circles" are in some cases used for what I refer to as "balls". Another example however gives "Hamming sphere" yet another meaning: mathoverflow.net/questions/38221/geometry-in-a-hamming-box –  Anthony Labarre Nov 9 '10 at 10:49
2  
your Hamming circle is a what everyone calls a sphere in the metric space of words with the Hamming metric. So usin the word sphere is the only sensible thing, independently of how people confuse balls and spheres. –  Mariano Suárez-Alvarez Nov 9 '10 at 14:03

1 Answer 1

To get started, let us work on the circle intersection where the distances are the same: $|C(x,d)\cap C(y,d)|$. Let the distance between $x$ and $y$ be $m$. Then we pick $i$ places of the disagreement where we agree with $x$, have to have $i$ of the disagreement that we agree with $y$, and $d-i$ of the others where we have to disagree with both to get the correct distance. Each of those $d-i$ can have $s-2$ choices, as they have to disagree with $x$ and $y$, as can the $m-2i$ that we didn't choose to agree with x or y. So $$|C(x,d)\cap C(y,d)|=\sum_{i=0}^{\frac{m}{2}} \binom{m}{i} \binom{m-i}{i} \binom{n-m}{d-i} (d+m-3i)^{(s-2)}$$ If you can sum this, you are better than I. For the ball, we can just sum over $m$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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