TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 157

Aus VoWi
Wechseln zu: Navigation, Suche

Wieviele "Wörter" der Länge 28 aus den Buchstaben a, b gibt es, die genau 5-mal a enthalten und zwischen zwei a mindestens 3-mal den Buchstaben b?


5xa und min 3xb dazwischen = |a |bbb a| bbb a |bbb a |bbb a|

Nun kann man die verbleibenden 11 b an 6 Stellen (mit | gekennzeichnet) einfügen.

Es handelt sich an Kombination mit Wiederhohlung also

C=(6+11-1) über 5=

Lösung = 4368

Etwas eher nachvollziehbare Lösung von Neverlasting[Bearbeiten]

Anzahl der Wörter mit Länge 28, die genau 5 Mal a enthalten? Zwischen je zwei a befindet sich mindestens 3 Mal b

So sehen diese Wörter aus: X a bbb X a bbb X a bbb X a bbb X a X

Mit X markiert sind jene 6 Stellen, an denen b eingefügt werden kann

Anz. der b, die noch fehlen: 28 - 5 - 4*3 = 11

Sei M folgende Menge:

M = { b1, b2, ..., b6 }

Wenn bx ausgewählt wird, bedeutet das, dass ein b an die Stelle x gesetzt wird.

Nun wählen wir genau 11 Elemente aus M aus, da genau 11 b an beliebige Stellen vergeben werden. Wiederholungen sind natürlich möglich. Beispielsweise haben wir folgende Auswahl: b1, b1, b1, b1, b3, b3, b4, b6, b6, b6, b6. Das ergibt 4 b an Stelle 1, 2 b an Stelle 3, 1 b an Stelle 4 und 4 b an Stelle 6. Also das Wort:

bbbb a bbb a bbb bb a bbb b a bbb a bbbb

Die Anzahl der möglichen 11-elementigen Auswahlen ist also die Lösung der Aufgabe. Es handelt sich um eine Kombination mit Wiederholung. (Man sehe sich dazu im Buch (In meiner Auflage auf Seite 50f) das Beispiel mit den Trennkugeln an)

Anzahl Wörter = (n+k-1 über k) = (6+11-1 über 11) = (16 über 11) = 4368

(n über k) ist übrigens äquivalent zu (n über n-k). Ich schätze so kam der Autor der vorhergehenden Lösung auf (16 über 5)

--Neverlasting 18:22, 5. Dez 2007 (CET)

anderer Lösungsvorschlag von m4rS[Bearbeiten]

Wir nehmen an, dass jedes a, dass wir einfügen, aus abbb besteht, sodass wir es beliebig einfügen können. Das heißt wir müssten von der Gesamtanzahl 28 - (5*3) abziehen, da bei jedem a 3 b dabei sind. Doch eigentlich dürfen wir nur 28-(4*3) rechnen, da das letzte a beliebig plaziert werden kann. Also haben wir 28-(4*3) Möglichkeiten, die 5 a einzufügen, d. h. (16 über 5)=4368