3
$\begingroup$

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$.

1 Answers 1

3

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.

  • 0
    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?2012-01-27
  • 0
    It comes from the condition that such a and b must exist. I've expanded my answer a bit.2012-01-27
  • 0
    Hey thanks a lot, friend! <32012-01-28
  • 0
    @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.)2012-01-28
  • 0
    How I will be able to interpret the combinatoria product?2012-12-12