Basic knowledge

Sample types




In a variation we draw k elements out of a set of n elements. The ordering in the resulting list of k elements is important.

Explanation
n: Number of objects in the set
k: Number of drawings = elements in the result list

If every element in the set can only be drawn once, then it is a variation without repetition (w/o-rep).
Formula:
Example:
A horse race with 10 horses takes place. How many possibilities are there for the first three places?
Solution:

Example with urn model:
A contest with 10 participants takes place. How many possibilities are there for the top 3?


If every element in the set can be drawn multiple times, then it is a variation with repetition (w-rep)
Formula:
Example:
How many possibilities are there to form a word with 5 letters from the alphabet?
Solution:

Example with urn model:
A 4-digit bike lock allows to set each digit to one of the values 0 to 9. How many possible codes exist?
In a combination we draw k elements out of a set of n elements. The ordering in the resulting subset of k elements is unimportant.

Explanation
n: Number of objects in the set
k: Number of drawings = elements in the result subset

If every element in the set can only be drawn once, then it is a combination without repetition (w/o-rep).

Formula:

Example:
Lotto 6/49: Count the number of possible outcomes!
Solution:


If every element in the set can be drawn multiple times, then it is a combination with repetition (w-rep)

Formula:

Example:
We draw 3 times out of an urn with 6 balls and return each time the ball drawn into the urn.
Solution:

Example with urn model
A fruit seller packs bags of 10 fruits from 4 different types of fruits as a special offer. How many differing bags of fruit are possible?

Solution:

n-1 is the number of separator sheets needed in order to separate in the ordered list of objects, e. g. AA|BBB|C|DDDDD the (here: 4) object classes. This is the reason for „n-1“ in the formula.

Special topics

Permutation is a special form of variation, where all n elemnts are drawn w/o repetition (n=k).

Example:
In a treasure hunt game all 5 stations have to be reached. The set of stations n is 5, thus k is 5 as well, since all stations have to be reached.
With Laplace probability, all events of an experiment have the same probability.
P(A) = Number of events which satisfy condition A = desired events
Number of all possible events possible events


Example:

How high is the probability to roll a 4 with a six-sided dice?
P({4}) = 1/6

How high ist he probability to roll a 3 or a 5 with a six-sided dice?
P({3, 5}) = 2/6

n! is read „n-factorial“.
Formula: n! = 1 ∙ 2 ∙…∙ n, n ∈

Example:
5! = 1 ∙ 2 ∙ 3 ∙ 4 ∙ 5

Special rule:
0! = 1

For n, k ∈ ∪ {0} with k ≤ n the binomial coefficient is defined as:

(The last rule holds only for k > 0.)
Example:


A few rules
Sum rule
There are n elements with property a and m elements with property b. The a and b properties cannot be taken or occur at the same time. Therefore, there are n+m possibilities to select one object with property a or b.
Example:
In a car rental company there are 3 small cars and 7 middle-sized cars. When you need to choose one of the cars, you have in total 3+7 possibilities to choose.
Product rule
If a problem can be divided into 2 subproblems which are executed one after another, and if there are n possibilities for the 1st subproblem and m possibilities for the 2nd subproblem, then there are n*m possibilities in total.

Example:
There are 3 routes from Gummersbach to Cologne and 4 routes from Cologne to Aachen. Then there are in total 3*4 = 12 possible routes from Gummersbach to Aachen.

Distributions

Ein Bernoulli-Experiment ist ein Zufallsexperiment, bei dem es nur zwei Ausgänge gibt: Ereignis A tritt ein oder nicht. Wird ein Bernoulli-Experiment n-mal hintereinander unter derselben Bedingung ausgeführt, so spricht man von einer Bernoulli-Kette der Länge n.

Das Eintreten des Ereignisses A wird oft als Erfolg oder Treffer, das Nichteintreten als Misserfolg bezeichnet. Die Wahrscheinlichkeit P(A) = p heißt deshalb auch Erfolgswahrscheinlichkeit oder Trefferwahrscheinlichkeit.

Beispiel
Bernoulli-Experiment: Wurf eines Würfels, A = Wurf der Augenzahl "Eins" mit P(A) = 1/6.
Bernoulli-Kette: n-maliger Wurf des Würfels und jeweils Beobachtung von A = Augenzahl "Eins". Die Wahrscheinlichkeit für A ist bei jedem Wurf gleich 1/6.

Binomialverteilung
Gegeben ist eine Bernoulli-Kette der Länge n. Bei jeder der n Durchführungen kann ein bestimmtes Ereignis A mit der Wahrscheinlichkeit p eintreten (und das Gegenereignis ¬A mit der Wahrscheinlichkeit q = 1-p). Man interessiert sich für X = Anzahl der Versuchsdurchführungen, bei denen A eintritt. X kann die Werte k = 0,1,2,…,n annehmen. Die Wahrscheinlichkeit, dass A genau k-mal eintritt ist:

Binomialverteilung Formel

Man nennt die Zufallsvariable X binomialverteilt und ihre Wahrscheinlichkeitsverteilung eine Binomialverteilung mit den Parametern n,p.

Eigenschaften der Binomialverteilung

Erwartungswert μ = E(X) = n*p

Varianz σ² = Var(X) = n*p*q = n*p*(1-p)

Weiterführende Informationen finden sich in "Teschl Mathematik für Informatiker Band 2, Auflage 3, Kapitel 28.2, Seite 306-312".

Formel wurde erzeugt mit Latex Formeleditor.

Hypergeometrische Verteilung
Gegeben ist eine Grundgesamtheit aus N Elementen, von denen M eine bestimmte Eigenschaft haben. Man entnimmt eine Stichprobe vom Umfang n (ohne Zurücklegen). Dann kann die Zufallsvariable X = Anzahl der Elemente in der Stichprobe mit der gewünschten Eigenschaft höchstens die Werte k = 0,1,2,…,n annehmen. Die Wahrscheinlichkeit, genau k Elemente mit der gewünschten Eigenschaft in der Stichprobe vorzufinden, ist

Hypergeometrische Verteilung Formel

(für k > M bzw. n - k > N - M ist P(X = k) = 0 nach Definition des Binomialkoeffizienten – wir können nicht mehr Elemente mit einer bestimmten Eigenschaft ziehen als vorhanden sind). Man nennt X hypergeometrisch verteilt und die dazugehörige Wahrscheinlichkeitsverteilung eine hypergeometrische Verteilung mit den Parametern n,M und N.

Eigenschaften der hypergeometrischen Verteilung

Erwartungswert μ = E(X) = Hypergeometrische Verteilung Erwartungswert Formel

Varianz σ² = Var(X) = Hypergeometrische Verteilung Varianz Formel

Weiterführende Informationen finden sich in "Teschl Mathematik für Informatiker Band 2, Auflage 3, Kapitel 28.1, Seite 303-306".

Formeln wurden erzeugt mit Latex Formeleditor.

Damit man die Binomialverteilung anwenden kann, muss zunächst ein Experiment mit genau zwei Ausgängen vorliegen (Treffer oder Misserfolg). Ferner muss ein Experiment n-mal gleichartig wiederholt werden. Die Binomialverteilung beantwortet mit P(X=k) dann die Frage, wie wahrscheinlich es ist, dass genau k = 0, …, n Treffer auftreten.

Beispiel: n-mal Würfeln ist zunächst ein n-mal wiederholtes Experiment mit je sechs Ausgängen. Die Binomialverteilung scheint also zunächst nicht anwendbar. Wenn aber die Frage lautet „Wie wahrscheinlich ist 2-mal „6“ in n=10 Würfen?“, dann werden die ursprünglich 6 Ausgänge auf 2 reduziert: Treffer = {„6“} und Misserfolg = {„1“, „2“, „3“, „4“, „5“}. Die Binomialverteilung ist auf diese Frage anwendbar.

NICHT anwendbar ist die Binomialverteilung z. B. auf Fragestellungen wie: „Wie wahrscheinlich ist es, dass ein zufällig gebildetes Wort mit 10 Großbuchstaben mit „AB“ beginnt?“, denn hier liegt kein Experiment mit zwei Ausgängen vor. Hier muss man mit anderen Methoden der Kombinatorik arbeiten.

Bei der Binomialverteilung müssen alle n Experimente gleichartig sein. Dies geht entweder, wenn durch „Ziehen mit Zurücklegen“ immer wieder die gleichen Bedingungen hergestellt werden, oder wenn die Reservoirs, aus denen gezogen wird, unendlich groß sind (Beispiel: ein Förderband in der Produktion).

Handelt es sich um „Ziehen ohne Zurücklegen“, dann gelangt man in den Bereich der hypergeometrischen Verteilung. Auch hier müssen wieder genau zwei Ausgänge (Treffer oder Misserfolg) vorliegen. Ein anderes Bild dafür ist, dass sich in einer Urne Kugeln von zwei Sorten befinden: Die einen haben eine bestimmte Eigenschaft (z.B. weiß zu sein), die anderen haben diese Eigenschaft nicht. Diese Kugeln werden nun ohne Zurücklegen gezogen.

Counting procedures

Für disjunkte Mengen gilt die Summenregel.

Für nicht-disjunkte Mengen wird das Inklusions-Exklusions-Prinzip benutzt. Dabei wird die Anzahl der Mengen summiert und die doppelten / N-mal vorkommenden Elemente werden einmal / (N -1)-mal entfernt.

Zwei Mengen
|A ∪ B| = |A| + |B| - |A ∩ B|
|A ∩ B| = |A| + |B| - |A ∪ B|

Drei Mengen
|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|
|A ∩ B ∩ C| = |A ∪ B ∪ C| - |A| - |B| - |C| + |A ∩ B| + |A ∩ C| + |B ∩ C|

(die jeweils untere Formel ergibt sich aus der jeweils oberen durch Termumstellung)