Autor |
Beitrag |
Heike Schmid (Asn)
| Veröffentlicht am Samstag, den 14. Juli, 2001 - 15:15: |
|
Habe da ein mittelgroßes Problem: Wieviele Worte ( auch sinnlose) der Länge 11 kann man aus den Buchstaben ABRAKADABRA bilden( 5*A, 2*B, 2*R, 1*D, 1*K) ? Und wieviele Worte der Länge 10? Und wie errechnet man das? |
Lupo
| Veröffentlicht am Samstag, den 14. Juli, 2001 - 17:49: |
|
Hallo Heike, Mir fallen dazu zwei Betrachtungsweisen ein. Um die Binomialkoeffizienten mit in die Rechnung zu bringen, kann man betrachten, dass man die Buchstaben auf die 11 Plätze verteilt: Es gibt 11 Möglichkeiten, dem K einen Platz zuzuweisen => Faktor 11 Es gibt noch 10 Möglichkeiten, dem D einen Platz zuzuweisen => Faktor 10 Es gibt noch 9 Möglichkeiten, dem ersten R einen Platz zuzuweisen => Faktor 9 Es gibt noch 8 Möglichkeiten, dem zweiten R einen Platz zuzuweisen => Faktor 8 Jetzt wurde noch nicht berücksichtigt, dass es egal ist, ob erst das eine R oder erst das andere R den neuntletzten Platz bekommt. Deshalb ist dies durch zwei zu teilen: Das kommt heraus auf (92) ("9 über 2") = 9*8/2 = 36 Also hier nur => Faktor 36 Es gibt noch 7 Möglichkeiten, dem ersten B einen Platz zuzuweisen => Faktor 7 Es gibt noch 6 Möglichkeiten, dem zweiten B einen Platz zuzuweisen => Faktor 6 Wieder durch 2 dividieren, da es egal ist, welches B zuerst seinen Platz bekommt: (72) = 7*6/2 = 21 => Faktor 21 Jetzt sind noch 5 Plätze frei, es gibt nur noch eine Möglichkeit, da sie alle mit "A" belegt werden müssen: also Faktor 1, formal auch schreibbar als (55) =1 Nun alle Faktoren multiplizieren: (111)* (101)* (92)* (72)*(55) = 11 * 10 * 9*4 * 7*3 = 83160. Anders kann man sich auch fragen, auf wie viele Arten man 11 Objekte anordnen kann. Das sind 11!. Jetzt ist es aber egal, ob ein A z.B. das dritte A war oder das vierte, also müssen wir durch die Anzahl aller möglichen Vertauschungen der 5 A's wieder teilen: teile durch 5!. Ebenso mit den 2 B'2 und den 2 R's: Es gibt also 11!:5!:2!:2!=83160 verschiedene Worte mit 11 Buchstaben. Formal konnte man auch noch durch 1! wegen D und 1! wegen K teilen, ändert nichts am Ergebnis, da 1!=1 Die letzte Methode find ich leichter, kommen leider keine Binomialkoeffizienten drin vor. Bei einem Wort mit 10 Buchstaben kann man das ganze so auffassen, dass zuerst einer weggelassen werden soll. Dies kann ich nicht anders, als fünfmal einzeln zu betrachten, dass jeweils einer der fünf Buchstaben weggelassen wird. Dann lässt sich das Problem auf das oben zurückführen: Fall a) A wird weggelassen: Es gibt 4*A, 2*B, 2*R, 1*D, 1*K Anzahl Wörter = a = 10!:4!:2!:2!:1!:1! = 37800 Fall b) B wird weggelassen: Es gibt 5*A, 1*B, 2*R, 1*D, 1*K Anz. Wörter = b = 10!:5!:1!:2!:1!:1!=15120 Fall c) R wird weggelassen: aus Symmetriegründen dasselbe Problem wie bei b): c= 10!:5!:2!:1!:1!:1!=15120 Fall d) D wird weggelassen: d= 10!:5!:2!:2!:1! = 7560 Fall e) K wird weggelassen: aus Symmetriegründen dasselbe Problem wie bei d): e= 10!:5!:2!:2!:1! = 7560 Die Möglichkeiten aller Fälle addieren (nicht multiplizieren, da sie entweder-oder-Fälle sind): ergibt 83160. Das ergibt wieder dasselbe wie eben. Das kann bestimmt jemand kürzer zeigen. Ich warte mal gespannt drauf. Lupo |
Heike Schmid (Asn)
| Veröffentlicht am Sonntag, den 15. Juli, 2001 - 09:05: |
|
Hallo Lupo, im Prinzip ist es egal, wie lange es dauert, das zu zeigen, ich bin heilfroh, dass es zumindest eine ( nachvollziehbare) Lösung gibt. Ich habe noch ein Problem, das irgendwas mit Binominalkoeffizienten zu tun haben soll. Hast du dazu auch eine Idee? >> bestimmen sie die Anzahl der geordneten Paare(A,B), wo A (Teilmenge von) B ( Teilmenge von) {1,2,....,n} mit n (element von)|N . |
SpockGeiger (Spockgeiger)
| Veröffentlicht am Sonntag, den 15. Juli, 2001 - 12:51: |
|
Hallo Heike Für B gibt es 2n Möglichkeiten. Die Anzahl der Möglichkeiten für A hängt dann von der Anzahl der Elemente in B ab. Nehmen wir an, B hätte k Elemente, so gibt es für A 2k Möglichkeiten, also sortieren wir die Möglichkeiten für B nach der Anzahl der Elemente. Es gibt (nk) Möglichkeiten, dass B k Elemente hat. Dann gibt es für A, wie gesagt, 2k Möglichkeiten. Summieren wir das auf, so erhalten wir Sn k=0(nk)2k1n-k Den letzten Faktor mit der Eins habe ich dazugemogelt. Er ändert nichts, aber nun erkennt man, dass der Ausdruck gerade 3n ist. viele Grüße SpockGeiger |
Heike Schmid (Asn)
| Veröffentlicht am Sonntag, den 15. Juli, 2001 - 14:01: |
|
Spockgeiger also, ich glaub dir das ja alles ;-) ,aber könntest du mir auch noch sagen, über was du eigentlich redest? Ich hab da nämlich momentan überhaupt keine Ahnung. Grüße Heike |
SpockGeiger (Spockgeiger)
| Veröffentlicht am Sonntag, den 15. Juli, 2001 - 14:38: |
|
Hallo Heike Ich hab auf Deine letzte Frage geantwortet. Wenn Du jetzt auch nicht weiß, wovon ich rede, musst Du das präzisieren. viele Grüße SpockGeiger |
Heike Schmid (Asn)
| Veröffentlicht am Sonntag, den 15. Juli, 2001 - 15:40: |
|
Okay, konkrete Fragen: 1. wie kann es nur für die Teilmenge B Möglichkeiten geben, wenn die Anzahl der geordneten Paare aus den Mengen A und B gesucht ist? 2. was soll deine Verwendung des Summenzeichens bedeuten? Ich kenne das zwar, aber irgendwie hatten wir da andere Bezeichnungen. 3. >> "den letzten Faktor mit der Eins habe ich dazugemogelt. Er ändert nichts, aber nun erkennt man, daß der Ausdruck gerade 3^n ist." Heißt das, daß die gesucht Antwort 3^n ist? p.s.: mag sein, daß ich ein bischen schwer von Begriff bin heute, aber auf welche Frage du geantwortet hast, war mir dann doch klar ;-)) Grüße und Danke Heike |
SpockGeiger (Spockgeiger)
| Veröffentlicht am Sonntag, den 15. Juli, 2001 - 16:07: |
|
Hallo Heike Ich wollte nie andeuten, Du seist schwer von Begriff, ich konnte nur nichts mit Deiner Anfrage anfangen. Hier die Antworten: 1. Das ist die Standardmethode. Da die Möglichen A's von B abhängen, zählen wir zu jedem möglichen B die Möglichkeiten für A und summieren auf. Da hier auch noch für mehrere Fälle von B (nämlich bei gleicher Mächtigkeit) die Anzahl der Möglichkeiten für A die gleiche ist, fassen wir solche Möglichkeiten für B zusammen und multiplizieren sie mit der jeweiligen Anzahl der Möglichkeiten für A. Wenn wir diese Zahlen aufsummieren, erhalten wir gerade die Gesamtanzahl. 2. Es wird über den Index k aufsummiert, wobei k von 0 bis n läuft. 3. Die Summe ist gerade die Gesamtanzahl der Möglichkeiten, im Prinzip also schon das Ergebnis, nur mit der Eins dabei ist es die Binomialformel für (1+2)n=3n, und das ist dann die Antwort. Wenn ich mich immer noch mißverständlich ausdrücke, bitte ich das zu entschuldigen, und frag bitte solange nach, bis es klar ist. viele Grüße SpockGeiger |
Heike Schmid (Asn)
| Veröffentlicht am Sonntag, den 15. Juli, 2001 - 17:24: |
|
O.K. Es ist klar, ich habs kapiert. Im Endeffekt ist es einfach (wie meistens), aber ich stand da schon eine Weile wie der Ochs vorm Berg davor. Liegt also nicht an dir, wenn ich glaube, ich sei ein bischen schwer von Begriff. machs gut Heike |
|