Triangle with Hamming distance?

Question

Let us $x, y \in F_{2}^{n}$ such that $d(x,y) = m$. How many are there $z \in F_{2}^{n}$ such that

$d(x,z) = k , d(y,z) = r$ ?

Answer 1

Hint: With $\oplus$ denoting the bit-wise XOR, we have $$ d(x \oplus v,x \oplus w) = d(v \oplus w). $$ Thus, we can assume without loss of generality that $x = \mathbf 0$. With that in mind, we can reframe the question into the following:

Suppose that we are given a bitstring $y \in \Bbb F_2^n$ with $m$ bits on and an integer $k$. In how many ways can we flip exactly $r$ bits of $y$ in order to produce a bitstring (namely $z$) that has exactly $k$ bits on?

We note that at least one such $z$ can be produced if and only if $|m-k| \leq r$ and $m-k \equiv r \pmod 2$.

Under the assumption that this condition holds, each vector $z$ can be uniquely produced via the following procedure:

1. Select $\frac{r + m-k}{2}$ of $m$ bits that were on to be turned off,
2. Select $\frac{r - m + k}{2}$ of $n-m$ bits that were off to be turned on.