Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Kombinatorik: Wörter der Länge 5

Kombinatorik: Wörter der Länge 5

Universität / Fachhochschule

Tags: Kombinatorik

stefan08 aktiv_icon

16:40 Uhr, 25.01.2014

Hallo,

ich habe folgende Aufgabenstellung:

M = {a, b, c, d, e, f},

Wörter der Länge 5
1)Wie viele mögliche Wörter.
2)Wie viele Wörter wo keine Buchstaben doppelt hintereinander vorkommen.
3)Wie viele Wörter wo nur ein Buchstabe wiederholt werden darf.
4)Wie viele Wörter wo ab und cd nicht vorkommen dürfen.
5)Wie viele Wörter wo zwischen jeden a und

b

mindestens 1Zeichen ist.

Ich habe:

1) 6^{5}

3)Variation ohne Wiederholung für

M = {a, b, c, d, e, f, x} \frac{7!}{(7 - 5)!} = 2520

6 Möglichkeiten für

x \Rightarrow 2520 \cdot 6

Möglichkeiten

Bei

2),4)

und

5)

komme ich aber nicht weiter.
Mein Ansatz für

4)

Möglichkeiten mit ab M=

{

ab,c,d,e,f}

5^{4},

mit cd:5^4, mit ab und cd:5^3
In den

5^{4}

wird aber aabcd oder ähnliches nicht mitgezählt.

Habt ihr eine Ahnung wie das geht?

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Gemischte Aufgaben der Kombinatorik
Kombinatorik: Ziehen mit Reihenfolge und mit Zurücklegen
Kombinatorik: Ziehen mit Reihenfolge und ohne Zurücklegen
Kombinatorik: Ziehen ohne Reihenfolge und ohne Zurücklegen

anonymous

00:14 Uhr, 26.01.2014

Hallo
zu

1)

ja, ich komme auch auf

6^{5} = 7776

Worte.

zu

3)

Du sagst

2520 \cdot 6 = 15120

Worte. Das wären mehr, als unter

1),

und dort kann man Worte ganz ohne Einschränkung bilden.
Also, die

2520 \cdot 6

kann demnach nicht stimmen.

zu

2)

Das ist nicht so schwer. Überleg dir:

>

Wie viele Möglichkeiten hast du für den ersten Buchstaben?

>

Wie viele Möglichkeiten hast du für den zweiten Buchstaben?
(Tip: Der zweite Buchstabe kann eigentlich jeder beliebige, ausser dem ersten sein.)

>

Wie viele Möglichkeiten hast du für den dritten, vierten, fünften Buchstaben?

anonymous

11:20 Uhr, 26.01.2014

3)

Es gibt zunächst zwei Möglichkeiten:

a)

KEIN Buchstabe wird wiederholt:
Das ist, wie du schon beschrieben hast, eine Variation von 5 Buchstaben aus der Auswahl an 6 Buchstaben. Also

n_{0} = \frac{6!}{(6 - 5)!} = 6! = 720

b)

EIN Buchstabe wird wiederholt:
Das heisst wir wählen aus der Auswahl an 6 Buchstaben zunächst mal 4 Buchstaben aus:

\frac{6!}{(6 - 4)!} = 360

Für den fünften Buchstaben soll sich eine Wiederholung einstellen. Dh. wir wählen aus den 4 Buchstaben einen aus.
Folglich sind das 4 Möglichkeiten.
Jetzt müssen wir uns noch Gedanken machen, welche Reihenfolge diese Buchstaben einnehmen können.
Ich stelle mir vor. Die ersten 4 Buchstaben stünden schon mal vorbereitet in einer Reihe. Jetzt kommt noch der 5. Buchstabe als Nachzügler und drängelt sich irgendwo ungeniert dazwischen. Dazu hat er 5 Möglichkeiten.

z . B

. wenn die ersten 4 Buchstaben lauteten:
abcd
dann sei zB. der Wiederholungsbuchstabe das

' b',

dieser Nachzügler setzt sich an die 1. bis 5. Stelle:
babcd
abbcd
abbcd
abcbd
abcdb
Wie man sieht, sind aber die Worte zwei und drei davon gleich.
Folglich müssen wir das Ganze noch durch 2 teilen.

Zusammenfassung für EINE Wiederholung:

n_{1} = 360 \cdot 4 \cdot (\frac{5}{2}) = 3600

c)

Zusammenfassung: höchstens eine Wiederholung:

n = n_{0} + n_{1} = 720 + 3600 = 4320

stefan08 aktiv_icon

13:11 Uhr, 26.01.2014

Danke für die ausführliche Antwort.

Stimmt

2)

wäre nicht so schwer, komme auf:

n \cdot {(n - 1)}^{4}

also

3750

3)b)Müsste man hier nicht statt den

\frac{5}{2}, 3

nehmen, es gibt ja schließlich nur 2 Kombinationen wo, das gleiche Wort rauskommt?

Hätte hier zu auch noch eine andere Überlegung und zwar kann man ja für 2Stellen ja alle 6Buchstaben verwenden und für die anderen dann nur

6 - 16 - 2

usw.

6 \cdot 6 \cdot 5 \cdot 4 \cdot 3

hier kommt aber deutlich weniger raus wo liegt hier mein Denkfehler?

5)Wörter ohne

a 5^{5}

Dann kann man noch die Permutationen der Mengen

{

a,b,x,x,x},{a,a,b,x,x},{a,a,a,b,x},{a,b,b,x,x},{a,b,b,b,x}
betrachten und die Permutation von

{

ab,x,x,x}{ab,a,x,x},{ab,a,a,x},{ab,b,b,x},{ab,b,x,x} wobei man hier mal 2 rechnen muss da statt ab auch ba möglich ist.
Außerdem gibt es noch die Kombinationen aaxbb und bbxaa die noch nicht vorkommen.
Für

x

gibt es 4Möglichkeiten. wenn man jetzt alles zusammenzählt also:
5^5+8(von bbxaa & aaxbb)+ 4(Permutation(

{

a,b,x,x,x})-2*Permutation({ab,x,x,x})....)
müsste das doch stimmen?

Bummerang

12:15 Uhr, 27.01.2014

Hallo,

die Lösung der Aufgabe

1)

scheint ja unstrittig

6^{5} = 7776

zu sein.

Auch bei der Aufgabe

2)

scheint es keine Probleme zu geben, deren Lösung

3750

sein sollte.

Aber bei der dritten Aufgabe bin ich anderer Meinung als cositan! Für die Lösung mit maximal einer einmaligen Wiederholung ergibt sich:

(\begin{matrix} 6 \\ 5 \end{matrix}) \cdot 1 \cdot 5! + (\begin{matrix} 6 \\ 4 \end{matrix}) \cdot 4 \cdot \frac{5!}{2! \cdot 1! \cdot 1! \cdot 1!} = 6 \cdot 1 \cdot 120 + 15 \cdot 4 \cdot 60 = 720 + 3600 = 4320

Dabei steht in jedem der Summanden der erste Faktor

(\begin{matrix} 6 \\ k \end{matrix})

für die Anzahl der Möglichkeiten, sich

k

verschiedene Buchstaben auszuwählen. Der zweite Faktor steht für die Anzahl der Möglichkeiten, sich einen der

k

verschiedenen Buchstaben für eine Wiederholung auszuwählen (wenn

k = 5

ist, dann kann ich keinen Buchstaben für eine Wiederholung auswählen, ich habe also genau eine Möglichkeit, nämlich die, keinen Buchstaben wählen zu können). Der letzte Faktor steht für die Möglichkeiten der Anordnung der 5 Buchstaben, die bei

k = 5

natürlich eine Permutation ohne Wiederholung ist, bei

k < 5

aber eine Permutation mit Wiederholung.

Jetzt fragt sich vielleicht der eine oder andere, warum sich dieser Depp hier die Arbeit gemacht hat, für

k = 5

und

k = 4

die selbe Anzahl wie cositan, nur auf einem anderen Weg zu ermitteln. Das liegt daran, dass ich die hier angegebene Aufgabenstellung nicht für eindeutig halte. Wenn sich ein Buchstabe wiederholen darf, so heisst das ja nicht unbedingt, dass er sich nur ein Mal wiederholen darf! Man sagt ja auch Kombination/Variation mit Wiederholung und meint: "mit beliebig vielen Wiederholungen", natürlich beschränkt durch

k,

dem Umfang der Auswahl. Ich würde deshalb bei der Lösung der Aufgabe zunächst darauf hinweisen, dass die Aufgabenstellung nicht eindeutig formuliert ist und es deshalb zwei mögliche Lösungen gibt. Falls die Aufgabenstellung lautete, dass es maximal einen Buchstaben mit beliebiger Anzahl an Wiederholungen geben darf, dann ist die Lösung

(\begin{matrix} 6 \\ 5 \end{matrix}) \cdot 1 \cdot 5! + (\begin{matrix} 6 \\ 4 \end{matrix}) \cdot 4 \cdot \frac{5!}{2! \cdot 1! \cdot 1! \cdot 1!} + (\begin{matrix} 6 \\ 3 \end{matrix}) \cdot 3 \cdot \frac{5!}{3! \cdot 1! \cdot 1!} + (\begin{matrix} 6 \\ 2 \end{matrix}) \cdot 2 \cdot \frac{5!}{4! \cdot 1!} + (\begin{matrix} 6 \\ 1 \end{matrix}) \cdot 1 \cdot \frac{5!}{5!}

= 6 \cdot 1 \cdot 120 + 15 \cdot 4 \cdot 60 + 20 \cdot 3 \cdot 20 + 15 \cdot 2 \cdot 5 + 6 \cdot 1 \cdot 1 = 720 + 3600 + 1200 + 150 + 6 = 5676

Diesen Fall könnte man auch berechnen, indem man aus den unter

1)

berechneten Möglichkeiten alle die rausschmeisst, bei denen sich 2 verschiedene Buchstaben wiederholen

(3

Buchstaben geht ja nicht, weil bei Wiederholung aller 3 Buchstaben ja ein Wort mit mindestens 6 Stellen entsteht). Für die 2 unterschiedlichen Buchstaben ergeben sich zwei Möglichkeiten: Einerseits können sie beide genau zwei Mal im Ergebnis auftreten und sie können ein Mal doppelt und ein Mal dreifach auftreten. Dafür ergeben sich die folgenden Möglichkeiten (nach dem selben Prinzip)

7776 - (\begin{matrix} 6 \\ 3 \end{matrix}) \cdot (\begin{matrix} 3 \\ 2 \end{matrix}) \cdot \frac{5!}{2! \cdot 2! \cdot 1!} - (\begin{matrix} 6 \\ 2 \end{matrix}) \cdot 2 \cdot \frac{5!}{3! \cdot 2!}

= 7776 - 20 \cdot 3 \cdot 30 - 15 \cdot 2 \cdot 10 = 7776 - 1800 - 300 = 7776 - 2100 = 5676

Zur Aufgabe

4)

kann man sich leicht vorstellen, dass die Anzahl der Möglichkeiten aus

1),

die ab enthalten, gleich der Anzahl der Möglichkeiten ist, dass cd enthalten ist. Als Plausibilitätsbeispiel sei genann, dass man ja alle

a' s

durch

c' s

und umgekehrt ersetzen kann und natürlich alle

b' s

durch

d' s

und umgekehrt. Oder noch allgemeiner: Jedes mögliche Paar von aa bis ff (also

36

Stück) kommt in den

7776

Möglichkeiten mit jeweils 4 Paaren (beginnend an erster bis vierter Stelle) gleich oft vor. Insgesamt erhält man

7776 \cdot 4 = 31104

Paare, wobei jedes der

36

Paare genau

864

Mal vorkommt. Jetzt darf man von den

7776

natürlich nicht die

864

zwei Mal abziehen, ein Mal für ab und ein Mal für cd, sondern man muss zunächst mal alle Möglichkeiten abziehen, die zwei Paare ab bzw. zwei Paare cd enthalten. Hat man zwei gleiche Paare ab oder cd, so kann der fünfte Buchstabe beliebig sein

(6

Möglichkeiten) und an den Stellen eins, drei und fünf im Ergebnis stehen

(3

Möglichkeiten). Also enthalten

6 \cdot 3 = 18

Möglichkeiten zwei Paare ab bzw. cd. Damit enthalten

864 - 18 = 846

Möglichkeiten mindestens ein ab und

846

Möglichkeiten mindestens ein cd. Würde man das aber einfach zusammenzählen, würde man alle Möglichkeiten, die sowohl das Paar ab als auch das Paar cd enthalten, doppelt zählen. Deshalb zählen wir die Möglichkeiten, die sowohl ab als auch cd enthalten. Das sind 6 Möglichkeiten für den fünften Buchstaben, der an 3 verschiedenen Stellen stehen kann und ab und cd können in beliebiger Reihenfolge (das ab kommt vor dem cd und umgekehrt') auftauchen. Das ergibt zusammen

6 \cdot 3 \cdot 2 = 36

Möglichkeiten. Mit anderen Worten:

Es gibt

846 + 846 - 36 = 1692 - 36 = 1656

Möglichkeiten, die ab oder cd enthalten. Die Anzahl der Möglichkeiten ohne ab und cd ist demzufolgt

7776 - 1656 = 6120

Die Aufgabe

5)

ist

m . E

. wieder sehr schwammig formuliert, da gibt es zu viele Möglichkeiten der Interpretation. Zunächst gehören

m . E

. auch alle Worte zur Ergebnismenge, die weder a noch

b

enhalten, denn auch diese haben zwischen jedem a und

b

ein anderes Zeichen. Das liegt an der Eigenschaft der Implikation, dass sie bei Nichterfüllung der Voraussetzung natürlich immer erfüllt ist. Genauso gehören

m . E

. Worte, die nur a und nur

b

enthalten dazu. Auch ist aus der Aufgabenstellung nicht unbedingt ersichtlich, ob nun a und

b

in dieser Reihenfolge im Ergebnis auftauchen müssen, damit ein anderer Buchstabe dazwischen kommen muss oder ob es auch für die Buchstaben

b

und a gilt. Ich bin gern bereit, meine Lösung zu den verschiedenen Möglichkeiten anzubieten, aber ohne Präzisierung mache ich hier

u . U

. mehr als die Hälfte nicht nur kostenlos sondern auch noch umsonst...

anonymous

12:49 Uhr, 27.01.2014

3)

Bummerang, ich muss dir recht geben.
Die Aufgabe ausführlich formuliert könnte heissen:

3 . a)

Wie viele Worte gibt es, in denen höchstens ein Buchstabe höchstens einmal wiederholt werden darf? (So habe ich es ursprünglich interpretiert)

3 . b)

Wie viele Worte gibt es, in denen höchstens ein Buchstabe beliebig oft wiederholt werden darf?
Vermutlich hast du, Bummerang, recht. So lange nur "wo nur ein Buchstabe wiederholt werden darf" da steht, ist wohl die Interpretation nach

3 . b)

angebrachter.

zu

4)

Wenn ich es mir recht überlege, ist auch diese Aufgabe nicht

100 %

eindeutig formuliert.
Die Aufgabe ausführlich formuliert könnte heissen:

4 . a)

Wie viele Worte gibt es, in denen weder die Teilfolge "ab" noch die Teilfolge "cd" vorkommen dürfen. (So hast du, Bummerang, die Aufgabe offensichtlich interpretiert.)

4 . b)

Wie viele Worte gibt es, in denen nicht sowohl die Teilfolge "ab" als auch die Teilfolge "cd" vorkommen dürfen.

Wahrscheinlich hat auch da Bummerang recht, und die Formulierung "wo ab und cd nicht vorkommen dürfen" zielt eher auf

4 . a)

ab.

Falls doch

4 . b)

gemeint sein sollte, so habe ich mir inzwischen überlegt: die Gegenereignisse sind überschaubar und abzählbar. Sie lauten:
abcdx
abxcd
xabcd
cdabx
cdxab
xcdab
...wobei

' x'

für einen beliebigen der 6 Buchstaben steht.

Bummerang

12:58 Uhr, 27.01.2014

Hallo cositan,

bei "ab und cd" habe ich auch einen Moment überlegt, ob ich das nach Deinem

4 b)

interpretieren soll, dieses aber verworfen, da diese Formulierung, so zweideutig wie sie ist, so gut wie nie im Sinne Deines

4 b)

gemeint ist. Ich weiss nicht wer diese Fragen gestellt hat (egal ob selbst erfunden oder von irgendwo übernommen) und ob sie wortwörtlich hier wiedergegeben wurden, aber wenn das hier wortwörtlich ist, dann sollte man der Fragestellerin/dem Fragesteller mal einen dezenten Hinweis geben, dass die Fragen bitte eindeutig gestellt werden. Am besten macht das mal eine(r) von den Besten des Studienjahres. Das als Empfehlung an stefan08.

PS: Dein Fall

4 b)

taucht als Berechnung bereits bei mir auf: "Deshalb zählen wir die Möglichkeiten, die sowohl ab als auch cd enthalten. Das sind 6 Möglichkeiten für den fünften Buchstaben, der an 3 verschiedenen Stellen stehen kann und ab und cd können in beliebiger Reihenfolge (das ab kommt vor dem cd und umgekehrt') auftauchen. Das ergibt zusammen

6 \cdot 3 \cdot 2 = 36

Möglichkeiten."

stefan08 aktiv_icon

21:54 Uhr, 27.01.2014

Erstmal danke für die gut verständlichen Erklärungen.

Zu den Fragen, die Fragen

1 - 4

kommen von einer Vorlesungsprüfung, wurden aber von einem Studenten weitergegeben, als dürfte die Mehrdeutigkeit davon kommen.
Die 5.Frage kommt von mir und war so gemeint, dass auch Wörter ohne a und

b

enthalten sind, falls es aber ein a und

b

gibt ist weder ab noch ba erlaubt.

Wobei

5)

eigentlich eins zu eins wie

4 a)

funktioniert

Wenn man aber Mindestabstand 2Zeichen annimmt müsste es doch folgendermaßen gehen:

Die Möglichkeiten mit nur 1Zeichen Abstand:
aXb und bXa mit

x

ist

c, d, e

oder

f,

also

2 \cdot 4

.
Permutation von

{

Y1,Y2,axb}=6 , für

y 1 & y 2

gibt es 6Möglichkeiten.
Permutation von

{

Y,Y,axb}=3 ,für

y

gibt es 6Möglichkeiten.(Die Möglichkeiten für

Y 2 = Y 1

die zu viel gezählt wurden)

2 \cdot 4 \cdot (6 \cdot 6 - (6 \cdot 3)) = 144

Davon Möglichkeiten mit ba oder ab: 'Axb'az, zb'axb', ab'axb','axb'ab, 'axb'ba, ba'axb'

\Rightarrow (2 \cdot 5 + 4) \cdot 4 = 56 ... . z

ist sine alle Buchstaben außer dem, durch den sich ab bzw. ba ergeben würde.
Das gleiche für bxa also

2 \cdot 56 = 112

144 - 112 = 32

Diese zieht man dann von den

6120

ab,

6120 - 32 = 6088

.

Bin mir aber ziemlich unsicher wegen der Anzahl wo

Y 1 = Y 2

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1141768

1141128

	Status: nicht eingeloggt	Noch nicht registriert?