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
    How I will be able $t$o interpret the combinatoria product?2012-12-12