Hallo, Ich habe da mal eine Kombinatorik-Frage. Im Papula und Bronstein bin ich nicht so recht fündig geworden, drum frage ich mal hier. Folgendes Problem: Gegeben seien die Buchstaben a und b. Wie viele Kombinationen zu 4 Buchstaben lassen sich bilden, wenn jeweils 3 Buchstaben gleich sein sollen? Es gibt die Kombinationen aaab aaba abaa baaa Sowie bbba bbab babb abbb Also 8, aber wie berechne ich das? Es ist nicht die Fakultät und nicht der Binominalkoeffizient. Wenn 2 gleiche Buchstaben verwendet werden sollen, gibt es offenbar 6 Möglichkeiten: aabb abab baab abba baba bbaa Das geht mit 4!/(2!*2!) Warum klappt es also beim Problem oben nicht?
Es gibt 4 Positionen für den alleinstehenden Buchstaben und dann kann man die Buchstaben noch austauschen. Hast Du doch eigentlich auch schon erkannt. Also kleine Formel: M = p*a, wobei p=..... 4 und a= .... 2 -> M = 8 ============ so ungefähr?
Kann sein, daß das eine Problemstellung ist, die nicht mit einer Gleichung lösbar ist. Bei nur einem "gleichen" Buchstaben passt Deine Gleichung ja auch nicht, bei 4 gleichen gibts nur noch zwei Lösungen. Ich halte Deine "Lösung" bei dreien daher für eine Zufallspassung...
Die Frage ist gleichbedeutend mit: Wieviel Kombinationen gibt es k_a von n Plätzen mit a zu belegen + Wieviel Kombinationen gibt es k_b von n Plätzen mit b zu belegen dementsprechend 2mal der Bi.-Koeff, wobei man den Fall betrachten muss k_a = k_b da fällt das *2 weg
Hallo, das was du meinst ist ja nix anderes wie Permutation mit Wiederholung. (Im Bronstein ist das bei mit Kapitel 16.1.1.3. Du hast n Element von denen k gleich sind. Du musst dann 4!/3! = 4 rechnen. Du musst allerdings beachten das hier nicht berücksitigt wird das die Elemente vertauscht werden also 3*A und 1*B sowie 3*B und 1*A . Wie man das noch berücksichtigt müsste man mal in ner ruhigen Minute ausknoppeln. In dem einfachen fall kann man ja einfach das ergebnis mal 2 nhemn. Gruß Peter
Der zweite Buchstaben spielt keine Rolle. Die Frage lautet deshalb: Auf wie viele Arten kann ich p Objekte auf n Plätzen verteilen. Tja, einfach: Das erste Objekt kann ich auf n Plätze, das zweite auf (n - 1) (einer ist ja schon besetzt), das dritte auf (n - 2) usw. Gibt also n * (n - 1) * (n - 2) * ... . Da die Objekte aber alle gleich sind, muss man noch die internen Vertauschungen entfernen, das ist bekanntlich Fakultät p. Soweit die kombinatorische Erklärung, das Ausrechnen lasse ich dir als Übungsaufgabe ;-)
Also, dass da ein *2 sein muss, ist klar wieso. Ich wundere mich nur, wie man im allgemeinen Fall darauf käme. Wenn ich 1000 Elemente anordnen müsste, dann könnte ich ja nicht durch probieren alle möglichen Kombinationen finden und dann daran ablesen, dass da noch ein Faktor 2 hin muss ;-)
Diese Kategorie von Problemen läuft unter dem Namen: "Permutationen von klassenweise äquivalenten Objekten" Bei Wikipedia steht ein Beispiel, dass dir bekannt vorkommen sollte. Es ist dort recht gut erklärt.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.