Beweisen Sie für den Ball B_{r}(u) mit Radius r und Mittelpunkt u folgende Gleichung?

Question

Gegeben seien eine endliche Menge \( K \) mit \( |K|=q \in \mathbb{N}, n \in \mathbb{N}, u \in K^{n} \) und \( r \in \mathbb{N}_{0} \). Beweisen Sie für den Ball \( B_{r}(u) \) mit Radius \( r \) und Mittelpunkt \( u \) folgende Gleichung:
\( \left|B_{r}(u)\right|=\sum \limits_{j=0}^{r}\left(\begin{array}{l} n \\ j \end{array}\right)(q-1)^{j} . \)

Comments

Was soll man unter dem Betrag eines Balls verstehen?

---

Der Begriff "Ball" bezieht sich hier auf eine Menge von Elementen in einem n-dimensionalen Raum, wobei die "Kugel" um einen Punkt  u  mit Radius  r  die Menge aller Punkte v  ist, deren Hamming-Distanz zu u  höchstens  r  beträgt.

Vielleicht hilft das weiter?

---

Der Betrag in diesem Zusammenhang bedeutet die Anzahl der Elemente der Menge

Answer 1

Die Kugel enthält alle Element \(x \in K^n\) mit Abstand

$$d(u,x)=|\{i=1, \ldots,n\mid u_i \neq x_i\}| \leq r$$

Den Abstand 0 hat nur u selbst und wird in der Summe für j=0 gezählt.

Des weiteren ist \(d(u,x)=j\) genau dann, wenn sich u und x in j Positionen unterscheiden. Man kann \(\binom{n}{j}\) Positionen dafür auswählen und hat auf jeder dieser Positionen q-1 "falsche" Elemente aus K zur Verfügung.

Daher diese Summe.