# Coding theory (combinatorics?)

Let $l, h, s$ be positive integers less than $n$ such that $h + l - s$ is an even positive integer. Let $x$ be a binary word of length $n$. Suppose the weight of $x$ is $l$. Determine the number of binary vectors of weight $h$ which are at distance $s$ from $x$.

Weight = No. of $1$'s in a vector. For eg, $0011011$ has weight $4$. Distance = No. of places that are different between $2$ vectors. For eg, $001101$ and $001111$ has distance $1$.

-

Without loss of generality, we may assume the word looks like this:

$$\overbrace{11\dots 1}^{\ell}\overbrace{00\dots 0}^{n-\ell}.$$

Assume we change $a$ of the $1$'s and $b$ of the $0$'s. The weight of the new word will be $\ell -a + b = h$. The distance between both words will be $s = a+b$. Under the given assumptions, these equations have a unique solution $(a,b)$ and the answer is then given by $$\binom{\ell}{a} \binom{n-\ell}{b}$$

Added: The solution is given by \begin{align*} a &= \frac{\ell+s-h}{2} \\ b &= \frac{h+s-\ell}{2} \end{align*} We know that $h+\ell-s$ is even, therefore $\ell+s-h$ and $h+s-\ell$ is even as well. (Parity ignores signs.) But the extra conditions that $$0 \leq a \leq \ell \text{ and } 0\leq b \leq n-\ell$$ must be met as well. If these conditions are satisfied, the number of such words are indeed given by the formula above; if not then there are no such words.

-
Thank you. May I ask why is the property h+l-s is an even postive integer necessary in the question and how does it affect the solution? –  newbowl Jan 27 '12 at 17:58
It comes from the condition that such a and b must exist. I've expanded my answer a bit. –  Myself Jan 27 '12 at 18:09
Hey thanks a lot, friend! <3 –  newbowl Jan 28 '12 at 2:47
@newbowl: glad I could help :-) (By the way, if you like an answer, you may "accept" it: it means clicking the thing beneath the vote-arrows besides the answer. That way other people know the question has been answered sufficiently.) –  Myself Jan 28 '12 at 15:02
Ok! Answer accepted! –  newbowl Jan 29 '12 at 2:45
show 1 more comment