Kombinatorik

Abzählende Kombinatorik

Die abzählende Kombinatorik^[1] ist ein Teilbereich der Kombinatorik. Sie beschäftigt sich mit der Bestimmung der Anzahl möglicher Anordnungen oder Auswahlen.

(Zurücklegen) „mit“ bzw. „ohne“ Zurücklegen der gezogenen Objekte sowie
(Reihenfolge) „mit“ bzw. „ohne“ Beachtung ihrer Reihenfolge (d. h. „geordnet“ bzw. „ungeordnet“).

Zur Notation

In einer Urne befinden sich $n$ Kugeln, aus der Elemente gezogen werden.
Allgemein bezeichnet $n$ die Zahl der vorhandenen Elemente und $k$ die Anzahl der Ziehungen bzw. $k_{1},\ldots ,k_{n}$ die jeweiligen Anzahlen $k_{i}\in \mathbb {N} _{0}$ , wie oft mit Zurücklegen das Element $i\in \{1,\ldots ,n\}$ gezogen wurde.

MIT Beachtung der Reihenfolge - MIT Zurücklegen

Es werden $k$ -Tupel der Form $(a,b,c,a)$ gebildet. Verwendet man Kugeln mit Nummern von $1$ bis $n$ gilt:

\Omega _{1}:=\{1,\ldots ,n\}^{k}

mit

|\Omega _{1}|=n^{k}

MIT Beachtung der Reihenfolge - OHNE Zurücklegen

Es werden $k$ -Tupel der Form $(b,c,a)$ gebildet. Verwendet man Kugeln mit Nummern von $1$ bis $n$ gilt:

\Omega _{2}:=\{(\omega _{1},\ldots ,\omega _{k})\in \{1,\ldots ,n\}^{k}\,|\,\forall _{i,j\in \{1,\ldots ,n\},i\not =j}\,:\,\omega _{i}\not =\omega _{j}\}

mit

|\Omega _{2}|:={n \choose k}\cdot {k!}={\frac {n!}{\left(n-k\right)!}}

OHNE Beachtung der Reihenfolge - OHNE Zurücklegen

Es werden $k$ -elementige Teilmengen einer $n$ -elementige Grundmenge gebildet der Form $\{a,c,d\}$ gebildet. Verwendet man Kugeln mit Nummern von $1$ bis $n$ gilt:

\Omega _{3}:=\{A\subset \{1,\ldots ,n\}^{k}\,|\,|A|=k\}

mit

|\Omega _{3}|:={n \choose k}={\frac {n!}{k!\left(n-k\right)!}}

OHNE Beachtung der Reihenfolge - MIT Zurücklegen

Es wird mit den $k_{1},\ldots ,k_{n}$ für jedes der $n$ -elementigen Grundmenge gezählt, wie oft es gezogen wurde. Tupel $(0,3,2,0)$ für eine Grundmenge der Form $\{a,b,c,d\}$ besagt, dass $b$ dreimal gezogen wurde, $c$ viermal gezogen wurde und $a,d$ überhaupt nicht gezogen wurde. Verwendet man Kugeln mit Nummern von $1$ bis $n$ gilt:

\Omega _{4}:=\left\{(\omega _{1},\ldots ,\omega _{n})\in \mathbb {N} _{0}^{n}\,\left|\,\sum _{i=1}^{n}\omega _{i}=k\right.\right\}

mit

|\Omega _{4}|:={n-1+k \choose n-1}={\frac {(n-1+k)!}{k!\left(n-1\right)!}}

Beispiel: Trennstellen ziehen

Man betrachtet nun eine Grundmenge $M:=\{a,b,c,d\}$ mit $n=4$ Elementen.
Da es nicht auf die Reihenfolge ankommt, werden die gezogenen Elemente mit gleichem Buchstaben zusammengefasst, z.B. mit $k=10$ zu $(a,a,a,a,b,d,d,d,d,d)$ .
Nun erweitert man das Tupel um $n-1$ Trennstellen z.B. $(a,a,a,a,\Delta ,b,\Delta ,\Delta ,d,d,d,d,d)$ .
Positionen der Trennstellen werden mit Nummer belegt und z.B. die Trennstellen $\{5,7,8\}$ gezogen.

Ersatzmodell: Trennstellen ziehen

Bei $n$ Elementen aus der Grundmenge benötigt man $n-1$ Trennstellen. Mit $k$ Ziehungen wird aus einer Grundmenge von $n-1+k$ Trennstellenpositionen gezogen. Damit führt man die kombinatorischen Möglichkeiten auf ein bekanntes Modell OHNE Beachtung der Reihenfolge - OHNE Zurücklegen zurück.

{n-1+k \choose n-1}={n+k-1 \choose k}={\frac {\left(n+k-1\right)!}{\left(n-1\right)!\cdot k!}}

In der Literatur findet man oft den zweiten Binomialkoeffizient als Anzahl der Möglichkeiten. Für die Trennstellenherleitung wird der erste Binomalkoeffizient verwendet.

Urnenmodelle

Die hier dargestellten Begriffe lassen sich auch über Urnenmodelle beschreiben. In einer Urne befinden sich $n$ Kugeln, die mit $1,...,n$ numeriert sind. Eine geordnete Stichprobe $(a_{1},...,a_{r})$ mit [ohne] Wiederholung entsteht durch r-maliges Ziehen mit [ohne] Zurücklegen der Kugeln in die Urne, wobei die Reihenfolge beachtet wird.

Modell

In einer Urne mit $N=S+W$ Kugelnseine $S$ schwarze und $W$ weiße Kugeln. Es werden $n\leq N$ Kugeln ohne Zurücklegen gezogen. Bezeichne k die Anzahl der schwarzen unter den $n$ gezogenen ( $0\leq k\leq n$ ), $A_{k}$ das Ereignis, dass die Anzahl der schwarzen genau gleich $k$ ist und $h(k;n,N,S)$ die Wahrscheinlichkeit für das Ereignis $A_{k}$ . Die Wahrscheinlichkeitsfunktion $h(k;n,N,S),k=0,...,n$ definiert die sogenannte hypergeometrische Verteilung mit Paramtern $n,N,S$ auf $\Omega '=\lbrace 0,1,...,n\rbrace$ .

Satz

Für $n\leq N$ und $S\leq N$ gilt:

$h(k;n,N,S)={\frac {{\binom {S}{k}}{\binom {N-S}{n-k}}}{\binom {N}{n}}};k=0,...,n$

Beweis (1)

Sei $\Omega$ die Menge aller ungeordneten Stichproben $\lbrace a_{1},...,a_{n}\rbrace$ aus der Menge $\lbrace 1,...,N\rbrace$ ohne Wiederholung, $P$ sei die Gleichverteilung auf $\Omega$ . Es ist $|\Omega |=C_{N}^{n}={\binom {N}{n}}$ . Die $S$ schwarzen Kugeln seien mit den Nummern $1,...,S$ versehen, die $N-S=W$ weißen Kugeln mit $S+1,...,N$ . Das Ereignis $A_{k}\subset \Omega$ besteht dann aus allen $\lbrace a_{1},...,an\rbrace$ mit genau $k$ Elementen $a_{i}$ aus $\lbrace 1,...,S\rbrace$ .

Heuristisch: Es gibt ${\binom {S}{k}}$ Möglichkeiten, $k$ Kugeln aus $S$ schwarzen $[{\binom {N-S}{n-k}}$ Möglichkeiten, $n-k$ Kugeln aus $N-S$ weißen] ohne Zurüklegen zu ziehen.

Beweis (2)

Jede Kombination einer der ${\binom {s}{k}}$ Möglichkeiten mit einer der ${\binom {N-S}{n-k}}$ Möglichkeiten ergibt genau ein Element aus $A_{k}$ . Folglich $|A_{k}|={\binom {s}{k}}{\binom {N-S}{n-k}}$ und $P(A_{n})={\frac {|A_{k}|}{|\Omega |}}$ wie behauptet.

Bemerkung

Im Spezialfall $n=k=S$ (d.h. Anzahl der Züge gleich Anzahl der schwarzen Kugeln; alle schwarzen Kugeln werden gezogen) ist

h=(S;S,N,S)={\frac {1}{\binom {N}{S}}}.

Qualitätskontrolle (Beispiel)

Aus einer Sendung von $N=10000$ Glühbirnen, welche $S$ defekte enthalten möge, werden $n=100$ Stück (ohne Zurücklegen) entnommen un geprüft. Die Wahrscheinlichkeit, dass unter den $100$ Proben genau $k$ (höchstens $k$ ) defekt sind, ist

h(k;100,10000,S)

oder

\sum _{i=1}^{k}h(k;100,10000,S)

Skatspiel (Beispiel)

Wie groß ist die Wahrscheinlichkeit, dass beim Austeilen der $N=32$ Karten der Spieler $A$ unter seinen $n=10$ Karten genau $k=3[k=4]$ der $S=4$ Asse besitzt?

h(3;10,32,4)={\frac {{\binom {4}{3}}{\binom {28}{7}}}{\binom {32}{10}}}\approx 0,073\approx {\frac {1}{14}}

[h(4;10,32,4)={\frac {{\binom {4}{4}}{\binom {28}{6}}}{\binom {32}{10}}}=\approx 0,0058\approx {\frac {1}{172}}]

Zufallsgrößen, Zufallsvariablen (1)

In 2.2.1 traten zwei Wahrscheinlichkeitsräume auf:

$\Omega$ ist die Menge der ungeordneten Stichproben vom Umfang $n$ aus $\lbrace 1,...,X\rbrace$ (ohne Wiederholung), $P$ ist Gleichverteilung auf $\Omega$ .
$\Omega '=\lbrace 0,1,...,n\rbrace ,P'$ hypergeometrische Verteilung (Anzahl $k\in \Omega '$ schwarzer Kugeln hypergeometrisch verteilt). Wir bezeichnen diese Anzahl als $X$ . $X$ ist eine Abbildung von $w=\lbrace a_{1},...,a_{n}\rbrace \in \Omega :X:\Omega \to \Omega ',w\to X(w)=|w\cap \lbrace 1,...,S\rbrace |$ .

Zufallsgrößen, Zufallsvariablen (2)

Das in 2.2.1 auftretende Ereignis $A_{k}$ können wir so schreiben:

A_{k}=\lbrace w\in \Omega :X(w)=k\rbrace =X^{-1}\lbrace k\rbrace

('Urbild der Menge

\lbrace k\rbrace

)

Durch die Definition

P'(\lbrace k\rbrace )=P(\lbrace w:X(w)=k\rbrace )\approx P(X^{-1}\lbrace k\rbrace ),k\in \Omega

erhalten wir eine Wahrscheinlichkeitsfunktion auf $\Omega '$ (im Beispiel gerade hypergeometrische Verteilung).

Für beliebige Ereignisse $A'\in \Omega$ setzt man in Verallgemeinerung der letzten Gleichung

P'(A')=P(\lbrace w:X(w)\in A'\rbrace )=P(X^{-1}(A')).

Bild (Definition)

Sei $P$ eine Wahrscheinlichkeitsfunktion über $\Omega$ . $\Omega '$ sei eine weitere (nicht-leere) höchstens abzählbare Menge.

a) eine Abbildung $X:\Omega \to \Omega '$ heißt Zufallsgröße (oder zufällige Größe).

b) Die durch $P'(A')=P(X^{-1}(A'))$ , $A'\in \Omega '$ , definierte Abbildung von ${\mathcal {S}}(\Omega ')$ in $[0,1]$ heißt Bild von $P$ unter $X$ :

(\Omega ,{\mathcal {S}}(\Omega ),P)\to ^{X}(\Omega ',{\mathcal {S}}(\Omega '),P')

und

(\Omega ',{\mathcal {S}}(\Omega '),P')\to ^{X^{-1}}(\Omega ,{\mathcal {S}}(\Omega ),P)

Diskreter Wahrscheinlichkeitsraum (Satz)

Mit dem in b) definierten $P'$ gilt: $(\Omega ',{\mathcal {S}}(\Omega '),P')$ bildet einen diskreten Wahrscheinlichkeitsraum.

Beweis (1)

Es ist zu zeigen, dass $P'$ eine Wahrscheinlichkeitsverteilung über $\Omega '$ ist. $P'(A')\in [0,1]$ (trivial)

i) Normierung: $P'(\Omega ')=P(X^{-1}(\Omega '))=P(\Omega )=1$

ii) $\sigma$ - Additivität: Für eine Folge $A_{1}',A_{2}',...$ von paarweise disjunkten Mengen aus $\Omega '$ sind die Urbildmengen wieder paarweise disjunkt:

X^{-1}(A'_{i})\cap X^{-1}(A_{j}')=X^{-1}(A_{i}'\cap A_{j}')=\varnothing

Beweis (2)

Ferner gilt:

X^{-1}(\bigcup _{i}A_{i}')=\bigcup _{i}X^{-1}(A_{i}')

Dann folgt:

P'(\bigcup _{i=1}^{\infty }A_{i}')=P(X^{-1}(\bigcup _{i=1}^{\infty }A_{i}'))=P(\bigcup _{i=1}^{\infty }X^{-1}(A_{i}'))

=\sum _{i=1}^{\infty }P(X^{-1}(A_{i}'))=\sum _{i=1}^{\infty }P'(A_{i}')

Wahrscheinlichkeitsverteilung (Definition)

Die durch $P(A')=P(X^{-1}(A')),A'\in \Omega '$ definierte Wahrscheinlichkeitsverteilung $P'$ auf $\Omega '$ heißt Wahrscheinlichkeitsverteilung von $X$ und wird mit $P_{X}$ bezeichnet. $X$ heißt auf $P'$ -verteilt.

Bemerkungen und Bezeichnungen (1)

1) $X^{-1}(A')\equiv \lbrace w;X(w)\in A'\rbrace$ schreibt man auch $\lbrace A\in A'\rbrace$ ("Ereignis $X$ in $A'$ "). Entsprechend schreibt man statt $P_{X}(A')=P(X^{-1}(A'))$ auch $P(X\in A')$ ("Wahrscheinlichkeit, dass $X$ in $A'$ ist").

2) Die zu $P'\equiv P_{X}$ gehörende Wahrscheinlichkeitsfunktion auf $\Omega '$ lautet $w\to P_{X}(\lbrace w'\rbrace )=P(X=w')$ .

3) Zu jedem Wahrscheinlichkeitsraum $(\Omega ,{\mathcal {S}}(\Omega ),P)$ gibt es die Zufallsgröße $Id:\Omega \to \Omega ,w\to Id(w)=w$ . in diesem Fall ist $\Omega '=\Omega ,P'=P$ .

Bemerkungen und Bezeichnungen (2)

4) Im Fall $\Omega '\subset \mathbb {R}$ (z.B. $\Omega =\mathbb {R} _{+}$ o.ä.) spricht man auch von einer Zufallsvariablen (statt Zufallsgröße). Beachte, dass diese eine schiefe (aber eingebürgerte) bezeichnung ist: $w$ ist die Variable, $X:\Omega \to \mathbb {R}$ die Funktion. Im Fall $\Omega \subset \mathbb {R} ^{k}$ spricht man von einem Zufallsvektor.

5) Da Zufallsvariablen reellwertige Funktionen sind, kann man mit ihnen üblicherweise Rechnen:

$(X+Y)(w)=X(w)+Y(w)$
$(X\cdot Y)(w)=X(w)\cdot Y(w)$
$(e^{X})(w)=e^{X(w)}$
$|X|(w)=|X(w)|$

Beispiel

$n$ -maliges Würfeln. Auf $(\Omega ,{\mathcal {S}}(\Omega ),P)$ , $\Omega ={\lbrace 1,...,6\rbrace }^{n}=\lbrace (a_{1},...,a_{n}):a_{i}\in \lbrace 1,...,6\rbrace \rbrace ,P$ Gleichverteilung auf $\Omega$ , definiere $X:\Omega \to \Omega '=\lbrace 0,...,n\rbrace$ durch $X(w)=|\lbrace i\in \lbrace 1,...,n\rbrace :a_{i}=6\rbrace |$ ("Anzahl Sechser").

Behauptung: $P_{X}(\lbrace k\rbrace )\equiv P(X-k)={\binom {n}{k}}({\frac {1}{6}})^{k}({\frac {5}{6}})^{n-k},k=0,...,n$

Binomialverteilung (Definition)

Die Wahrscheinlichkeitsverteilung auf $\lbrace 1,...,n\rbrace$ definiert durch

P_{k}={\binom {n}{k}}p^{k}\cdot (1-p)^{n-k},k=0,...,n

heißt Binomialverteilung mit den Parametern $n$ und $p$ , kurz $B(n,p)$ -Verteilung ( $0\leq p\leq 1$ ). Die im Beispiel angegebene Zufallsvariable $X$ ist also $B(n,{\frac {1}{6}})$ -verteilt.

Indikatorvariablen (Beispiel)

Sei $A\subset \Omega$ . Die Zufallsvariable $1_{A}:\Omega \to \lbrace 0,1\rbrace$ ,

1_{A}(w)=\left\{{\begin{array}{ll}1,&w\in A\\0,&w\notin A\end{array}}\right.

heißt Indikatorvariable von $A$ . Umgekehrt stellt jede $\lbrace 0,1\rbrace$ -wertige Zufallsvariable $X$ eine Indikatorvariable $1_{A}$ dar, nämlich

A=\lbrace w\in \Omega :X(w)=1\rbrace =\lbrace X=1\rbrace .

Sei eine Wahrscheinlichkeitsverteilung $P$ auf $\Omega$ gegeben und setze $p=P(A)$ . Dann ist die Verteilung von $X=1_{A}$ gegeben durch $P(X-1)=p,P(X=0)=1-p$ . $X$ heißt bernoulliverteilt mit Paramter p, kurz $B(1,p)$ -verteilt.

Rechenregeln

Für Indikatorvariablen:

$1_{A\cap B}=1_{A}\cdot 1_{B}$
$1_{A\cup B}=1_{A}+1_{B}+1_{A\cap B}$
$1_{\bar {A}}=1-1_{A},(1=1_{\Omega })$

Die nun folgenden Erläuterungen beziehen sich auf den Fall von mehreren, aber auf dem gleichen Wahrscheinlichkeitsraum $(\Omega ,{\mathcal {S}}(\Omega ),P)$ definierten Zufallsvariablen.

Gemeinsame Verteilung (Definition) (1)

Gegeben $k$ Zufallsvariablen $X_{1},...X_{k},X_{i}:\Omega \to \Omega _{i}'\subset \mathbb {R}$ .

Sei $X=(X_{1},...,X_{k}):\Omega \to \Omega '=\Omega _{1}1'\times ...\times \Omega _{k}'\subset \mathbb {R} ^{k}$ der aus ihnen gegildete Zufallsvektor. Dann heißt die Verteilung $P_{X}=P_{(X_{1},...,X_{k})}$ auch gemeinsame Verteilung der $X_{1},...,X_{k};P_{X_{i}}$ heißt auch i-te Rand- oder Marginalverteilung.
Die Randverteilung $P_{X_{i}}$ lässt sich aus der gemeinsamen Verteilung $P_{X}$ wie folgt berechnen. Sei $A_{i}'\subset \Omega '_{i}$ . Setze

A'=\Omega '_{1}\times ...\times \Omega '_{i-1}\times A'_{i}\times \Omega '_{i+1}\times ...\times \Omega _{k}'.

Gemeinsame Verteilung (Definition) (2)

Dann ist

X^{-1}(A')=\lbrace w:X_{1}(w)\in \Omega _{1}',...,X_{i}(w)\in A_{i}',...,X_{k}(w)\in \Omega _{k}'\rbrace

=\lbrace w:X_{i}(w)\in A_{i}'\rbrace =X_{i}^{-1}(A_{i}')

P_{X_{i}}(A'_{i})=P(X_{i}^{-1}(A_{i}'))=P(X^{-1}(A'))=P_{X}(A')

Beispiel (1)

Werfen zweier (unterschiedbarer) Würfel. Setze $\Omega =\lbrace 1,...,6\rbrace ^{2},w=\lbrace j,k\rbrace \in \Omega ,1\leq j,k\leq 6$ und definiere die Zufallsvariablen $X_{i}:\Omega \to \Omega '_{i}=\lbrace 1,...,6\rbrace ,i=1,2$ gemäß

X_{1}=((j,k))=j[X_{2}=((j,k))=k]

die Augenzahl des 1. [2.] Würfels.

Beispiel (2)

Hier ist $\Omega '=\Omega _{1}'\times \Omega '_{2}=\Omega$ und die gemeinsamer Verteilung der $X_{1},X_{2}$ auf $\Omega '$ ist

P_{(X_{1},X_{2})}(\lbrace (j,k)\rbrace )={\frac {1}{|\Omega '|}}={\frac {1}{36}}

für alle

j,k=1,...,6

.

Die Randverteilung von $X_{1}$ erhalten wir aus der letzten Gleichung der Definition wie folgt:

P_{X_{1}}(\lbrace j\rbrace =P_{(X_{1},X_{2})}(\lbrace j\rbrace \times \lbrace 1,...,6\rbrace )=\sum _{k=1}^{6}P_{(X_{1},X_{2})}(\lbrace (j,k)\rbrace )={\frac {6}{36}}={\frac {1}{6}}

Siehe auch

Multimengen
k-Tupel
Permutation
Mengen k-elementige Teilmengen
Variationen und Kombinationen

Seiten-Information

Der Foliensatz für diese Seite wurde auf Basis der folgenden Wikipedia-Quelle erstellt:

Abzählende Kombinatorik https://de.wikipedia.org/wiki/Abz%C3%A4hlende%20Kombinatorik
Datum: 5.11.2018
Wikipedia2Wikiversity-Konverter: https://niebert.github.com/Wikipedia2Wikiversity
Wiki2Reveal Link-Generator
Dieser Foliensatz gehört zum Kurs:Stochastik

Quellen

↑ „Abzählende Kombinatorik“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 6. Oktober 2018, 05:03 UTC. URL: https://de.wikipedia.org/w/index.php?title=Abz%C3%A4hlende_Kombinatorik&oldid=181538699 (Abgerufen: 5. November 2018, 15:27 UTC)

This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] „Abzählende Kombinatorik“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 6. Oktober 2018, 05:03 UTC. URL: https://de.wikipedia.org/w/index.php?title=Abz%C3%A4hlende_Kombinatorik&oldid=181538699 (Abgerufen: 5. November 2018, 15:27 UTC)