4. Wie viel Kombinationen sind möglich?

Wie viel Kombinationen sind möglich?

  • V

    Hi Leute!

    Ich hab folgende Aufgabe gegeben:

    L_{5,c} = \{ x | x \in L_2 \text{und x enthält genau c Einsen} \}

    wobei L2={0,1}nL_2=\{0,1\}^n

    Die Frage der Aufgabe lautet nun: Bestimmen sie Die Anzahl der Wörter der folgenden Sprachen!

    Ich hab jetzt zu obiger(n) Sprache(n) mal ein Beispiel mit c=1 konstruiert:

    L_{5,1} = \{ x | x \in \{0,1\}^n \text{und x enthält genau 1 Eins} \}

    Aus diesem Beispiel folgen dann meiner Meinung nach folgende Wörter:

    {0,1}1={0,1}\{0,1\}^1 = \{0,1\}; {0,1}2={00,11,01,10}\{0,1\}^2 = \{00,11,01,10\}; {0,1}3={000,001,010,011,100,101,110,111}\{0,1\}^3 = \{000,001, 010, 011, 100, 101, 110, 111\}

    Bis hierhin gibt's ja eigentlich bis jetzt nur diese sechs Wörter die die Sprache L5,1L_{5,1} erfüllen, nämlich: {1,01,10,001,010,100}\{1, 01, 10, 001, 010, 100\}

    Nun meine Frage: Wenn das bis hier hin richtig ist, wie gebe ich dann allgemein an, wie viele Wörter sich aus der L5,cL_{5,c} konstruieren lassen, die die Einschränkung erfüllen?

    Ich hoffe das ihr mir da weiterhelfen könnt!

    0
  • I

    Was ist n? Und hat es etwas zu bedeuten, dass die Sprachen ausgerechnet L_5 und L_2 heißen?
    Ansonsten: die Anzahl der Möglichkeiten, dass ein Binärwort der Länge n genau c Einsen hat, entspricht der Anzahl der Möglichkeiten, aus einer n-elementigen Menge c Elemente auszuwählen.

    0
  • ?

    Mir kommt es auch so vor, als wären hier irgendwie die 5, 2 und n durcheinander gewürfelt worden.

    0
  • V

    Und hat es etwas zu bedeuten, dass die Sprachen ausgerechnet L_5 und L_2 heißen?

    Dass die Sprachen L_2 und L_5 heißen kommt nur daher weil ich vor der Teilaufgabe 5, die die Sprache L_5 ist, eine Sprache L_2 aus einer Sprache L_1 berechnen musste. Diese gesamte Aufgabe umfasst quasi 5 Teilsprachen und jede Sprache baut auf einer vorhergehenden Sprache auf, allerdings bis auf Sprache L_1; die war gegeben (muss ja so sein).

    Deswegen passt das bei L_5 schon so, dass da die Sprache L_2 verwendet wird.

    Was ist n?

    n ist die ganze Aufgabe über schon frei wählbar gewesen. Auch bei den anderen Sprachen!

    Ansonsten: die Anzahl der Möglichkeiten, dass ein Binärwort der Länge n genau c Einsen hat, entspricht der Anzahl der Möglichkeiten, aus einer n-elementigen Menge c Elemente auszuwählen.

    Heißt das also, dass ich die Sprache L5,c=(nc)L_{5,c} = \binom{n}{c} (Binomialkoeffizient) ausdrücken kann und ich so in Abhängigkeit von n und c die Anzahl gültiger Wörter der Sprache L5,cL_{5,c} berechnen kann?

    0
  • 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}\}

    Ich nehme einmal 0≤c≤n0 \leq c \leq 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}

    0
Anmelden zum Antworten