Kombinatorik



  • Hallo Forum,

    ich steh grad auf dem Schlauch:
    In einer Schale liegen n nummerierte Kugeln. Wieviele Möglichkeiten gibt es die Kugeln per Hand zu entnehmen? Anordnung in der Hand egal, es kommt nur auf die Menge in der Hand an. Laut Skript n! Möglichkeiten. Was sind die 6 Möglichkeit?
    Beispiel: 3 Kugeln.
    1. Möglichkeit: Ich sie einzeln heraus.
    2. 1+2, dann 3 heraus.
    3. 1+3, dann 2 heraus.
    4. 2+3, dann 1 heraus.
    5. Ich nehme alle 3 zugleich heraus.
    6 ?

    Viele Grüße

    .



  • Keine?

    Mir leuchtet die Aufgabenstellung noch nicht so ganz ein, so wie Du die Lösungen schreibst, wäre ja auch

    3, dann 1+2
    und
    3, dann 2+1

    eine gültige Lösung?

    Wenn es nur auf die Menge in der Hand ankommt, sind Deine Lösungen 2,3,4 doch alle identisch?

    Die Lösung n! deutet eigentlich darauf hin, daß es nur auf die Reihenfolge der Ziehung ankommt, d.h. eine reine Permutation.

    Aber die von Dir beschriebene Aufgabenstellung liest sich anders.



  • Deine Beschreibung ist ein wenig wirr. Du hast also n Kugeln. Willst du nun alle n Kugeln ziehen? Dann ist eigentlich nur die Reihenfolge interessant, in der du die Kugeln ziehst. Du schreibst aber

    Anordnung in der Hand egal, es kommt nur auf die Menge in der Hand an.

    Da dein Skript von n! Möglichkeiten redet, gehe ich trotzdem davon aus, dass es hier um die unterschiedlichen Reihenfolgen geht. Dann sind die 6 Möglichkeiten bei den Kugeln {1, 2, 3}:
    123
    132
    213
    231
    312
    321

    Du hast n Möglichkeiten beim Ziehen der ersten Kugel. Beim Ziehen der zweiten Kugel sind nur noch n-1 Kugeln übrig, also hast du hier n-1 Möglichkeiten usw. Dann hast du insgesamt n*(n-1)(n-2)...*2*1 = n! Möglichkeiten.



  • Ist vermutlich nicht gedacht unterschiedliche Mengen herauszunehmen, sondern nur die Reihenfolge, und dann wäre es:
    1-2-3
    1-3-2
    2-1-3
    2-3-1
    3-1-2
    3-2-1
    sind 6. Eben 3!

    edit: okay - zu langsam... 🕶



  • Ne, es geht um die Anzahl der Mengenbildungen um die Kugeln zu entfernen. Ob in der Hand nun 1+2 oder 2+1 liegt ist egal.
    1. {1}, {2}, {3}
    2. {1,2}, {3}
    ...

    Und keine Kugel zu entfernen löst das Problem nicht, da alle Kugeln entfernt werden müssen. Bei 4 Kugeln sind es 18 Möglichkeiten. Das kann nicht n! sein.



  • Also gehts darum, Teilmengen auszuwählen? Dann gibts bei den Kugeln {1,2,3} folgende acht Möglichkeiten:
    {}
    {1}
    {2}
    {3}
    {1,2}
    {1,3}
    {2,3}
    {1,2,3}

    Insgesamt gibt es bei n Kugeln $$\sum\limits_{k=0}^n {n \choose k} = (1+1)^n = 2^n$$ Möglichkeiten.



  • Ne, ein Topf mit Kugeln und es sollen alle Kugeln entfernt werden.
    Ich habe den Prof eine EMail geschickt. Ich glaube da ist ein Fehler im Skript.



  • Also gehts darum, die gesamte Menge auf alle möglichen Arten in paarweise disjunkte Teilmengen zu zerlegen, deren Vereinigung die Gesamtmenge ergibt?



  • @Michael: Genau.



  • Wenn du n Kugeln hast, dann suchst du jetzt anscheinend die Anzahl der Möglichkeiten, eine n-Menge zu partitionieren, wobei die Reihenfolge innerhalb der Teilmengen egal ist, aber ihre Reihenfolge untereinander nicht egal ist.
    Die Anzahl der verschiedenen Partitionierungen in k Teilmengen einer n-Menge ist $$S_{n,k}$$ (Stirlingsche Zahl zweiter Art). Da die Reihenfolge wichtig ist, müssen wir noch mit der Zahl der Permutationen multiplizieren:

    k=1nk!Sn,k\sum_{k=1}^n k!S_{n,k}

    Mir kommt die Formel irgendwie bekannt vor, vielleicht gibts dafür noch was kürzeres, aber ich hab grade keine passende Literatur zur Hand.

    Zu den Stirlingschen Zahlen: Siehe Wikipedia. Da gibt es einige Möglichkeiten, sie zu berechnen, rekursiv und explizit.



  • Rekursiv hätte ich Folgendes anzubieten: f(1) = 1, f(n) = n(f(n-1) - 1) + 2.



  • Was Ihr schreibt könnte hinhauen.
    Ich warte mal auf die Antwort des Prof.

    Danke 🙂


Log in to reply