Kombinatorik/Fakultät

    Guten Tag,

    bei folgender Aufgabe habe ich ein Problem :

    In einem Getränkemarkt kann man sich aus 3 Getränkesorten seine Getränkeliste aus insgesamt 12 Flaschen selbst zusammenstelllen. Dem Käufer ist die Anordnung der Flaschen in der Kiste egal. Wie viele Möglichkeiten gibt es?

    91 ist die Lösung.

    Mein größtes Problem ist,dass ich nicht weiß , wie ich n und wie ich k bestimmen soll.

    N war meines Erachtens immer die Auswahl , die möglich ist und k , was ich tatsächlich auswähle.

    Indem Fall wäre es eine Auswahlmöglichkeit ohne wesentliche Reihenfolge und Wiederholungen sind zugelassen.

    Deshalb wäre ich die Formel :
    ( n + k -1)
    ( k )


    Viele Grüße

    tragosso

    Wenn man bei kleinen Anzahlen von Sorten (S) und Flaschen (F) einfach mal die Möglichkeiten zählt, ergibt sich diese Liste (Flaschenzahl nach rechts, Sortenzahl nach unten):

    [TEX] \begin{array}{ccccccc} | \ Fl \ 00 \ 01 \ 02 \ 03 \ 04 \\ So \ | \ - \ - \ - \ - \ - \\ 01 \ | \ 01 \ 01 \ 01 \ 01 \ 01 \\ 02 \ | \ 01 \ 02 \ 03 \ 04 \ 05 \\ 03 \ | \ 01 \ 03 \ 06 \ 10 \ 15 \\ 04 \ | \ 01 \ 04 \ 10 \ 20 \ 35 \\ 05 \ | \ 01 \ 05 \ 15 \ 35 \ 70 \end{array}[/TEX]

    Schräg von links unten nach rechts oben erkennt man die Binomialkoeffizienten eines konstanten n, z.B. 1,4,6,4,1 für n=4 (4 über 0, 4 über 1, ... , 4 über 4). Die Sortenzahl müsste aber, damit die Tabelle symmetrisch wird, um 1 niedriger sein, man muss also mit S-1 arbeiten.
    Bei vorgegebenen Zahlen F und S landet man demnach in der (schrägen) Binomialkoeffizienten-Reihe von F + S-1 (obere Zahl) und die Zeile (Zählung bei 0 angefangen, also S-1) ergibt die untere Zahl, also:

    [TEX] \left( \begin{array}{c} F + S-1 \\ S-1 \end{array} \right)[/TEX]

    Für F=12 und S=3 demnach:

    [TEX] \left( \begin{array}{c} 14 \\ 2 \end{array} \right) = \frac{14 \cdot 13}{1 \cdot 2} = 91[/TEX]

    Die Aufgabe brachte mich auf die Idee, mal einige Kombinatorik-Formeln (Anzahl der Möglichkeiten) zusammenzustellen. Dabei wird öfter der Binomialkoeffizient "n über k"
    [TEX] \left( \begin{array}{c} n \\ k \end{array} \right) = \frac{n!}{k! \cdot (n-k)!} = \left( \begin{array}{c} n \\ n-k \end{array} \right)[/TEX]
    auftreten.

    1. mit Zurücklegen, d.h. die Grundmenge besteht aus k verschiedenen Elementen, die jeweils beliebig oft auftreten können (so wie in der Aufgabe) und es wird z-mal gezogen

    a) Reihenfolge beachten: [TEX]k^z[/TEX]

    b) Reihenfolge egal (so wie in der Aufgabe): [TEX] \left( \begin{array}{c} z+k-1 \\ k-1 \end{array} \right) = \left( \begin{array}{c} z+k-1 \\ z \end{array} \right) [/TEX]

    2. ohne Zurücklegen, d.h. die Grundmenge besteht aus einer festen Menge von n Elementen, in der es k verschiedene Elemente gibt (-> k [TEX]\le[/TEX] n). Das Element 1 kommt [TEX]a_1[/TEX]-mal vor, das Element 2 [TEX]a_2[/TEX]-mal, ... und das Element k [TEX]a_k[/TEX]-mal. Da die allgemeine Formel etwas unhandlich ist, notiere ich nur die Sonderfälle.

    2.1. alle Elemente verschieden ( k=n, alle [TEX]a_i[/TEX]=1 )

    a) Reihenfolge beachten: [TEX] \left( \begin{array}{c} k \\ z \end{array} \right) \cdot z! = \frac{k!}{(k-z)!} [/TEX]

    b) Reihenfolge egal: [TEX] \left( \begin{array}{c} k \\ z \end{array} \right) = \frac{k!}{z! \cdot (k-z)!} [/TEX]

    2.2. alle Elemente werden gezogen ( z=n )

    a) Reihenfolge beachten: [TEX] \frac{z!}{a_1 ! \cdot a_2 ! \cdot ... \cdot a_k !} [/TEX]

    b) Reihenfolge egal: 1

    2.3. es wird höchstens so oft gezogen, dass keines der verschiedenen Elemente fehlt ( [TEX]z \le \displaystyle\min_{1 \le i \le k}(a_i)[/TEX] ). Das ist wie "mit Zurücklegen".

    a) Reihenfolge beachten: [TEX]k^z[/TEX]

    b) Reihenfolge egal: [TEX] \left( \begin{array}{c} z+k-1 \\ k-1 \end{array} \right) = \left( \begin{array}{c} z+k-1 \\ z \end{array} \right) [/TEX]

    2.4. es gibt nur 2 verschiedene Elemente ( k=2, Annahme: [TEX]a_1 \le a_2[/TEX] )

    a) Reihenfolge beachten: [TEX] \displaystyle\sum\limits_{i=\max(0;z-a_2)}^{a_1} \left( \begin{array}{c} z \\ i \end{array} \right) [/TEX]

    b) Reihenfolge egal: min ( min([TEX]a_1[/TEX],[TEX]a_2[/TEX])+1 ; min(z,n-z)+1 )