Kombinatorisches Zählen < Kombinatorik < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:50 Mo 28.04.2014 | | Autor: | Trikolon |
| Aufgabe | | Weshalb gibt es n über k Elemente, sodass [mm] \summe_{j=1}^{n}i_j=k [/mm] mit 0 [mm] \le [/mm] k [mm] \le [/mm] n und [mm] i_1,...,i_n \in [/mm] {0,1}? |
s.o.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:17 Mo 28.04.2014 | | Autor: | Marcel |
Hallo,
> Weshalb gibt es n über k Elemente, sodass
> [mm]\summe_{j=1}^{n}i_j=k[/mm] mit 0 [mm]\le[/mm] k [mm]\le[/mm] n und [mm]i_1,...,i_n \in[/mm]
> {0,1}?
> s.o.
nimm' denn Nullvektor aus dem [mm] $\IR^n\,.$
[/mm]
Bei diesem musst Du an [mm] $k\,$ [/mm] Stellen die Null durch eine Eins ersetzen, so
dass die Summe über die Komponenten des Vektors [mm] $k\,$ [/mm] ergibt.
Mach' Dir ein Beispiel mit [mm] $n=5\,$ [/mm] und lasse dann
[mm] $k=0,1,2,3,4,5\,,$
[/mm]
durchlaufen, also bspw. für [mm] $k=3\,:$
[/mm]
Hier müsstest Du bei
$(0,0,0,0,0)$
drei Stellen durch eine 1 ersetzen, d.h. die Frage wäre:
Wie viele Vektoren mit 5 Einträgen kann man mit
drei [mm] $1\,$en [/mm] und zwei [mm] $0\,$en
[/mm]
erstellen?
Du kannst mit diesem Verfahren aus
$(0,0,0,0,0)$
halt
${5 [mm] \choose [/mm] 3}$
solcher Vektoren erstellen...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:20 Mo 28.04.2014 | | Autor: | Sax |
Hi,
da nicht klar ist, was mit "Elemente" gemeint ist, formuliere ich die Frage mal so um :
"Wieso gibt es [mm] \vektor{n \\ k} [/mm] n-Tupel [mm] (i_1, [/mm] ..., [mm] i_n) [/mm] mit Einträgen aus {0;1}, so dass $ [mm] \summe_{j=1}^{n}i_j=k [/mm] $ ist ?"
Die Antwort hängt davon ab, wie [mm] \vektor{n \\ k} [/mm] definiert wurde.
Aus der kombinatorischen Definition [mm] "\vektor{n \\ k} [/mm] ist die Anzahl der k-elementigen Teilmengen einer n-elementigen Menge" folgt die Behauptung sofort, denn wenn [mm] \vektor{n \\ k} [/mm] die Anzahl der Möglichkeiten ist, k Objekte aus n Objekten auszuwählen, dann wähle man eben aus den n Stellen des Tupels k aus, besetze diese mit Einsen, den Rest mit Nullen, die Summe aller Einträge ist dann k und es gibt gerade [mm] \vektor{n \\ k} [/mm] Möglichkeiten für eine derartige Auswahl.
Wenn aber [mm] \vektor{n \\ k}=\bruch{n!}{k!*(n-k)!} [/mm] definiert wurde, so ist zu zeigen, dass die obige Anzahl auf diese Weise berechnet werden kann.
Das geschieht dadurch, dass man sich klar macht, dass es in dem Tupel für die erste Eins n mögliche Plätze gibt, für die zweite Eins noch (n-1) Plätze, ..., für die k-te Eins schließlich noch (n-k+1) Plätze. Das führt zunächst auf $ n*(n-1)* ... *(n-k+1) $ Möglichkeiten. Da aber die Einsen nicht unterscheidbar sind, muss dieses Produkt durch die Anzahl der Möglichkeiten, die es gibt, diese k Einsen anzuordnen (also durch k!) dividiert werden, um die gesuchte Anzahl zu erhalten. Damit ergibt sich der obige Ausdruck.
Gruß Sax.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:33 Mo 28.04.2014 | | Autor: | Marcel |
Hallo Sax,
> Hi,
>
> da nicht klar ist, was mit "Elemente" gemeint ist,
> formuliere ich die Frage mal so um :
>
> "Wieso gibt es [mm]\vektor{n \\ k}[/mm] n-Tupel [mm](i_1,[/mm] ..., [mm]i_n)[/mm] mit
> Einträgen aus {0;1}, so dass [mm]\summe_{j=1}^{n}i_j=k[/mm] ist ?"
>
> Die Antwort hängt davon ab, wie [mm]\vektor{n \\ k}[/mm] definiert
> wurde.
>
> Aus der kombinatorischen Definition [mm]"\vektor{n \\ k}[/mm] ist
> die Anzahl der k-elementigen Teilmengen einer n-elementigen
> Menge" folgt die Behauptung sofort, denn wenn [mm]\vektor{n \\ k}[/mm]
> die Anzahl der Möglichkeiten ist, k Objekte aus n Objekten
> auszuwählen, dann wähle man eben aus den n Stellen des
> Tupels k aus, besetze diese mit Einsen, den Rest mit
> Nullen, die Summe aller Einträge ist dann k und es gibt
> gerade [mm]\vektor{n \\ k}[/mm] Möglichkeiten für eine derartige
> Auswahl.
>
> Wenn aber [mm]\vektor{n \\ k}=\bruch{n!}{k!*(n-k)!}[/mm] definiert
> wurde, so ist zu zeigen, dass die obige Anzahl auf diese
> Weise berechnet werden kann.
> Das geschieht dadurch, dass man sich klar macht, dass es
> in dem Tupel für die erste Eins n mögliche Plätze gibt,
> für die zweite Eins noch (n-1) Plätze, ..., für die k-te
> Eins schließlich noch (n-k+1) Plätze. Das führt
> zunächst auf [mm]n*(n-1)* ... *(n-k+1)[/mm] Möglichkeiten.
kleine Ergänzung: Man macht sich am Besten klar, dass
[mm] $n*(n-1)*...*(n-k+1)=\frac{n!}{(n-k)!}$
[/mm]
gilt.
(Wer mit dem Produktzeichen umgehen kann:
[mm] $n*(n-1)*...*(n-k+1)=\produkt_{m=1}^k (n-m+1)=\frac{\produkt_{m=1}^n (n+1-m)}{\produkt_{\ell=k+1}^n (n+1-\ell)}=\frac{\produkt_{m'=1}^n m'}{\produkt_{\ell'=1}^{n-k} \ell'}\,,$
[/mm]
wobei sich das letzte Gleichheitszeichen wegen der Kommutativität der
Multiplikation ergibt, genauer:
[mm] $\produkt_{m=1}^n (n+1-m)\;\;\;\;\stackrel{\text{klar}}{=}\;\;\;\;n*(n-1)*...*2*1\;\;\;\;\stackrel{\text{Komm. der Mult.}}{=}\;\;\;\;1*2*...*(n-1)*n$
[/mm]
und analog mit [mm] $n-k\,$ [/mm] anstatt [mm] $n\,.$)
[/mm]
> Da aber
> die Einsen nicht unterscheidbar sind, muss dieses Produkt
> durch die Anzahl der Möglichkeiten, die es gibt, diese k
> Einsen anzuordnen (also durch k!) dividiert werden, um die
> gesuchte Anzahl zu erhalten. Damit ergibt sich der obige
> Ausdruck.
Gruß,
Marcel
|
|
|
|
