Kombinatorik Möglichkeiten Wortbildung?
Hallo,
ich würde gerne Wissen, wie viele Möglichkeiten es gibt verschiedene Wörter der Länge 8 aus den 16 Buchstaben des Wortes RHABARBERBARBARA (5A, 5R, 1H, 4B, 1E) zu bilden.
Ich komme leider auf keine zufriedenstellende Lösung.
3 Antworten
Ich komme auf 76468 Möglichkeiten.
Ich habe allerdings keine geschlossene Art der Berechnung gefunden.
Ich habe zuerst ("von Hand") ermittelt, wieviele Möglichkeiten es mit 5 "a"s gibt, mit 4, mit 3, mit 2, mit 1 und mit 0.
Für jede Verteilung habe ich dann die Möglichkeiten berechnet.
Beispiel:
Möglichkeiten für 3a, 4r und 1 b: 8!/(3!*4!*1!)
Danke, dass du dir den Aufwand gemacht hast! Es verunsichert mich etwas, dass die Aufgabe auf dem ersten Arbeitsblatt von Diskrete Mathematik und Logik ist :')
Ich kam nur auf 64456, kann aber sein, daß ich ein paar Kombinationen übersehen habe oder mich beim Rechner vertippt.
Die Methode sollte auf jeden Fall zum Ziel führen. Ich weiß aber nicht, wo der logische Fehler in meiner Antwort steckt; sie muß falsch sein, denn sie führt zu einem viel zu kleinen Ergebnis.
es ist ja auch nicht gesagt, dass meine Lösung stimmt.
Dies sind meiner Meinung nach die möglichen Buchstabenverteilungen:
a r b e h
5 3 0 0 0
5 2 1 0 0
5 2 0 0 1
5 2 0 1 0
5 1 2 0 0
5 1 1 0 1
5 1 1 1 0
5 1 0 1 1
5 0 3 0 0
5 0 2 0 1
5 0 2 1 0
5 0 1 1 1
4 4 0 0 0
4 3 1 0 0
4 3 0 0 1
4 3 0 1 0
4 2 2 0 0
4 2 1 0 1
4 2 1 1 0
4 2 0 1 1
4 1 3 0 0
4 1 2 0 1
4 1 2 1 0
4 1 1 1 1
4 0 4 0 0
4 0 3 0 1
4 0 3 1 0
4 0 2 1 1
3 5 0 0 0
3 4 1 0 0
3 4 0 0 1
3 4 0 1 0
3 3 2 0 0
3 3 1 0 1
3 3 1 1 0
3 3 0 1 1
3 2 3 0 0
3 2 2 0 1
3 2 2 1 0
3 2 1 1 1
3 1 4 0 0
3 1 3 0 1
3 1 3 1 0
3 1 2 1 1
3 0 4 0 1
3 0 4 1 0
2 5 1 0 0
2 5 0 0 1
2 5 0 1 0
2 4 2 0 0
2 4 1 1 0
2 4 1 0 1
2 4 0 1 1
2 3 3 0 0
2 3 2 1 0
2 3 2 0 1
2 3 1 1 1
2 2 4 0 0
2 2 3 0 1
2 2 3 1 0
2 2 2 1 1
2 1 4 0 1
2 1 4 1 0
2 1 3 1 1
2 0 4 1 1
1 5 2 0 0
1 5 1 0 1
1 5 1 1 0
1 5 0 1 1
1 4 3 0 0
1 4 2 0 1
1 4 2 1 0
1 4 1 1 1
1 3 4 0 0
1 3 3 0 1
1 3 3 1 0
1 3 2 1 1
1 2 4 0 1
1 2 4 1 0
1 2 3 1 1
1 1 4 1 1
0 5 3 0 0
0 5 2 1 0
0 5 2 0 1
0 5 1 1 1
0 4 4 0 0
0 4 3 0 1
0 4 2 1 1
0 3 4 1 0
0 3 4 0 1
0 3 3 1 1
0 2 4 1 1
Auf was beziehen sich die fehlenden 4310 und wie kommst du darauf?
Um die Aufgabe zu berechnen, mußt Du überlegen, wie Du die Buchstaben, die ja unterschiedlich oft vorhanden sind, auf unterschiedliche Arten so summieren kannst, daß jeweils ein Wort mit 8 Buchstaben entsteht.
Das machst Du am besten mit einer Tabelle.
In die Kopfzeile schreibst Du 5 5 4 1 1, denn so oft kommen die einzelnen Buchstaben im Pool vor: 5 A 5 R 4 B 1 E 1 H
Ich habe zunächst einmal überlegt, wie viele Verteilungen mit 5 A möglich sind.
Da kommst Du auf
5 3 0 0 0;
5 2 1 0 0;
5 2 0 1 0
5 2 0 0 1;
5 1 2 0 0;
5 1 1 0 1;
5 1 1 1 0;
5 1 0 1 1;
5 0 2 0 1;
5 0 2 1 0;
5 0 1 1 1.
Alle diese Kombinationen haben gemeinsam, daß sie sich zu 8 summieren.
Nun kannst Du Dir jede einzelne Verteilung vornehmen.
Aus 5 A und 3 R kannst Du 8!/(5!*3!) unterschiedliche Wörter bilden.
Der Zähler ist immer 8!, weil das Wort aus 8 Buchstaben besteht, in den Nenner kommen Buchstaben, die mehrfach vorkommen, als Fakultäten, um ununterscheidbare Wörter auszuschließen.
Danach nimmst Du Dir die Verteilungen mit 4 A vor, also 4 3 1 0 0 usw.
Man kann sehr leicht eine Verteilung übersehen und sich hinterher beim Berechnen der Kombinationen jeder einzelnen Verteilung sehr schnell vertippen.
Deswegen kommen hier laufend unterschiedliche Ergebnisse heraus.
Mathematisch stellt die Aufgabe keine besondere Herausforderung dar, ist aber mit mühseliger Rechnerei und Auflisterei verbunden, die äußerst fehleranfällig ist.
Die Idee mit den unterschiedlichen Verteilungen hatte ich auch zeitweise, aber ich dachte, es gäbe sicher eine einfachere Lösung, denn das ist eine 1 Punkt Aufgabe auf einem 30 Punkte Arbeitsblatt. Dir/Euch vielen Dank für die aufgewendete Mühe!
Genau das war auch mein Ansatz.
Meine Zahl entstand excelgestützt, indem ich eben (händisch) eingetragen habe, welche Verteilungsmöglichkeiten (Wie viele a's, r's und so weiter) es gibt und danach die Möglicheiten berechnet habe, wieviele unterschiedliche Permutationen es dazu gibt.
Anzahl Permutationen bei der Verteilung v*a w*r x*b y*e und z*h:
8!/(v!*w!*x!*y!*z!)
Leicht möglich, dass ich bei den Verteilungsmöglichkeiten eine Fehler gemacht habe.
In meiner Antwort hatte ich ja gehofft, auf eine einfache Methode gestoßen zu sein. Die war aber falsch. Ich weiß auch, warum. Ich kann sehr viele unterschiedliche 8-Buchstaben-Wörter mit 5 A bilden. Ich kann aber keine zwei von ihnen zu einem 16-Buchstaben-Wort verbinden, weil ich dann 10 A bräuchte, soviel sind aber gar nicht vorhanden.
Deswegen brauche ich wesentlich mehr Wörter mit 8 Buchstaben, um auf über 60 Mio 16-Buchstaben-Wörter zu kommen.
Es kann sein, daß es einen anderen Weg gibt, habe aber keine Ahnung, welchen.
Das Auflisten und einzelne Berechnen klappt auf jeden Fall, wenn man es sehr sorgfältig macht, dauert aber seine Zeit.
Dann kann ich jetzt beruhigt weitermachen! Danke!
Danke dir! Noch eine kurze Frage, du hast die Möglichkeiten für 3a, 4r und 1 b mit 8!/(3!*4!*1!), gibt es zu der Rechnung irgendeinen Begriff um die Herleitung nachzuschauen? Hab nichts dazu in meinem Skript und mit der Thematik erst seit kurzem zu tun.
Einen Begriff dazu kenne ich nicht.
Aber woher es kommt, kann ich dir sagen:
Ich habe (bei dem Beispiel) die 8 Zeichen 3*a, 4*r und 1*b.
8 (verschieden) Zeichen kann man prinzipiell auf 8! Möglichkeiten anordnen.
Da aber die 3 a's nicht unterscheidbar sind, dividiert man noch durch die Permutationen dieser 3 as, also durch 3!
(Also 3! = 6
Es ist egal ob die a's an den Positionen 123, 132, 213, 231, 312 oder 321 sind - das ist alles das gleiche)
Das gleich mache ich mit den 4 r's und (der Vollständigkeit halber) dem einen b.
Hallo,
überlege zunächst, wieviel unterschiedliche Wörter Du mit allen 16 Buchstaben bilden kannst. Das sind 16!/(5!*5!*4!)=60.540.480 16buchstabige Wörter, die sich alle voneinander unterscheiden.
Jedes dieser Wörter besteht aus jeweils zwei Wörtern mit je acht Buchstaben. Dabei ist es unmöglich, daß eins von ihnen aus identischen Hälften besteht, denn die vorhandenen Buchstaben lassen sich nicht auf zwei genau gleiche Wörter mit acht Buchstaben verteilen. Jedes Wort mit 16 Buchstaben besteht also aus zwei unterschiedlichen Wörtern mit 8 Buchstaben. Andererseits kann man aus einem Paar Wörtern mit 8 Buchstaben zwei unterschiedliche Wörter mit 16 Buchstaben formen, indem man ihre Reihenfolge vertauscht.
Die Frage ist, wieviele unterschiedliche 8-Buchstaben-Wörter benötige ich, um jeweils zwei von ihnen zu einem von diesen 60 Mio. 16-Buchstaben-Wörtern zu kombinieren? Die Formel n über 2 liefert mir die Zahl der Paare, die ich aus n Wörtern bilden kann, wobei noch nicht berücksichtigt ist, daß ich die Paare untereinander vertauschen kann, so daß sie sich nur durch die Reihenfolge unterscheiden. Berücksichtige ich die Reihenfolge nicht, bekomme ich nur
30.270.240 unterschiedliche 16-Buchstaben-Wörter, die aus Paaren von n 8-Buchstaben-Wörtern gebildet wurden.
n über 2=30.270.240.
Durch Probieren findet man heraus, daß n etwa 7781 sein muß.
Wenn ich aus 7781 8-Buchstaben-Wörtern 2*30.270.240 16-Buchstaben-Wörter bilden kann und diese alle 16-Buchstaben-Wörter sind, die sich aus dem vorhandenen Buchstabenmaterial bilden lassen, kann es nicht mehr als diese 7781 8-Buchstaben-Wörter geben. Gäbe es mehr, könnte ich aus ihnen mehr 16-Buchstaben-Wörter bilden, als die einzelnen Buchstaben überhaupt hergeben - und das sollte nicht möglich sein.
Ohne Gewähr.
Willy
Schon mal vielen, vielen Dank für die ausführliche Antwort. Ich versuche gerade noch ein kleines Skript zu schreiben und ein hoffentlich halbwegs sicheres Reverenz-Ergebnis mit bruteforce zu erreichen. Mal schauen obs klappt.
Es müssen doch mehr Wörter möglich sein.
Allein die Kombinationen mit 4 A ergeben über 8000 Wörter.
64456 ist nun meine Alternative.
Ich habe mal alle Kombinationen aufgelistet, wie man unterschiedlich viele A, R, B, H und E zu 8 Buchstaben summieren kann, also 5+3+0+0+0, 5+2+1+0+0 usw. wobei ich natürlich berücksichtigt habe, daß E und H nur einmal, das B viermal und A und R je fünfmal vorkommen.
Dann habe ich für jede Kombination errechnet, wie viele Wörter sich aus diesen 8 Buchstaben jeweils formen lassen und diese dann summiert.
Keine besonders elegante Methode, aber sie scheint mir doch der Sache näherzukommen.
Das ist einfach eine Kombination. Die Formel dazu lautet....
Sprich: Es gibt 12870 Möglichkeiten aus 16 Buchstaben ein 8-buchstabiges Wort zu bilden. Ob das Wort im Wörterbuch steht, kann freilich nicht garantiert werden - es kann also z.B. auch AAAAARRR lauten.
Naja, ich glaube nicht, dass das so einfach ist. Einerseits wird beim Binomialkoeffizient doch die Reihenfolge nicht beachtet, welche hier beachtet werden müsste, oder täusche ich mich? Zudem sind es ja eigentlich nur 5 Buchstaben, die auch teilweise "aufgebraucht" werden können, was die Möglichkeiten weiter einschränkt. Zumindest waren das meine Gedanken dazu.
Stimmt, da habe ich eine falsche Antwort gegeben. Sorry dafür!
Das ist einfach eine Kombination. Die Formel dazu lautet....
Scheint doch nicht so einfach zu sein. Deine Antwort ist falsch.
Ich korrigiere mich nach oben, da ich einen Fehler entdeckt habe: ich komme auf 77238 Möglichkeiten.