Kombinatorik

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Abzählende Kombinatorik[Bearbeiten]

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[Bearbeiten]

In einer Urne befinden sich Kugeln, aus der Elemente gezogen werden.
Allgemein bezeichnet die Zahl der vorhandenen Elemente und die Anzahl der Ziehungen bzw. die jeweiligen Anzahlen , wie oft mit Zurücklegen das Element gezogen wurde.

MIT Beachtung der Reihenfolge - MIT Zurücklegen[Bearbeiten]

Es werden -Tupel der Form gebildet. Verwendet man Kugeln mit Nummern von bis gilt:

mit

MIT Beachtung der Reihenfolge - OHNE Zurücklegen[Bearbeiten]

Es werden -Tupel der Form gebildet. Verwendet man Kugeln mit Nummern von bis gilt:

mit

OHNE Beachtung der Reihenfolge - OHNE Zurücklegen[Bearbeiten]

Es werden -elementige Teilmengen einer -elementige Grundmenge gebildet der Form gebildet. Verwendet man Kugeln mit Nummern von bis gilt:

mit

OHNE Beachtung der Reihenfolge - MIT Zurücklegen[Bearbeiten]

Es wird mit den für jedes der -elementigen Grundmenge gezählt, wie oft es gezogen wurde. Tupel für eine Grundmenge der Form besagt, dass dreimal gezogen wurde, viermal gezogen wurde und überhaupt nicht gezogen wurde. Verwendet man Kugeln mit Nummern von bis gilt:

mit

Beispiel: Trennstellen ziehen[Bearbeiten]

  • Man betrachtet nun eine Grundmenge mit Elementen.
  • Da es nicht auf die Reihenfolge ankommt, werden die gezogenen Elemente mit gleichem Buchstaben zusammengefasst, z.B. mit zu .
  • Nun erweitert man das Tupel um Trennstellen z.B. .
  • Positionen der Trennstellen werden mit Nummer belegt und z.B. die Trennstellen gezogen.

Ersatzmodell: Trennstellen ziehen[Bearbeiten]

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

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

Urnenmodelle[Bearbeiten]

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

Modell[Bearbeiten]

In einer Urne mit Kugelnseine schwarze und weiße Kugeln. Es werden Kugeln ohne Zurücklegen gezogen. Bezeichne k die Anzahl der schwarzen unter den gezogenen (), das Ereignis, dass die Anzahl der schwarzen genau gleich ist und die Wahrscheinlichkeit für das Ereignis . Die Wahrscheinlichkeitsfunktion definiert die sogenannte hypergeometrische Verteilung mit Paramtern auf .

Satz[Bearbeiten]

Für und gilt:

Beweis (1)[Bearbeiten]

Sei die Menge aller ungeordneten Stichproben aus der Menge ohne Wiederholung, sei die Gleichverteilung auf . Es ist . Die schwarzen Kugeln seien mit den Nummern versehen, die weißen Kugeln mit . Das Ereignis besteht dann aus allen mit genau Elementen aus .

Heuristisch: Es gibt Möglichkeiten, Kugeln aus schwarzen Möglichkeiten, Kugeln aus weißen] ohne Zurüklegen zu ziehen.

Beweis (2)[Bearbeiten]

Jede Kombination einer der Möglichkeiten mit einer der Möglichkeiten ergibt genau ein Element aus . Folglich und wie behauptet.

Bemerkung[Bearbeiten]

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

Qualitätskontrolle (Beispiel)[Bearbeiten]

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

oder

Skatspiel (Beispiel)[Bearbeiten]

Wie groß ist die Wahrscheinlichkeit, dass beim Austeilen der Karten der Spieler unter seinen Karten genau der Asse besitzt?

Zufallsgrößen, Zufallsvariablen (1)[Bearbeiten]

In 2.2.1 traten zwei Wahrscheinlichkeitsräume auf:

  • ist die Menge der ungeordneten Stichproben vom Umfang aus (ohne Wiederholung), ist Gleichverteilung auf .
  • hypergeometrische Verteilung (Anzahl schwarzer Kugeln hypergeometrisch verteilt). Wir bezeichnen diese Anzahl als . ist eine Abbildung von .

Zufallsgrößen, Zufallsvariablen (2)[Bearbeiten]

Das in 2.2.1 auftretende Ereignis können wir so schreiben:

('Urbild der Menge )

Durch die Definition

erhalten wir eine Wahrscheinlichkeitsfunktion auf (im Beispiel gerade hypergeometrische Verteilung).

Für beliebige Ereignisse setzt man in Verallgemeinerung der letzten Gleichung

Bild (Definition)[Bearbeiten]

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

a) eine Abbildung heißt Zufallsgröße (oder zufällige Größe).

b) Die durch , , definierte Abbildung von in heißt Bild von unter :

und

Diskreter Wahrscheinlichkeitsraum (Satz)[Bearbeiten]

Mit dem in b) definierten gilt: bildet einen diskreten Wahrscheinlichkeitsraum.

Beweis (1)[Bearbeiten]

Es ist zu zeigen, dass eine Wahrscheinlichkeitsverteilung über ist. (trivial)

i) Normierung:

ii) - Additivität: Für eine Folge von paarweise disjunkten Mengen aus sind die Urbildmengen wieder paarweise disjunkt:


Beweis (2)[Bearbeiten]

Ferner gilt:


Dann folgt:



Wahrscheinlichkeitsverteilung (Definition)[Bearbeiten]

Die durch definierte Wahrscheinlichkeitsverteilung auf heißt Wahrscheinlichkeitsverteilung von und wird mit bezeichnet. heißt auf -verteilt.

Bemerkungen und Bezeichnungen (1)[Bearbeiten]

1) schreibt man auch ("Ereignis in "). Entsprechend schreibt man statt auch ("Wahrscheinlichkeit, dass in ist").

2) Die zu gehörende Wahrscheinlichkeitsfunktion auf lautet .

3) Zu jedem Wahrscheinlichkeitsraum gibt es die Zufallsgröße . in diesem Fall ist .

Bemerkungen und Bezeichnungen (2)[Bearbeiten]

4) Im Fall (z.B. o.ä.) spricht man auch von einer Zufallsvariablen (statt Zufallsgröße). Beachte, dass diese eine schiefe (aber eingebürgerte) bezeichnung ist: ist die Variable, die Funktion. Im Fall spricht man von einem Zufallsvektor.

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

Beispiel[Bearbeiten]

-maliges Würfeln. Auf , Gleichverteilung auf , definiere durch ("Anzahl Sechser").

Behauptung:

Binomialverteilung (Definition)[Bearbeiten]

Die Wahrscheinlichkeitsverteilung auf definiert durch

heißt Binomialverteilung mit den Parametern und , kurz -Verteilung (). Die im Beispiel angegebene Zufallsvariable ist also -verteilt.

Indikatorvariablen (Beispiel)[Bearbeiten]

Sei . Die Zufallsvariable ,

heißt Indikatorvariable von . Umgekehrt stellt jede -wertige Zufallsvariable eine Indikatorvariable dar, nämlich

Sei eine Wahrscheinlichkeitsverteilung auf gegeben und setze . Dann ist die Verteilung von gegeben durch . heißt bernoulliverteilt mit Paramter p, kurz -verteilt.

Rechenregeln[Bearbeiten]

Für Indikatorvariablen:


Die nun folgenden Erläuterungen beziehen sich auf den Fall von mehreren, aber auf dem gleichen Wahrscheinlichkeitsraum definierten Zufallsvariablen.

Gemeinsame Verteilung (Definition) (1)[Bearbeiten]

Gegeben Zufallsvariablen .

Sei der aus ihnen gegildete Zufallsvektor. Dann heißt die Verteilung auch gemeinsame Verteilung der heißt auch i-te Rand- oder Marginalverteilung.
Die Randverteilung lässt sich aus der gemeinsamen Verteilung wie folgt berechnen. Sei . Setze

Gemeinsame Verteilung (Definition) (2)[Bearbeiten]

Dann ist


Beispiel (1)[Bearbeiten]

Werfen zweier (unterschiedbarer) Würfel. Setze und definiere die Zufallsvariablen gemäß

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

Beispiel (2)[Bearbeiten]

Hier ist und die gemeinsamer Verteilung der auf ist

für alle .

Die Randverteilung von erhalten wir aus der letzten Gleichung der Definition wie folgt:

Siehe auch[Bearbeiten]

Seiten-Information[Bearbeiten]

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

Quellen[Bearbeiten]

  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)