Abzählende KombinatorikBearbeiten

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 NotationBearbeiten

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ücklegenBearbeiten

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

  mit  

MIT Beachtung der Reihenfolge - OHNE ZurücklegenBearbeiten

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

  mit  

OHNE Beachtung der Reihenfolge - OHNE ZurücklegenBearbeiten

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ücklegenBearbeiten

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 ziehenBearbeiten

  • 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 ziehenBearbeiten

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.

UrnenmodelleBearbeiten

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.

ModellBearbeiten

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  .

SatzBearbeiten

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.

BemerkungBearbeiten

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:

  •  
  •  
  •  
  •  

BeispielBearbeiten

 -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.

RechenregelnBearbeiten

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 auchBearbeiten

Seiten-InformationBearbeiten

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

QuellenBearbeiten

  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)