Sphere packing condition for a perfect code

is a perfect -error correcting code, iff the Hamming balls for any two codewords and #m/thm/code

Proof

Given a codeword , the number of strings with Hamming distance is given by

since there are combinations of positions different from , and each differing position may be one of letters. Hence, for a code to be perfect, the closed balls of radius must partition , giving the expression above.

The latter part can be interpreted as

The first terms of a row in Pascal's triangle sum to a power of .

#state/tidy | #lang/en | #SemBr