Explicación de la fórmula de la distancia de los vectores binarios

Question

Así que, aquí está una vez más esto artículo de topcoder sobre combinatoria. Después de que el artículo describe con éxito lo que la teoría que va a utilizar: Combinaciones/Permutaciones , va a una aplicación para ello, es decir. Vectores binarios . Hay una serie de propiedades para ellos que no entiendo muy bien, especialmente esta (#3)

3. El número de pares ordenados (a, b) de vectores binarios, tal que la distancia entre ellos (k) se puede calcular como sigue:

¿De dónde viene esta fórmula?

Además, hay un ejemplo sobre la declaración de la fórmula anterior:

La distancia entre a y b es el número de componentes que difiere en a y b - por ejemplo, la distancia entre (0, 0, 1, 0) y (1, 0 1, 1) es 2).

¿Podría alguien explicarme, por favor, cómo vector(es) binario(s) distancia ¿se hace? Necesito saber lo básico y me temo que no encuentro nada útil o conciso usando Google.

Gracias de antemano.

Answer 1

$2^n$ es el número de vectores que se pueden elegir como primer elemento del par ordenado.

Una vez elegido el primer elemento, hay $\binom nk$ formas de elegir $k$ de las posiciones de los bits para pasar de 0 a 1 o viceversa para procurar el segundo elemento del par.

---

La distancia entre $(0,0,1,0)$ y $(1,0,1,1)$ es $2$ porque los dos vectores difieren en $2$ posiciones, a saber, la primera y la última:

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

Esta medida de distancia se conoce como Distancia Hamming .