Kombinatorik-Aufgabe

19.01.2010, 20:22

Mäuschen1985

Kombinatorik-Aufgabe

Hallo!

Ich habe folgende Aufgabe bearbeitet:

Wie viele 6-stellige Zahlen gibt es, in denen jede der Ziffern 0,1,2 mindestens einmal vorkommt?

Ich habe mir dazu folgendes überlegt:

An Stelle 1 kann jede Zahl stehen ausser der 0 --> 9 Möglichkeiten!
An Stelle 2 kann jede Zahl stehen ausser die an Stelle 1 --> 9 Möglichkeiten!
An Stelle 3 kann jede zahl stehen ausser die an Stelle 1 und 2 --> 8 Möglichkeiten!
An Stelle 4 muss jetzt eine der 3 geforderten stehen--> also 3 Möglichkeiten!
Stelle 5 --> 2 Möglichkeiten!
Stelle 6 --> 1 Möglichkeit!

Insgesamt komme ich so auf

1*2*3*8*9*9 =3888 Möglichkeiten

Wäre das so richtig? Oder muss man an diese Aufgabe anders herangehen...

lg

mäuschen

20.01.2010, 13:06

Zellerli

Auf diesen Beitrag antworten »

Wenn du so an die Aufgabe herangehst, musst du (kannst ja mal ein Baumdiagramm anskizzieren) auch Fallunterscheidungen treffen:

Was wenn an den ersten drei Stellen die geforderten Ziffern alle gefallen sind?
Usw.

Wie wäre es über das Gegenereignis? Aus welchen Teilereignissen besteht es?

Puh irgendwie kommt man nicht um das Sieben herum...

20.01.2010, 13:56

Mäuschen1985

Auf diesen Beitrag antworten »

Hallo Zellerli!

Wenn an den ersten 3 stellen die geforderten ziffern schon gefallen sind wäre das ja nicht schlimm es geht ja darum das jede ziffer mindestens einmal vorkommen soll. So wären sie dann 2 mal vorgekommen...oder hab ich das jetzt falsch verstanden...

20.01.2010, 19:44

Lord Pünktchen

Auf diesen Beitrag antworten »

RE: Kombinatorik-Aufgabe
Also mir fallen dazu 2 Ansätze ein.
Sei (a0, a1, ..., a5) eine sechstellige Zahl mit Ziffern ai.

1) Man verteilt zuerst die 0, die 1 und dann die 2 auf die möglichen Positionen.

Also gibt es 5*4*3 Möglichkeiten die 0, die 1 und die 2 zu verteilen ohne a0 zu belegen.

Ebenso gibt es (5*1*4 + 5*4*1) Möglichkeiten, die 0, die 1 und die 2 zu verteilen und dabei a0 zu belegen.
(Für die 0 gibt es 5 möglichkeiten, da eine Zahl nicht mit 0 begint.)

Also ist die Anzahl aller Kombinationen:

5*4*3*(Anzahl der dreistelligen Zahlen) + 40*10^3

2) Man verwendet die Gleichverteilung und die Einschluss-Ausschluss-formel.
Da man die Gleichverteilung benutzt kann man von der errechneten Wahrscheinlichkeit auf die Anzahl der Kombinationen schließen.

Edith meint: Ansatz 1) ist wie ich eingesehen habe ziemlich unsinnig.

21.01.2010, 12:53

Zellerli

Auf diesen Beitrag antworten »

Anders als Lord Pünktchen in seinem ersten Ansatz habe ich verstanden, dass da "mindestens" steht.

Aber du kannst ja nicht sagen, dass die Ziffern gleich an den ersten Stellen auftreten müssen, nur weil du ihnen die Möglichkeit gibst.

Wirst wohl Sieben müssen (Inklusion-Exklusion) oder wie Lord Pünktchen es genannt hat "Einschluss-Ausschluss-Formel".

Ich würde da mit dem/n Gegenereignis(sen) anfangen, da kommt man dann Stück für Stück drauf.

21.01.2010, 13:16

Mäuschen1985

Auf diesen Beitrag antworten »

oaky vielen dank dann werd ich das mal mit Inkl. Exkl. probieren...

21.01.2010, 14:14

Auf diesen Beitrag antworten »

Zitat:

Original von Lord Pünktchen
2) Man verwendet die Gleichverteilung und die Einschluss-Ausschluss-formel.
Da man die Gleichverteilung benutzt kann man von der errechneten Wahrscheinlichkeit auf die Anzahl der Kombinationen schließen.

Dazu ist anzumerken, dass es die Siebformel auch für Mengenmächtigkeiten gibt - man kann sich also den künstlichen Umweg über die Gleichverteilung getrost sparen. Augenzwinkern

21.01.2010, 14:52

Siguras

Auf diesen Beitrag antworten »

Also wenn ich mir die Aufgabe so ansehe würde ich einfach 6nPr3 mal 6nPr3 in den Taschenrechner eingeben, das Ergebnis schein mir auch sinnvoll.
Es gibt 6nPr3 Möglichkeiten diese 3 Zahlen anzuordnen und für den Rest dann auch wieder 6nPr3 Möglichkeiten, oder bin ich da total falsch?
Was nPr genau bedeutet weiß ich jetzt nicht, ich habs mir so gemerkt, dass 49nCr6 die Wahrscheinlichkeit für 6 Richtige im Lotto ist und 49nPr6 die Wahrscheinlichkeit unter berücksichtigung der Reihenfolge, die ja hier wichtig ist.

21.01.2010, 17:35

Auf diesen Beitrag antworten »

Ja, total falsch.

Wie oben schon mehrfach gesagt führt hier kaum ein Weg an der Siebformel vorbei. Passende Mengen dazu wären

$\begin{eqnarray*} \Omega \end{eqnarray*}$ ... Menge aller 6-stelligen Zahlen
$\begin{eqnarray*} A_k \end{eqnarray*}$ ... Menge aller 6-stelligen Zahlen, die nicht die Ziffer $\begin{eqnarray*} k \end{eqnarray*}$ enthalten

Zu bestimmen ist dann die Anzahl

$\begin{eqnarray*} |\Omega\setminus (A_0 \cup A_1 \cup A_2)| = |\Omega| - |A_0 \cup A_1 \cup A_2| \end{eqnarray*}$ ,

was mit der Siebformel gut in den Griff zu kriegen ist, da man die Durchschnitte der $\begin{eqnarray*} A_k \end{eqnarray*}$ gut abzählen kann, im Gegensatz zu deren Vereinigungen.

16.02.2010, 12:38

Hel20

Auf diesen Beitrag antworten »

Hi,

ich weiß, ist schon etwas älter, ich versuch nur im zuge von Klausurvorbereitungen Kombinatorikaufgaben zu üben und versteh eure Lösung nicht... wieso geht das hier nicht, wie schon vorgeschlagen, über das Gegenereignis? es gibt 9*10^5 möglichkeiten, irgendwelche 6stelligen zahlen (ohne führende 0) zu bilden. davon dann einfach die anzahl möglicher zahlen ohne 0,1,2 drin abziehen, das müssten wohl 6^7 sein, also insgesamt 9*10^5 - 6^7?

danke schonmal smile

24.02.2011, 11:38

G-SUS

Auf diesen Beitrag antworten »

Wenn dann müssten das doch 7^6 Möglichkeiten sein? Aber das passt leider auch nicht.

Ich habe eine Excel-Tabelle gebastelt, die alle 6-stelligen Zahlen erhält und diese auf das Kriterium prüft. Dies ergibt dann 59790 Möglichkeiten. 100% Garantie dafür möchte ich nicht übernehmen, aber es sieht schon richtig aus.

Weitere Werte sind:
5 Stellen: 3376
4 Stellen: 150
3 Stellen: 4

Auf eine Lösung per Inklusion/Exklusion bin ich bisher leider nicht gekommen.

24.02.2011, 14:13

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von G-SUS
Ich habe eine Excel-Tabelle gebastelt, die alle 6-stelligen Zahlen erhält und diese auf das Kriterium prüft. Dies ergibt dann 59790 Möglichkeiten.

Das ist richtig.

Zitat:

Auf eine Lösung per Inklusion/Exklusion bin ich bisher leider nicht gekommen.

Wo hakt es da bei dir? Das ist doch in diesem Fall ziemlich einfach.

24.02.2011, 14:51

G-SUS

Auf diesen Beitrag antworten »

Beim Bilden der Schnittmenge hänge ich fest.

Ich habe jeweils für die Ziffern 0, 1 und 2 berechnet wie viele Möglichkeiten es gibt, dass diese Ziffern in einer 6-stelligen Zahl mindestens einmal vorkommen.

Für die Null sollten das 368559 Möglichkeiten ( $\begin{eqnarray*} |A_{0}| \end{eqnarray*}$ ) sein und jeweils für die Eins und Zwei 468559 Möglichkeiten ( $\begin{eqnarray*} |A_{1}| \end{eqnarray*}$ und $\begin{eqnarray*} |A_{2}| \end{eqnarray*}$ ).

Dann sollten sich die Gesamtmöglichkeiten so berechnen lassen:
$\begin{eqnarray*} n_{0}= \left(| A_{0} | + | A_{1} | + | A_{2} |\right) - \left(| A_{0}\cap A_{1} |+| A_{0}\cap A_{2} |+| A_{1} \cap A_{2}| \right) + | A_{0}\cap A_{1}\cap A_{2} | \end{eqnarray*}$

Bei der Berechnung der Mächtigkeit der Schnittmengen komme ich nun nicht weiter.

24.02.2011, 17:08

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von G-SUS
Ich habe jeweils für die Ziffern 0, 1 und 2 berechnet wie viele Möglichkeiten es gibt, dass diese Ziffern in einer 6-stelligen Zahl mindestens einmal vorkommen.

Für die Null sollten das 368559 Möglichkeiten ( $\begin{eqnarray*} |A_{0}| \end{eqnarray*}$ ) sein und jeweils für die Eins und Zwei 468559 Möglichkeiten ( $\begin{eqnarray*} |A_{1}| \end{eqnarray*}$ und $\begin{eqnarray*} |A_{2}| \end{eqnarray*}$ ).

So sind die Mengen aber nicht definiert. $\begin{eqnarray*} A_k \end{eqnarray*}$ ist die Menge der 6-stelligen Zahlen, in denen die Ziffer k nicht vorkommt. Die sind viel leichter zu bestimmen, z. B.

$\begin{eqnarray*} |A_0|=9^6=531441 \end{eqnarray*}$

$\begin{eqnarray*} |A_1|=8\cdot9^5=472392 \end{eqnarray*}$

Zitat:

Bei der Berechnung der Mächtigkeit der Schnittmengen komme ich nun nicht weiter.

Bei Benutzung der richtigen Mengendefinition sind auch die Schnittmengen leicht bestimmbar.

24.02.2011, 19:14

G-SUS

Auf diesen Beitrag antworten »

Danke für den Tipp, der hat mir den richtigen Weg gezeigt. Freude

Wie du schon geschrieben hast, ist $\begin{eqnarray*} A_{k} \end{eqnarray*}$ die Menge der Zahlen in denen die Ziffer k nicht vorkommt. Bei den Schnittmengen sind es dann zwei bzw. drei der Ziffern, die nicht vorkommen dürfen. Also:
$\begin{eqnarray*} |S|=900000 \end{eqnarray*}$ (Anzahl 6-stelliger Zahlen)
$\begin{eqnarray*} |A_{0}|=9^{6} \end{eqnarray*}$ (keine Null)
$\begin{eqnarray*} |A_{1}|=|A_{2}|=8\cdot 9^{5} \end{eqnarray*}$ (keine Eins bzw. Zwei)

$\begin{eqnarray*} | A_{0}\cap A_{1}|=A_{0}\cap A_{2} |=8^{6} \end{eqnarray*}$ (keine Null und Eins)
$\begin{eqnarray*} | A_{1} \cap A_{2}|=7\cdot 8^{5} \end{eqnarray*}$ (keine Eins und Zwei, sowie keine Null an 1. Stelle)
$\begin{eqnarray*} | A_{0}\cap A_{1}\cap A_{2} |=7^{6} \end{eqnarray*}$ (keine Null, Eins und Zwei)

Dann die Siebformel:
$\begin{eqnarray*} n_{0}= |S|-\left(| A_{0} | + | A_{1} | + | A_{2} |\right) + \left(| A_{0}\cap A_{1} |+| A_{0}\cap A_{2} |+| A_{1} \cap A_{2}| \right) - | A_{0}\cap A_{1}\cap A_{2} | \end{eqnarray*}$

und man hat das Ergebnis: $\begin{eqnarray*} n_{0}=59790 \end{eqnarray*}$

Neue Frage »

Antworten »

Kombinatorik-Aufgabe

Verwandte Themen