I
Sei also L={x∈{0,1}n∣x enthaelt genau c Einsen}L = \{ x \in \{0,1\}^n | x \text{ enthaelt genau } c \text{ Einsen}\}L={x∈{0,1}n∣x enthaelt genau c Einsen}
Ich nehme einmal 0≤c≤n0 \leq c \leq n0≤c≤n an.
Wenn wir einen n-Bit String s betrachten, so musst du die c Plaetze waehlen, an denen s eine 1 hat. Die Reihenfolge der Wahl dieser Plaetzte spielt natuerlich keine Rolle. Hast du diese Plaetze gewaehlt, so ist s vollstaendig bestimmt, da s genau c Einsen hat und somit alle uebrigen Plaetze auf 0 gesetzt werden muessen.
Folglich gilt ∣L∣=(nc)|L| = {n \choose c}∣L∣=(cn)