1
$\begingroup$

So, here's once again this article from topcoder about combinatorics. After the article successfully describes what theory it will use: Combinations/Permutations, it goes into an application for it, ie. Binary Vectors. There are a number of properties for them that I don't quite understand, especially this one (#3)

  1. The number of ordered pairs (a, b) of binary vectors, such that the distance between them (k) can be calculated as follows:

enter image description here

Where does this formula come from?

Moreover, there's an example about the previous formula statement:

The distance between a and b is the number of components that differs in a and b — for example, the distance between (0, 0, 1, 0) and (1, 0, 1, 1) is 2).

Could someone please explain to me how does binary vector(s) distance is done? I need to know the basics and I'm afraid I can't find anything useful or concise using Google.

Thanks in advance!

$\endgroup$
3
$\begingroup$

$2^n$ is the number of vectors that can be chosen as the first element of the ordered pair.

Once the first element is chosen, there are $\binom nk$ ways to choose $k$ of the bit positions to flip from 0 to 1 or vice versa to procude the second element of the pair.


The distance between $(0,0,1,0)$ and $(1,0,1,1)$ is $2$ because the two vectors differ at $2$ positions, namely the first and the last:

(0,0,1,0)
(1,0,1,1)
 ^-----^--- 2 columns where the two vectors differ

This distance measure is known as the Hamming distance.

$\endgroup$
  • $\begingroup$ in computer terms, do an exclusive or (XOR) of each component and sum the results. $\endgroup$ – WW1 Apr 30 '15 at 2:53
  • 1
    $\begingroup$ @Henning: Thanks for the reply, sorry I didn't reply sooner, I was very busy. Could you please explain to me what's an ordered pair in this case? isn't the ordered pair supposed to be Just One element from Each Vector? That still confuses me, sir. $\endgroup$ – jlstr Apr 30 '15 at 15:55
  • 1
    $\begingroup$ @Jose: No, in this case the ordered pair is a pair $(a,b)$ of vectors -- that is, $a$ is an entire vector and $b$ is another vector. One of the ordered pairs for distance $k=2$ is $\bigl((0,0,1,0),(1,0,1,1)\bigr)$. $\endgroup$ – hmakholm left over Monica Apr 30 '15 at 16:02
  • $\begingroup$ @HenningMakholm: Thank you once again, pardon my huge lack of knowledge and understanding for this topic; Could you please explain to me this statement again: "2^n is the number of vectors that can be chosen as the first element of the ordered pair." -If you are using the whole vector(s), what is the "First Element"? is the "First Element" one or the other? ie. whichever you decide? Thanks again. $\endgroup$ – jlstr Apr 30 '15 at 17:09
  • 1
    $\begingroup$ @JoseE: I mean the first element of the pair. In the pair $\bigl((0,0,1,0),(1,0,1,1)\bigr)$ the first element of the pair is the vector $(0,0,1,0)$. (And its first element is the number $0$). There are $2^n$ different vectors of length $n$, and each of these can be the first element of the pair. $\endgroup$ – hmakholm left over Monica Apr 30 '15 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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