Kombination verschieden Aufgaben

24.10.2011, 00:38

GiggiLag

k-Permutation/Tupel/Multimenge/Kombination verschieden Aufgaben

Hallo,

ich hab Fragen zu verschieden Aufgaben im Themenbereich Kombinatorik. Die Aufgaben sind nach aufsteigender Schwierigkeit sortiert.

1) Bei einem Tanz-Wettbewerb sollen 12 verschiedene Tänzer jeweils vortanzen. Wieviel verschiedene Auftritts-Möglichkeiten gibt es, wenn der der erste und letzte Tänzer bereits festgesetzt sind.
Meine Lösung:
"Ziehen ohne Zurücklegen unter Beachtugn der Reihenfolge" $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ k-Permutation: $\begin{eqnarray*} \frac{n!}{(n-k)!} \end{eqnarray*}$ für n=10, k=10, da 2 Tänzer (Anfang und Ende) fix sind ergibt sich für mich:
$\begin{eqnarray*} \frac{10!}{(10-10)!} = 3628800 \end{eqnarray*}$
Das kommt mir zu leicht vor. Ist das korrekt?

2) Wieviel 8-stellige Dezimalzahlen gibt es, in denen jede Ziffer höchstens einmal vorkommt?
Meine Lösung:
Sei A die Menge der Ziffern mit $\begin{eqnarray*} A = \{0,1,2,3,4,5,6,7,8,9\} \end{eqnarray*}$
"Ziehen ohne Zurücklegen unter Beachtung der Reihenfolge" $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ k-Permutation.

Ansatz 1: Jede gültige Zahl ist in Ziffern aufgebaut als: $\begin{eqnarray*} z_{0}z_{1}z_{2}z_{3}z_{4}z_{5}z_{6}z_{7} \end{eqnarray*}$ mit $\begin{eqnarray*} z_{0}\in A\setminus \{0\} \end{eqnarray*}$ und $\begin{eqnarray*} z_{n\in\mathbb N} \end{eqnarray*}$ sind paarweise Verschieden. Dies folgt, da jede gültige Zahl nicht mit Null anfangen soll und keine Ziffer doppelt vorkommen darf. Somit gilt für die Anzahl der Möglichkeiten:
$\begin{eqnarray*} |A\setminus\{0\}|\cdot|A\setminus\{z_{0}\}|\cdot|A\setminus\{z_{0},z_{1}\}|\cdot|A\setminus\{z_{0},z_{1},z_{2}\}|\cdot|A\setminus\{z_{0},z_{1},z_{2},z_{3}\}|\cdot|A\setminus\{z_{0},z_{1},z_{2},z_{3},z_{4}\}|\cdot|A\setminus\{z_{0},z_{1},z_{2},z_{3},z_{4},z_{5}\}|\cdot|A\setminus\{z_{0},z_{1},z_{2},z_{3},z_{4},z_{5},z_{6}\}| \end{eqnarray*}$
$\begin{eqnarray*} = 9\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3 = 1632960 \end{eqnarray*}$

Ansatz 2: Für alle Permutation gilt: $\begin{eqnarray*} \begin{pmatrix} 10 \\ 8 \end{pmatrix} \end{eqnarray*}$ . Von diesen Permutation müssen diejenigen herausgenommen werden, welche vorne eine Null stehen haben. Dies sind ein Zehntel aller Permutationen. Somit gilt:
$\begin{eqnarray*} \begin{pmatrix} 10 \\ 8 \end{pmatrix} \cdot 0,9 = 1632960 \end{eqnarray*}$

Beide Ansätze bringen mich auf das selbe Ergebnis. Sind beide aus eurer Sicht legitim?

3) Wieviele mögliche Ergebnisse gibt es bei einem gleichzeitigen Wurf von 5 Würfeln?
Meine Lösung:
"Ziehen mit Zurücklegen ohne Beachtung der Reihenfolge" $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ k-Multimenge. $\begin{eqnarray*} k = \end{eqnarray*}$ Anzahl der Würfel, $\begin{eqnarray*} n = \end{eqnarray*}$ Anzahl der Möglichkeiten

Für die Multimenge gilt: $\begin{eqnarray*} \begin{pmatrix} n+k-1 \\ k \end{pmatrix} = \frac{(n+k-1)!}{(n-1)!\cdot k!} = \frac{(6+5-1)!}{(6-1)!\cdot 5!} = 9 \cdot 7 \cdot 4 = 252 \end{eqnarray*}$
Korrekt?

4) Wieviele mögliche Ergebnisse gibt es beim gleichzeitigen Wurf von 7 Würfeln, in denen eine 5 oder eine 3 vorkommt? (Mit 3 und 5 sind Augen gemeint)
Meine Lösung:
"Ziehen mit Zurücklegen ohne Beachtung der Reihenfolge" $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ k-Multimenge. $\begin{eqnarray*} k = \end{eqnarray*}$ Anzahl der Würfel, $\begin{eqnarray*} n = \end{eqnarray*}$ Anzahl der Möglichkeiten

Für die Multimenge gilt: $\begin{eqnarray*} \begin{pmatrix} n+k-1 \\ k \end{pmatrix} = \frac{(n+k-1)!}{(n-1)!\cdot k!} = \frac{(6+7-1)!}{(6-1)!\cdot 7!} = 792 \end{eqnarray*}$

Sofern Aufgabe 3) korrekt ist, ist der Schritt bis jetzt auch korrekt. Nun muss ich allerdings die Mengen entfernen, die als Auge eine 3 oder eine 5 enthalten. Dies sind 1/3 aller Mengen.
$\begin{eqnarray*} 792 * \frac{2}{3} = 528 \end{eqnarray*}$
Darf ich den letzten Schritt machen?

5) Wieviele Möglichkeiten gibt es, 50 Autos 5 Städte zuzuordnen, wenn die Städte gleichviele Autos Erhalten sollen?
"Ziehen ohne Zurücklegen ohne Beachtung der Reihenfolge" $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ k-Kombination.
Meine Lösung:
Für eine einzige Stadt gibt es: $\begin{eqnarray*} \begin{pmatrix} 50 \\ 10 \\ \end{pmatrix}= 10\,272\,278\,170 \end{eqnarray*}$ Kombinationen. In dem Fall sind 10 Autos verteilt, jedoch müssen noch 40 weitere Autos im 10er Pack auf 4 weitere Städte verteilt werden. Dies gilt für jede Kombination aus der ersten Rechnung. Es folgt für die Gesamtzahl aller Kombinationen mit:
$\begin{eqnarray*} \begin{pmatrix} 50 \\ 10 \\ \end{pmatrix} \cdot \begin{pmatrix} 40 \\ 10 \\ \end{pmatrix} \cdot\begin{pmatrix} 30 \\ 10 \\ \end{pmatrix} \cdot\begin{pmatrix} 20 \\ 10 \\ \end{pmatrix} \cdot\begin{pmatrix} 10 \\ 10 \\ \end{pmatrix} = 4,833\cdot 10^{31} \end{eqnarray*}$
Ist es korrekt, dass ich multipliziere an dieser Stelle? Freunde von mir sind der festen Überzeugung es muss addiert werden.

6) Bei einem Seminar sollen 7 Studierende jeweils zwei Vorträge halten. Wieviele Möglichkeiten gibt es für die Reihenfolge der Vortragenden?
Meine Lösung:
Das große Problem dieser Aufgabe ist, dass jeder Student zwei Vorträge hat. Daraus folgt, dass ein Student sowohl seine Vorträge hintereinander halten kann, als auch dass ein anderer Student dazwischen einen Vortrag hält. Dies sei an einem Beispiel von 2 Studenten dargestellt. Student A mit den Vorträgen 1 und 2, und Student B mit den Vorträgen 3 und 4:

Mögliche Permutation der Vorträge (Anzahl 4! = 24):
$\begin{eqnarray*} \begin{tabular}[t]{c|c} Vörtrags-Permutation & Studenten-Reihenfolge \\ \hline (1,2,3,4) & (A,B) \\ (1,2,4,3) & (A,B) \\ (1,3,2,4) & (A,B,A,B) \\ (1,3,4,2) & (A,B,A,B) \\ (1,4,2,3) & (A,B,A,B) \\ (1,4,3,2) & (A,B,A,B) \\ (2,1,3,4) & (A,B) \\ (2,1,4,3) & (A,B) \\ (2,3,1,4) & (A,B,A,B) \\ (2,3,4,1) & (A,B,A) \\ (2,4,1,3) & (A,B,A,B) \\ (2,4,3,1) & (A,B,A) \\ \dots&\dots \end{tabular} \end{eqnarray*}$

Führt man die Tabelle weiter fort sieht man, dass es die 6 Studenten-Reihenfolgen: (A,B), (B,A), (A,B,A), (B,A,B), (A,B,A,B), (B,A,B,A) gibt. Meine weiteren Überlegungen waren nun, wie ich aus weiteren Studenten folgen kann, wieviele mögliche Vortrags-Reihenfolgen es gibt. Für 3 Stundenten (A,B,C), mit je 2 Vorträgen, bin ich von einer Ausgangsreihenfolge (A,B,C) ausgegangen und auf folgende Idee gekommen:

Reihenfolge (A,B,C) lässt sich mit A erweitern (Student A hält seinen zweiten Vortrag) zu (A,B,C,A), dies ist ein Sohn (1.Generation) der Ausgangsreihenfolge. (A,B,A,C) ist der zweite Sohn der 1. Generation. Von der Reihenfolge (A,B,C) gibt es mit A erweitert KEINE weiteren Söhne erster Generation, da (A,A,B,C) = (A,B,C) - logischerweise. Diese beiden Söhne können mit A nicht mehr erweitert werden, da Student A bereits beide Vorträge gehalten hat. Die Söhne erster Generation können als nun mit B erweitert werden, woraus 4 Söhne zweiter Generation folgen. Die folgenden Söhne werden mit C erweitert, woraus die längsten Reihenfolgen aus (A,B,C) resultieren (8 Söhne dritter Generation).

Es ergibt sich somit ein Baum. Dieser Baum spiegelt alle Reihenfolgen wieder, welche aus der Ausgangsreihenfolge (A,B,C) durch hinzfügen von jeweils einem weiteren A,B,C (jeder Student hält einen zusätzlichen Vortrag, wobei der Student seine Vorträge nicht hintereinander halten soll, da diese Möglichkeit bereits der Vater des jeweiligen Sohnes widerspiegelt). Insgesamt folgt für die Anzahl der Möglichkeiten:
Ausgangsreihenfolge + 2 Söhne-1Gen + 4 Söhne-2Gen + 8 Söhne-3Gen = 1+2+4+8 = 15

Es gibt 6 Ausgangsreihenfolgen, woraus folgt: Alle Möglichen Studentenen-Reihenfolgen sind: $\begin{eqnarray*} 6 \cdot 15 = 90 \end{eqnarray*}$
Gibt es einen Denkfehler?

Abstraktion aus dem Beispiel:
Weiterführend habe ich versucht die Essenz aus dem Beispiel herauszufiltern und in einer Formel zusammenzufassen um diese auf mein Ausgangsproblem anweden zu können.

Sei $\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$ die Anzalh der Studenten. Jeder Student hat zwei Vorträge, woraus sich ergibt, dass die minmale Reihenfolge aus $\begin{eqnarray*} n \end{eqnarray*}$ Elementen besteht und die maximal Reihenfolge aus $\begin{eqnarray*} 2n \end{eqnarray*}$ .

Nun muss von den minimalen Reihenfolge ausgegangen werden, wobei jede minimale Reihenfolge die Wurzel eines oben beschriebenen Baumes bilden soll. Ergo gibt es n-Permutation $\begin{eqnarray*} (n!) \end{eqnarray*}$ Anzahl an Wurzeln. Diese minimale Reihenfolge wird erweitert um ein Element der Reihenfolge, um an die Söhne der nächsten Generation zu gelangen. Die Anzahl der Söhne die hierbei entstehen ist n-1, da der Sohn bei dem "zwei gleiche Elemente nebeneinaderstehen durch Erweiterung" bereits ein Vater ist. Insgesamt muss n-mal Erweitert werden um an die maximale Reihenfolge zu gelangen.

Zusammengefasst:
Alle Start-Reihenfolgen als n-Permutation der Anzahl der Studenten: $\begin{eqnarray*} n! \end{eqnarray*}$
gültige Söhne der nächsten Generation: $\begin{eqnarray*} n-1 \end{eqnarray*}$
Schritte (Stufen des Baumes): $\begin{eqnarray*} n \end{eqnarray*}$

Daraus folgt für die Anzahl aller möglichen Vortragsreihenfolgen (N) für die Anzahl (n) der Studenten:
$\begin{eqnarray*} N = n! \cdot (\sum\limits_{k=0}^n (n-1)^{k} ) \end{eqnarray*}$

Proberechnung:
n=1: $\begin{eqnarray*} 1! \cdot((1-1)^0 + (1-1)^1)= 1 \cdot (1+0) = 1 \end{eqnarray*}$ Korrekt - logisch.
n=2: $\begin{eqnarray*} 2! \cdot (1^0+ 1^1 + 1^2) = 2 \cdot 3 = 6 \end{eqnarray*}$ Korrekt - siehe oben.
n=3 $\begin{eqnarray*} 3! \cdot (2^0 + 2^1 + 2^2 + 2^3) = 6 \cdot 15 = 90 \end{eqnarray*}$
n=4: $\begin{eqnarray*} 4! \cdot (3^0 + 3^1 + 3^2 + 3^3 + 3^4) = 24 \cdot 121 = 10890 \end{eqnarray*}$
....
n=7: $\begin{eqnarray*} 7! \cdot (6^0+6^1+6^2+6^3+6^4+6^5+6^6+6^7) = 5040 \cdot 335923 = 1\,693\,051\,920 \end{eqnarray*}$

Vielen Dank für jede Hilfe vorweg!

Liebe Grüße,

25.10.2011, 16:12

Math1986

Auf diesen Beitrag antworten »

RE: k-Permutation/Tupel/Multimenge/Kombination verschieden Aufgaben
Oje.. in Zukunft bitte nur eine Frage pro Thema, man wird ja regelrecht erschlagen geschockt

1) Sieht soweit richtig aus.

2) Stimmt auch, führt ja auch beides zum selben Ergebnis.

3) Hier stellt sich schon die Frage, ob die Würfel unterscheidbar sind oder nicht, ich würde aber auch so wie du zu "nein" tendieren. Ich glaube, du hast die Ergebnisse von 3) und 4) vertauscht.

5) Ja, multiplizieren ist richtig.

6) Ich kann der Argumentation nicht ganz folgen, maber du kannst berstmal die Anzahl Möglichkeiten für 14 verschiedene Studenten berechnen, und dir dann überlegen, wie du diese Studenten untereinander anordnen kannst.
Wenn von den 14 Vorträgen 2 vom selben Studenten gehalten werden, dann sind es ja nur noch halb so viele Kombinationsmöglichkeiten...

25.10.2011, 16:22

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von GiggiLag
Beide Ansätze bringen mich auf das selbe Ergebnis. Sind beide aus eurer Sicht legitim?

Die Rechnung mag legitim sein, die Symbolik im zweiten Rechenweg ist es nicht: Unter $\begin{eqnarray*} \binom{10}{8} \end{eqnarray*}$ versteht man einen Binomialkoeffizienten mit dem Wert $\begin{eqnarray*} \frac{10!}{8!\cdot 2!} = 45 \end{eqnarray*}$ , das hast du hier aber bestimmt nicht gemeint, sondern wohl eher $\begin{eqnarray*} \frac{10!}{2!} \end{eqnarray*}$ unglücklich

Neue Frage »

Antworten »

k-Permutation/Tupel/Multimenge/Kombination verschieden Aufgaben

Verwandte Themen