Explanation of Distance of binary vectors formula

Question

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)

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

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!

Answer 1

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