www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Kombinatorik" - Kombinatorisches Zählen
Kombinatorisches Zählen < Kombinatorik < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Kombinatorisches Zählen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

        
Bezug
Kombinatorisches Zählen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
        
Bezug
Kombinatorisches Zählen: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
                
Bezug
Kombinatorisches Zählen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]