Let's start with a warm up problem.
Suppose I am given two binary vectors $x, y \in \{0, 1\}^n$ of length $n$ that differ in exactly $r$ places, i.e. $||x-y||_0=r$, i.e. their hamming distance is $r$.
Now I want to compute the size of following set: $$ S_{a,b} = \{ z ~~\vert~~ ||x-z||_0 = a, ||y-z||_0 = b \} $$
Intuitively, the set $S_{a,b}$ contains all vectors that are exactly $a$ bits apart from $x$ and at the same time $b$ bits apart from $y$.
First, we notice that we can re-order the dimensions of $x$ and $y$ such that they disagree in the first $r$ dimensions and agree in the remaining $(n-r)$ dimensions without loss of generality.
To compute $\vert S_{a,b}\vert$ imagine the we look at the vectors $z$ where we "flip" $i$ zeros in the first $r$ bits where $x$ and $y$ disagree, and we flip the rest $a-i$ bits in the remaining $(n-r)$ dimensions. There are $\binom{r}{i}\binom{n-r}{a-i}$ such vectors. But in order to satisfy the other conditions it has to hold $$(r-i) + (a-i) = b$$
since $y$ should be $(r-i)$ apart from $z$ in the first $r$ dimensions (in order to be the complement of $x$) and $(a-i)$ bits apart in the remaining $(n-r)$ dimensions (in order to match $x$).
Solving for $i$ we get $i=\frac{a-b+r}{2}$ and plugging it in we get that the size of the region in question for even $(a+b-r)$ is $$ \vert S_{a,b} \vert=\binom{r}{\frac{a-b+r}{2}}\binom{n-r}{\frac{a+b-r}{2}} $$
Now onto the real question.
Suppose we can partition our $x, y, z$ into subspaces of equal size, i.e. $x=[x_1, \dots, x_m]$, where each $x_i$ is of size b, making the total size $n=b\cdot m$. Similarly we partition $y$ and $z$.
Now I want to compute the size of the following region:
$$ S_{a,b,c} = \{ z ~~\vert~~ ||x-z||_0 = a, ||y-z||_0 = b, \\ \sum_{i=1}^m\mathbb{I} ( ||x_i - z_i||_0 > 0 ) <= c, \\\sum_{i=1}^m\mathbb{I} ( ||y_i - z_i||_0 > 0 ) <= c \} $$
Intuitively, this region contains the same vectors as before with the additional constraint that when $x$ and $z$ differ they can do so in at most $c$ partitions.
I tried to approach this in a similar manner as before without any luck. We can do a similar "trick" with re-ordering the dimensions per partition. One idea would be to compute the size of some other smaller sets and combine them to obtain the size of $S_{a,b,c}$.
A variant of the problem would be to specify how much $x$ and $y$ differ per partition i.e. specify $r_i=||x_i - y_i||_0$ for all $i=1,\dots, m$ and compute the size of $S_{a,b,c}$ then.
Yet another variant would be to add specify $\sum_{i=1}^m\mathbb{I} ( ||x_i - y_i||_0 > 0 ) <= d$, i.e. that $x$ and $y$ themselves differ in at most $d$ partitions.
For both of these variants I can conclude that if $2c<d$, or for more than $2c$ partitions $r_i>0$'s then the size of the region $S_{a,b,c}$ must be $0$.
Any thoughts or helpful references or different ideas on how to approach this problem? What if only have 2 partitions for $x, y, z$ rather then $m$?
A brute-force solution would be to enumerate all $z$'s and simply count how many satisfy the given constraints but that would not scale since I need to compute the size of $S_{a,b,c}$ for many different combinations of $a$ and $b$.
