====== Zählstrategien (Kombinatorik) ======

Zählstrategien werden dann hilfreich, wenn ein Zufallsexperiment mehr Ergebnisse hat als man auf den ersten Blick abzählen kann. Gerade bei Laplace-Experimenten kann man mit diesen Strategien die Anzahl aller Ergebnisse und die Anzahl der günstigen Ergebnisse vergleichsweise einfach bestimmen.

Grundsätzlich sind beim Zählen zwei Fragen zu beantworten: Muss die Reihenfolge beachtet werden? Können Ergebnisse mehrmals auftreten?

Die Formeln der Zählstrategien kann man sich gut mit Hilfe eines Baumdiagramms veranschaulichen.

=== Allgemeines Zählprinzip ===

Um die Anzahl der Pfade eines Baumes zu berechnen multipliziert man die Anzahl der Verzweigungen auf jeder Stufe.

Hat man z.B. einen Baum mit n Verzweigungen auf jeder Stufe und k Stufen, dann ist die Gesamtzahl aller möglichen Ergebnisse <m>n^k</m>. Bei 6 Verzweigungen auf jeder Stufe und 5 Stufen wären das also 7776 Pfade.

=== Ziehen mit Wiederholung  ===

z.B. Würfeln oder Ziehen mit Zurücklegen (n unterscheidbare Kugeln), **unter Beachtung der Reihenfolge**. Es handelt sich hier um //Variationen//, bei denen die einzelnen Elemente beliebig oft vorkommen können.

Der Baum hat auf jeder Stufe gleich viele Verzweigungen und jedes Ergebnis hat die gleiche Wahrscheinlichkeit. Jedes einzelne Ereignis (= jeder Pfad) hat dann die Wahrscheinlichkeit <m>1/n^k</m>, 

mit n=6 und k=5 also 1/7776.

=== Ziehen ohne Wiederholung ===

z.B. Ziehen ohne Zurücklegen (n unterscheidbare Kugeln), **unter Beachtung der Reihenfolge**

Der Baum hat auf jeder Stufe gleich viele Verzweigungen, die Wahrscheinlichkeiten der Ergebnisse sind auf der Stufe gleich, ändern sich aber mit jeder Stufe.

Die **Anzahl** der Pfade ist dann <m>n~*~(n-1)~*~(n-2)~*~cdots~*~(n-k+1)</m>, weil auf jeder Stufe eine Kugel weniger in der Urne ist - damit ist auch klar, dass k nicht größer als n sein kann.

Ist k = n so nennt man die möglichen Anordnungen //Permutationen//, ist k < n //Variationen//.((Im Englischen werden Variationen auch Permutatioenen genannt.))

Diesen Ausdruck kann man mit Hilfe der Fakultät (Zeichen: !) einfacher notieren: 

<m>{n!}/{(n-k)!}~=~{n~*~(n-1)~*~(n-2)~*~cdots~*~(n-k+1)~*~(n-k)~*~(n-k-1)~*~cdots~*~2~*~1}/{(n-k)~*~(n-k-1)~*~(n-k-2)~*~cdots~*~2~*~1}</m>

<m>~~~~~=~n~*~(n-1)~*~(n-2)~*~cdots~*~(n-k+1)</m> = **n [nPr] k** (Taschenrechner), 

mit n=6 und k=5 also 6*5*4*3*2 = [6 nPr 5] = 720.

Die Wahrscheinlichkeit jedes einzelnen Pfades ist dann wieder der Kehrwert der Anzahl, also (n-k)!/n! = 1/(n [nPr] k), im Beispiel also 1/720.

=== Ziehen mit einem Griff ===

Ziehen mit einem Griff ist wieder Ziehen ohne Zurücklegen, diesmal aber **ohne Beachtung der Reihenfolge**. Ein Beispiel dafür wäre die Lottoziehung, bei der am Ende die Zahlen der Größe nach sortiert werden. Die möglichen Anordnungen nennt man hier //Kombinationen//.

Die **Anzahl** der möglichen Pfade ist wie beim Ziehen mit Wiederholung n!/(n-k)!, die Anzahl der unterscheidbaren Ereignisse ist aber geringer, da die erste Kugel auf jedem der k Plätze des Pfades auftauchen kann, die zweite noch auf k-1 Plätzen usw. - jeder Ereignis kommt also <m>k~*~(k-1)~*~(k-2)~*~cdots~*~2~*~1~=~k!</m> mal vor.

Für die Ereignisanzahl muss man nun also noch die Ergebnisanzahl durch die Häufigkeit der Ereignisse teilen, also <m>{n!}/{(n-k)!} ~:~ k! ~=~ {n!}/{k!(n-k)!} ~=~ (matrix{2}{1}{n k})</m>. Diesen Ausdruck nennt man auch den Binomialkoeffizienten, der Taschenrechner hat dafür die Taste **[nCr]**.

{{tag>mathpublisher}}