Binomialzahlen: ungeordnete Auswahl mit Wiederholung

02.10.2008, 22:39

saimen

Binomialzahlen: ungeordnete Auswahl mit Wiederholung

Bei meiner GFS habe ich beim Beweis folgenden Satzes eine Verständnisfrage.

Zitat:

Die Anzahl der ungeordneten Auswahlen mit Wiederholung von k Objekten aus einer Menge von n Objekten ist
$\begin{eqnarray*} \begin{pmatrix} n+k-1 \\ k \end{pmatrix} \end{eqnarray*}$
Beweis: Wir konstruieren eine eindeutige Zuordnung zwischen der Menge aller ungeordneten Auswahlen, die wir betrachten, und der Menge aller binären (n+k-1)-Tupel mit genau k Einsen. Da die Anzahl dieser (n+k-1)-Tupel mit genau k Einsen gleich $\begin{eqnarray*} \begin{pmatrix} n+k-1 \\ k \end{pmatrix} \end{eqnarray*}$ ist, ist damit die Behauptung bewiesen.

Die Zuordnung, die anschließend erläutert wird, verstehe ich, aber wieso ist die Anzahl der (n+k-1)-Tupel mit genau k Einsen gleich
$\begin{eqnarray*} \begin{pmatrix} n+k-1 \\ k \end{pmatrix} \end{eqnarray*}$
???
Vielen Dank schonmal im Vorraus smile

02.10.2008, 23:45

Auf diesen Beitrag antworten »

Ist wohl zu offensichtlich, um es zu erkennen:

Das Tupel hat $\begin{eqnarray*} n+k-1 \end{eqnarray*}$ Positionen, von denen man $\begin{eqnarray*} k \end{eqnarray*}$ auswählen kann als diejenigen Positionen, wo die Einsen stehem sollen. Die Einsen sind nicht unterscheidbar, also ist dies eine ungeordnete Auswahl der Einserpositionen aus der Menge aller Positionen ... muss ich noch weiter reden?

02.10.2008, 23:54

saimen

Auf diesen Beitrag antworten »

ok da stand ich wohl aufm schlauch
danke für die schnelle antwort.

23.08.2010, 19:31

MJR

Auf diesen Beitrag antworten »

Dieser Thread ist schon recht alt, allerdings habe ich noch eine Bitte.
Könnte jemand nochmal genauer erläutern was AD meint?
Ich danke euch schon mal jetzt smile

23.08.2010, 20:30

wisili

Auf diesen Beitrag antworten »

Ich probiere es mit einem Beispiel:
Die Menge {a, b, c} hat n=3 Elemente.
Ich wähle mit Wiederholungen z.B. k=5 Elemente aus, etwa (a b b c c).
(Man darf nämlich jedes ungeordnete Tupel durchaus alphabetisch ordnen.)

Nun macht man einen Codierungstrick*: Statt des 5-Tupels (a b b c c)
schreibt man (1011011): Die Einsenblöcke stehen für die Elemente, alphabetisch, und die Nullen figurieren als Trennzeichen. Es braucht immer n-1 Trennzeichen, hier also 2. Das so definierte binäre Tupel hat die Länge k+n-1, hier 5+3-1=7. Das Tupel steht fest, wenn die Plätze der n-1 Nullen innerhalb des n+k-1-Tupels festgelegt sind. Das geht auf n+k-1 über k Arten, hier 7 über 5 = 21.

(* bezieht sich auf den oben im Erstbeitrag erwähnten Hinweis:
«Wir konstruieren eine eindeutige Zuordnung zwischen der Menge aller ungeordneten Auswahlen, die wir betrachten, und der Menge aller binären (n+k-1)-Tupel mit genau k Einsen.»)

Neue Frage »

Antworten »

Binomialzahlen: ungeordnete Auswahl mit Wiederholung

Verwandte Themen