Alle unterschiedlichen 3-stellige Zahlenkombinationen von {1, 1, 1, 2, 2, 3}

23.02.2014, 19:35

Brayn410

Alle unterschiedlichen 3-stellige Zahlenkombinationen von {1, 1, 1, 2, 2, 3}

Hallo ihr Lieben, smile

sry dass ich schon wieder schreibe, aber ich sitze wirklich schon paar Stunden an dieser Aufgabe. Zuerst mal, die Aufgabe habe ich im Internet gefunden als ich weitere Kombinatorikaufgaben suchte, daher gleich mal der Link:
http://webcache.googleusercontent.com/se...e&ct=clnk&gl=de
Es geht um die Aufgabe 4.
Falls das mit dem Link nicht funktioniert, hier nochmal eine kurze Zusammenfassung:
Gegeben sind die Zahlen {1, 1, 1, 2, 2, 3} (quasi Multimenge). Nun soll man nach Aufgabenstellung alle unterschiedlichen 3-stelligen Zahlenkombinationen aufschreiben. Um das aber mal "realistischer" zu machen, habe ich versucht mir eine Formel zu suchen, mit der man das auch berechnen kann. Die Lösung kann man in dem Link leicht Zählen, es sind 19 Kombinationen, aber wie berechnet man das?

Meine bisherigen Versuche:
1. Idee:
Man hat 6 Möglichkeiten für die erste Stelle, 5 für die zweite und 4 für die dritte Stelle. Nun hat man aber einige doppelt gezählt, da 1 1 1 mit dieser Vorgehensweise 3! mal zu oft gezählt wurde, gleiches gilt für 2 2 . Das letzte Feld ist leer, da es egal ist was dort steht hauptsache man denkt an die 2! zuviel gezählte Möglichkeiten somit dachte ich an die Lösung:
$\begin{eqnarray*} \frac{6*5*4}{3!*2!} = \frac{120}{12} = 10 \end{eqnarray*}$
Was ja leider nicht stimmt, vielleicht habe ich zuviel abgezogen(?)

2. Idee:
Siebformel (Inklusion - Exklusion)
Man stelle sich vor, man hätte nicht diese Menge {1, 1, 1, 2, 2, 3} sondern wie in Teil c diese Menge {1, 1, 1, 2, 2, 2, 3, 3, 3} dann gäbe es für jede Stelle drei Möglichkeiten, also $\begin{eqnarray*} 3^3 = 27 \end{eqnarray*}$ von der ziehe ich nun alle Abbildungen ab, die:
die 3 nicht treffen (7 Stück),
die 2 nicht treffen (4 Stück) und
die 1 nicht treffen (3 Stück) und addiere alle die:
die 3 und 2 nicht treffen (10 Stück)
die 3 und 1 nicht treffen (9 Stück)
die 2 und 1 nicht treffen (7 Stück) und subtrahiere alle die:
die 1, 2 und 3 nicht treffen (13 Stück)
Das entspricht:
27 - 14 + 26 - 13 = 26
Stimmt ja leider auch nicht unglücklich

3. Idee:
Ein Blick in unsrer Skript smile

dort gibt es einen Überblick zu verschiedenen kombinatorischen Formeln. Dazu muss man wissen ob die Abbildung inj., surj, bij. oder gar nichts von all dem ist und letzteres trifft auf diesen Fall zu, da sowas wie 1 1 1 erlaubt ist. D.h nicht surj. weil 3 und 2 fehlt und nicht inj. da 1 öfter als nur einmal vorkommt. Daher bleiben nur noch so Sachen wie:
$\begin{eqnarray*} \begin{pmatrix} n + m - 1 \\ n \end{pmatrix} \end{eqnarray*}$ und

$\begin{eqnarray*} \sum\limits_{k=0}^m S(n,k)\ \ \ (wobei\ S(n,k)\ die\ Stirling\ Zahlen\ sind) \end{eqnarray*}$ das ganze entspricht also den Bell Zahlen und schließlich

$\begin{eqnarray*} P(n+m,m)\ \ \ (hierbei\ entspricht\ P(n+m, m)\ den\ Zahlpartitionen) \end{eqnarray*}$

In letzterem sehe ich hier keine keinen Sinn, die Bellzahlen brauch man gar nicht erst zu versuchen, da S(6,3) schon 90 ergibt, daher wird das niemals weniger und den ersten Fall habe ich auch schon wie folgt versucht:
$\begin{eqnarray*} \begin{pmatrix} n + m - 1 \\ n \end{pmatrix} = \begin{pmatrix} 6 + 3 - 1 \\ 6 \end{pmatrix} = \begin{pmatrix} 8 \\ 6 \end{pmatrix} = 28 \end{eqnarray*}$

4. Idee:
Dazu gibts keine "einfache" Formel, daher soll man die auch nur aufschreiben. smile

Trotzdem interessiert es mich smile

Vielen Dank schonmal für euer interesse und sry. wegen dem langen Text,
Liebe Grüße Matthias

23.02.2014, 21:41

Math1986

Auf diesen Beitrag antworten »

RE: Alle unterschiedlichen 3-stellige Zahlenkombinationen von {1, 1, 1, 2, 2, 3}
Es wird, denke ich, auf Möglichkeit 4 hinauslaufen:
Zunächst musst du dir überlegen welche Zahlen du auswählst, dann musst du dir überlegen, wie du diese permutierst. Die Anzahl der Permutationen hängt aber gerade von der Auswahl ab, die du getroffen hast: Wenn du 3 verschiedene Zahlen auswählst dann kannst du die auf 6! verschiedene Möglichkeiten anordnen, wenn du 3 gleiche Zahlen wählst hast du nur eine Möglichkeit. Ich sehe da keine Formel mit der man das elegant lösen könnte.

23.02.2014, 22:36

Brayn410

Auf diesen Beitrag antworten »

RE: Alle unterschiedlichen 3-stellige Zahlenkombinationen von {1, 1, 1, 2, 2, 3}
Hallo Math1986,

vielen Dank für deine schnelle Antwort. Dieses Problem ist mir beim probieren auch aufgefallen, wobei du bei deiner Aussage:

Zitat:

Wenn du 3 verschiedene Zahlen auswählst dann kannst du die auf 6! verschiedene Möglichkeiten anordnen

bestimmt nicht 6! sondern 3! = 6 meintest oder?

Liebe Grüße Matthias

23.02.2014, 23:00

HAL 9000

Auf diesen Beitrag antworten »

@Brayn410

Zu deiner 2.Idee mit der Siebformel:

Was meinst du mit "nicht treffen" ??? Wenn schon, dann kann man die Siebformel hier so anwenden:

$\begin{eqnarray*} \Omega \end{eqnarray*}$ ... alle Variationen mit Wiederholung von 3 aus {1,2,3}

$\begin{eqnarray*} A_2 \end{eqnarray*}$ ... alle Variationen aus $\begin{eqnarray*} \Omega \end{eqnarray*}$ , die mehr als zweimal (d.h. dann genau dreimal) eine 2 enthalten

$\begin{eqnarray*} A_3 \end{eqnarray*}$ ... alle Variationen aus $\begin{eqnarray*} \Omega \end{eqnarray*}$ , die mehr als einmal (d.h. zwei- oder dreimal) eine 3 enthalten

Nun ist $\begin{eqnarray*} |A_2| \end{eqnarray*}$ = 1 und $\begin{eqnarray*} |A_3| = 3\cdot 2 + 1 \end{eqnarray*}$ und beide sind disjunkt. Die gesuchte Anzahl ist nun

$\begin{eqnarray*} |\Omega| - |A_2| - |A_3| + |A_2\cap A_3| = 3^3 - 1 - 7 + 0 = 19 \end{eqnarray*}$ .

Zumindest hast du gelernt, dass es selbst relativ einfach formulierierbare kombinatorische Probleme gibt, die sich nicht einfach nur durch Einsetzen in Standardformeln lösen lassen.

23.02.2014, 23:30

Math1986

Auf diesen Beitrag antworten »

RE: Alle unterschiedlichen 3-stellige Zahlenkombinationen von {1, 1, 1, 2, 2, 3}

Zitat:

Original von Brayn410
vielen Dank für deine schnelle Antwort. Dieses Problem ist mir beim probieren auch aufgefallen, wobei du bei deiner Aussage:

Zitat:

Wenn du 3 verschiedene Zahlen auswählst dann kannst du die auf 6! verschiedene Möglichkeiten anordnen

bestimmt nicht 6! sondern 3! = 6 meintest oder?

Ja, natürlich smile

23.02.2014, 23:59

Brayn410

Auf diesen Beitrag antworten »

Hallo HAL 9000,

so was ärgerliches genau, du hast mal wieder recht, vielen vielen Dank smile

Ich wollte mit "nicht treffen" ausdrücken dass diese Elemente von den maximalen 27 abgezogen werden. Besser gesagt, diese acht 333, 332, 331, 323, 313, 233, 133, 222 kann man ja nicht erzeugen. Ich bin das Problem wohl total falsch angegangen.

Vielen Dank nochmal smile

Liebe Grüße Matthias

Neue Frage »

Antworten »

Alle unterschiedlichen 3-stellige Zahlenkombinationen von {1, 1, 1, 2, 2, 3}

Verwandte Themen