Show that the number of codewords of weight 3 in the Hamming code, Ham(r,2), where r is the redundancy and 2 indicates a binary code, is
$$\frac{(2^r-1)(2^{r-1}-1)} {3}$$
So, I know Ham(r,2) contains codewords of length $n= 2^r-1$ and that $2^{r-1}-1$ of them are nonzero.
Moreover, I know that every unique codeword of weight three in Ham(r,2) can be defined by a unique set of three linearly dependent columns of the corresponding parity-check matrix for Ham(r,2).
So… My idea was to simply set up a counting argument; say, given that every codeword of weight 3 is defined by a set of three linearly dependent columns of the parity-check matrix and there are $n = 2^r-1$ of them, then there are $n \choose 3$ possible codewords of weight 3.
Problem is the algebra just isn't getting me from $${n \choose 3 } =\frac{(2^r-1)!} {3!(2^r-4)!}$$ to $$\frac{(2^r-1)(2^{r-1}-1)} {3}$$ I'm I just messing up on the algebra or I'm i just going at it the wrong way…
Best Answer
That would be true if any combination of 3 colums of H were linearly dependent, which would imply that any $n-$ tuple of weight $3$ is a codeword (obviuosly false).
We know that $H$ has $n$ different (nonzero) $r-$tuples. We are interested in picking three of them $h_1$, $h_2$, $h_3$ such that $h_1+h_2+h_3=0$ (LD set). Imagine we pick the first two $h_1$, $h_2$ arbitrarily; now, see that there's one and only one $h_3$ that make the set LD. We have $n \choose 2$ ways of choosing the first pair, and $h_3$ is determined. But wait, we must divide by 3 to avoid counting as different the cases where $h_3$ is in the three possible positions. So the total number is
$$ \frac{n \choose 2}{3} =\frac{n (n-1)}{6}=\frac{(2^n-1)(2^n-2)}{6}=\frac{(2^n-1)(2^{n-1}-1)}{3}$$