Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen] Englische Flagge
Mathematik-Online-Lexikon: Erläuterung zu

Auswahl von Teilmengen

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Übersicht

Die folgende Tabelle gibt die Anzahl der Möglichkeiten an, aus einer Menge mit $ n$ verschiedenen Elementen $ k$ Elemente auszuwählen, wobei unterschieden werden muß, ob die Reihenfolge eine Rolle spielt (sortiert) und Wiederholungen zugelassen sind.

  sortiert nicht sortiert
mit Wiederholungen $ n^k$ $ \displaystyle \binom{n+k-1}{k}$
ohne Wiederholungen $ n(n-1)\cdots(n-k+1)$ $ \displaystyle \binom{n}{k}$

i)
unsortierte Auswahl ohne Wiederholungen

Berücksichtigt man die Reihenfolge, so gibt es $ n$ Möglichkeiten für das erste, $ (n-1)$ Möglichkeiten für das zweite, bis hin zu $ (n-k+1)$ Möglichkeiten für das $ k$-te Element, also insgesamt

$\displaystyle n(n-1)\cdots(n-k+1) $

Möglichkeiten. Diese Anzahl muß noch durch die Anzahl

$\displaystyle k! $

der Permutationen von $ k$ Elementen dividiert werden.

ii)
unsortierte Auswahl mit Wiederholungen

Ein äquivalentes Problem ist, $ n-1$ Markierungen zwischen $ n+k$ Punkten zu plazieren.

$ \bullet$ | $ \bullet$ | $ \bullet$ | $ \bullet$ | $ \bullet$ | $ \bullet$ | $ \bullet$ | $ \bullet$
          $ \vartriangle$   $ \vartriangle$       $ \vartriangle$   $ \vartriangle$  
Die um $ 1$ verminderte Anzahl der Punkte zwischen der $ (i-1)$-ten und $ i$-ten Markierung entspricht den Wiederholungen des $ i$-ten Elements. Nach i) ergibt sich für die Anzahl der möglichen Markierungen

$\displaystyle \binom{n+k-1}{n-1}\, , $

was mit der in der Tabelle angegebenen Zahl übereinstimmt.

iii)
Die Formeln für die sortierte Auswahl ergeben sich unmittelbar.
(Autoren: Höllig/Knesch)
[Zurück zur Aussage]
  automatisch erstellt am 11.  6. 2007