matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Hochschulmathe
  Status Uni-Analysis
    Status Reelle Analysis
    Status UKomplx
    Status Uni-Kompl. Analysis
    Status Differentialgl.
    Status Maß/Integrat-Theorie
    Status Funktionalanalysis
    Status Transformationen
    Status UAnaSon
  Status Uni-Lin. Algebra
    Status Abbildungen
    Status ULinAGS
    Status Matrizen
    Status Determinanten
    Status Eigenwerte
    Status Skalarprodukte
    Status Moduln/Vektorraum
    Status Sonstiges
  Status Algebra+Zahlentheo.
    Status Algebra
    Status Zahlentheorie
  Status Diskrete Mathematik
    Status Diskrete Optimierung
    Status Graphentheorie
    Status Operations Research
    Status Relationen
  Status Fachdidaktik
  Status Finanz+Versicherung
    Status Uni-Finanzmathematik
    Status Uni-Versicherungsmat
  Status Logik+Mengenlehre
    Status Logik
    Status Mengenlehre
  Status Numerik
    Status Lin. Gleich.-systeme
    Status Nichtlineare Gleich.
    Status Interpol.+Approx.
    Status Integr.+Differenz.
    Status Eigenwertprobleme
    Status DGL
  Status Uni-Stochastik
    Status Kombinatorik
    Status math. Statistik
    Status Statistik (Anwend.)
    Status stoch. Analysis
    Status stoch. Prozesse
    Status Wahrscheinlichkeitstheorie
  Status Topologie+Geometrie
  Status Uni-Sonstiges

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
StartseiteMatheForenDiskrete MathematikDoppelte Abzählen
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Diskrete Mathematik" - Doppelte Abzählen
Doppelte Abzählen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Doppelte Abzählen: Frage zur Lösung
Status: (Frage) beantwortet Status 
Datum: 19:53 Mo 21.02.2011
Autor: hilado

Aufgabe
Zeigen Sie mit der Regel vom doppelten Abzählen, dass für positive ganze Zahlen n >= k >= 1 die folgende Identität gilt:

k * [mm] \vektor{n \\ k} [/mm] = n * [mm] \vektor{n - 1 \\ k - 1 } [/mm]

Hinweis: Die angegebenen Zahlgrößen, sagen wir [mm] a_{n, k} [/mm] beschreiben die Anzahl k-elementiger Teilmengen einer n-elementigen Menge, wobei eines der k Elemente gesondert ausgezeichneten ist. Beispiel: Für n = 3, k = 2 sind dies die Mengen

[mm] \{1*, 2 \}, \{1, 2* \}, [/mm]
[mm] \{1*, 3 \}, \{1, 3* \}, [/mm]
[mm] \{2*, 3 \}, \{2, 3* \}, [/mm]

wobei * das ausgezeichnete Element kennzeichnet. Also ist [mm] a_{3, 2} [/mm] = 6.

Also, ich hab die Lösung hier stehen, doch leider verstehe ich diese nicht ganz:

Paar bestehend aus einer Menge und einem darin ausgezeichneten Element, können wir auf zwei Weisen abzählen:

* Wir wählen die Teilmenge und zeichnen darin eines der Elemente aus:

[mm] a_{n, k} [/mm] = [mm] \vektor{n \\ k }*k [/mm]

Frage: Wie begründe ich das k an dieser Stelle? Warum gerade k?

* Wir wählen das Element, das als ausgezeichnetes auftreten soll, und ergänzen aus den verbleibenden n - 1 Elementen zu einer k-Teilmenge:

[mm] a_{n, k} [/mm] = n * [mm] \vektor{n - 1 \\ k - 1}. [/mm]

Das kann ich schon eher nachvollziehen. Wenn wir eine Menge haben [mm] \{ n_{1}, n_{2}, ..., n_{k} \} (n_{k} [/mm] ist dabei das ausgezeichnete Element), dann kann ich das für jedes Element so schreiben:

[mm] \{ n_{k} \} \cup \{n_{1}, n_{2}, ..., n_{n-1} \} [/mm]

Da wir [mm] n_{k} [/mm] aus der Teilmenge k-ter Ordnung rausgenommen haben, müssen wir nur noch die Teilmengen k-1-ter Ordnung der Menge n-1 zählen.



Nach der Regel vom doppelten Abzählen erhalten wir:

k * [mm] \vektor{n \\ k} [/mm] = n * [mm] \vektor{n - 1 \\ k - 1} [/mm]



        
Bezug
Doppelte Abzählen: Antwort
Status: (Antwort) fertig Status 
Datum: 19:59 Mo 21.02.2011
Autor: kamaleonti

Hallo,
> Zeigen Sie mit der Regel vom doppelten Abzählen, dass für
> positive ganze Zahlen n >= k >= 1 die folgende Identität
> gilt:
>  
> k * [mm]\vektor{n \\ k}[/mm] = n * [mm]\vektor{n - 1 \\ k - 1 }[/mm]
>  
> Hinweis: Die angegebenen Zahlgrößen, sagen wir [mm]a_{n, k}[/mm]
> beschreiben die Anzahl k-elementiger Teilmengen einer
> n-elementigen Menge, wobei eines der k Elemente gesondert
> ausgezeichneten ist. Beispiel: Für n = 3, k = 2 sind dies
> die Mengen
>  
> [mm]\{1*, 2 \}, \{1, 2* \},[/mm]
>  [mm]\{1*, 3 \}, \{1, 3* \},[/mm]
>  [mm]\{2*, 3 \}, \{2, 3* \},[/mm]
>  
> wobei * das ausgezeichnete Element kennzeichnet. Also ist
> [mm]a_{3, 2}[/mm] = 6.
>  Also, ich hab die Lösung hier stehen, doch leider
> verstehe ich diese nicht ganz:
>  
> Paar bestehend aus einer Menge und einem darin
> ausgezeichneten Element, können wir auf zwei Weisen
> abzählen:
>  
> * Wir wählen die Teilmenge und zeichnen darin eines der
> Elemente aus:
>  
> [mm]a_{n, k}[/mm] = [mm]\vektor{n \\ k }*k[/mm]
>  
> Frage: Wie begründe ich das k an dieser Stelle? Warum
> gerade k?

Es gibt [mm] \vektor{n \\ k } [/mm] k-elementige Teilmengen (Binomialkoeffizient). Da in jeder Teilmenge k Elemente sind, gibt es k Möglichkeiten, eines davon auszuzeichnen.

>  
> * Wir wählen das Element, das als ausgezeichnetes
> auftreten soll, und ergänzen aus den verbleibenden n - 1
> Elementen zu einer k-Teilmenge:
>  
> [mm]a_{n, k}[/mm] = n * [mm]\vektor{n - 1 \\ k - 1}.[/mm]
>  
> Das kann ich schon eher nachvollziehen. Wenn wir eine Menge
> haben [mm]\{ n_{1}, n_{2}, ..., n_{k} \} (n_{k}[/mm] ist dabei das
> ausgezeichnete Element), dann kann ich das für jedes
> Element so schreiben:
>
> [mm]\{ n_{k} \} \cup \{n_{1}, n_{2}, ..., n_{n-1} \}[/mm]
>
> Da wir [mm]n_{k}[/mm] aus der Teilmenge k-ter Ordnung rausgenommen
> haben, müssen wir nur noch die Teilmengen k-1-ter Ordnung
> der Menge n-1 zählen.
>
>
>  
> Nach der Regel vom doppelten Abzählen erhalten wir:
>  
> k * [mm]\vektor{n \\ k}[/mm] = n * [mm]\vektor{n - 1 \\ k - 1}[/mm]
>  

Gruß

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


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