Contar los elementos de una esfera de Hamming mediante la combinatoria

Question

Tenemos la siguiente esfera de Hamming

$$\mathcal B_3= ((0,0,0,0),(\mathbb F_7)^4)$$

con $\mathbb F_7=\{0,1,2,3,4,5,6\}$

Así que queremos conocer todos los elementos posibles con distancia Hamming $\le3$ a $(0,0,0,0)$

$$\{u\in\mathbb F^4_7:dist((0,0,0,0),u)\le3\}$$

Es obvio que tenemos que utilizar la combinatoria para resolver este problema.

En primer lugar, observamos que tres elementos de u tienen que ser $\neq 0$

$$u=(v1,v2,v3,0) \ v_i \neq 0 $$

para obtener la distancia Hamming de $3$ .

El siguiente paso sería contar todas las combinaciones posibles para elegir $3$ posiciones de un vector con longitud $4$ .

$$ \frac {4!}{(4-1)!\cdot1!}=24$$

Sabemos que $v_1,v_2,v_3\in\{1,2,3,4,5,6\}$

Así que para cada $v_i$ tenemos $6$ posibles combinaciones. ¿Cómo puedo combinar esto con el $24$ ¿desde arriba?

Answer 1

Una pista: la pregunta se refería a las palabras a distancia de Hamming $\le 3$ pero parece que te has concentrado en los que están a distancia exactamente $3$ . Pero la distancia máxima en este espacio es $4$ . Así que puedes simplemente

• Observe que hay $6^4=1296$ palabras a la distancia exacta de cuatro de $(0,0,0,0)$ .
• Entonces observe que el número total de palabras en este espacio es $7^4=2401$ .
• Eso deja $2401-1296=1105$ vectores que están a distancia $\le3$ .

Answer 2

Si lo que dices es cierto sobre la distancia de martilleo, entonces es $4*6^3$ No son 24 sino 4