Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.