Identitäten von < Kombinatorik < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
| Aufgabe | Man gebe kombinatorische Beweise für die folgenden Binomialidentitäten:
(a) [mm] $n\cdot [/mm] { n-1 [mm] \choose [/mm] k-1 } = k [mm] \cdot {n\choose k } [/mm] $
(b) [mm] $\sum_{i=0}^n i\cdot {n\choose i} [/mm] = [mm] n\cdot 2^{n-1} [/mm] $
(c) [mm] ${n+1\choose k+1} [/mm] = [mm] \sum_{m=k }^n {m\choose k}$ [/mm]
(d) [mm] ${n\choose k } [/mm] {k [mm] \choose [/mm] m } = { [mm] n\choose [/mm] m } {n-m [mm] \choose [/mm] k-m } $ |
zu (a): die rechte Seite ist die Anzahl aller Möglichkeiten aus einer
n-Menge eine k-Menge auszuwählen und dort ein Element "rot" zu färben,
nennen wir dies a bei einer beliebigen Menge A.
Grund: Jede Teilmenge hat ja $k-$Elemente und ich habe bei jeder Teilmenge
ja die Möglichkeit ein Element zu färben und das kann ich wohl $k$ mal
machen, also...
So, bei der rechten Seite scheint es günstig zu sein, dieses angefärbte
Element in den Teilmengen zu "suchen". Wenn ich wissen will, wo es
vorkommt, nehme ich es überall dort raus, wo es vorkommt, denn so kann
ich Methoden anwendbar machen und die Anzahl der Teilmengen verändert
sich ja dadurch offenbar nicht...
Nun, wenn ich das a aus allen Teilmengen entferne, wo es drinnen liegt, redzuziert sich die Anzahl der Elemente bei diesen Teilmengen um 1. Da es dann aber in KEINER Teilmenge mehr drinnen ist, ist es so, als würde ich von der Hauptmenge $X:=1,2, [mm] \ldots,n$ [/mm] ein Element nehmen und erhalte so alle Teilmengen von [mm] $X\setminus\{a\} [/mm] .$ Also ergibt dies ${n-1 [mm] \choose [/mm] k-1}$
Mein Problem ist jedoch, dass ich kombinatorisch nicht einsehe, wie man auf das n auf der linken Seite kommen soll. Ich habe ein beliebiges, aber festes angemaltes Element betrachtet und es abgezählt. Warum sollte die Anzahl n mal so hoch sein, wie mein Resultat?
Kann mir dabei jemand helfen?
Zu b)
Folgt sofort aus (a), wenn man die rechte Seite von (a) aufsummiert; es ist klar, dass daraus die Potenzmengenmächtigkeit resultiert...
Zu c) Mit Induktion: Der Induktionsanfang ist klar. Der Induktionsschluss folgt ganz einfach durch kombinatorische Summenaufpsaltung der rekursiven Art: [mm] ${n\choose k } [/mm] = { n-1 [mm] \choose [/mm] k -1 } + {n-1 [mm] \choose [/mm] k} $.
Rin rein kombinatorischer Beweis scheint mir hier zu schwierig und wenn nicht gar unmöglich. Was sagt ihr?
Zu d)
Wenn (a) richtig ist, lässt sich dieses leicht auf (d) verallgemeinern, man hat ja immerhin einerseits [mm] ${n\choose 1} [/mm] $ und andererseits ${k [mm] \choose [/mm] 1}$ stehen... man färbt also diesmal nicht ein - sondern $k$ Elemente zu färben. Meine Argumente scheinen aber schwammig zu sein... Ich tu mir ein wenig schwer hier in der Unterscheidung von "rein beliebiges Argument" vs. "beliebiges, jedoch festes Element"... Kann mir da jemand ein wenig helfen?
|
|
| |
|
> Man gebe kombinatorische Beweise für die folgenden
> Binomialidentitäten:
> (a) [mm]n\cdot { n-1 \choose k-1 } = k \cdot {n\choose k }[/mm]
> (b) [mm]\sum_{i=0}^n i\cdot {n\choose i} = n\cdot 2^{n-1} [/mm]
> (c) [mm]{n+1\choose k+1} = \sum_{m=k }^n {m\choose k}[/mm]
> (d) [mm]{n\choose k } {k \choose m } = { n\choose m } {n-m \choose k-m }[/mm]
>
> zu (a): die rechte Seite ist die Anzahl aller
> Möglichkeiten aus einer
> n-Menge eine k-Menge auszuwählen und dort ein Element
> "rot" zu färben,
> nennen wir dies a bei einer beliebigen Menge A.
> Grund: Jede Teilmenge hat ja [mm]k-[/mm]Elemente und ich habe bei
> jeder Teilmenge
> ja die Möglichkeit ein Element zu färben und das kann
> ich wohl [mm]k[/mm] mal
> machen, also...
>
> So, bei der rechten Seite scheint es günstig zu sein,
> dieses angefärbte
> Element in den Teilmengen zu "suchen". Wenn ich wissen
> will, wo es
> vorkommt, nehme ich es überall dort raus, wo es vorkommt,
> denn so kann
> ich Methoden anwendbar machen und die Anzahl der
> Teilmengen verändert
> sich ja dadurch offenbar nicht...
> Nun, wenn ich das a aus allen Teilmengen entferne, wo es
> drinnen liegt, redzuziert sich die Anzahl der Elemente bei
> diesen Teilmengen um 1. Da es dann aber in KEINER Teilmenge
> mehr drinnen ist, ist es so, als würde ich von der
> Hauptmenge [mm]X:=1,2, \ldots,n[/mm] ein Element nehmen und erhalte
> so alle Teilmengen von [mm]X\setminus\{a\} .[/mm] Also ergibt dies
> [mm]{n-1 \choose k-1}[/mm]
> Mein Problem ist jedoch, dass ich
> kombinatorisch nicht einsehe, wie man auf das n auf der
> linken Seite kommen soll. Ich habe ein beliebiges, aber
> festes angemaltes Element betrachtet und es abgezählt.
> Warum sollte die Anzahl n mal so hoch sein, wie mein
> Resultat?
Bei deiner Methode für rechts kann es jedem der Elemente der Grundmenge passieren, rot eingefärbt zu werden.
Damit gibt es links n Möglichkeiten für dieses "fest" ausgesuchte Element.
>
> Kann mir dabei jemand helfen?
>
>
>
> Zu b)
> Folgt sofort aus (a), wenn man die rechte Seite von (a)
> aufsummiert; es ist klar, dass daraus die
> Potenzmengenmächtigkeit resultiert...
>
> Zu c) Mit Induktion: Der Induktionsanfang ist klar. Der
> Induktionsschluss folgt ganz einfach durch kombinatorische
> Summenaufpsaltung der rekursiven Art: [mm]{n\choose k } = { n-1 \choose k -1 } + {n-1 \choose k} [/mm].
> Rin rein kombinatorischer Beweis scheint mir hier zu
> schwierig und wenn nicht gar unmöglich. Was sagt ihr?
Hier wählst du ein festes Element a der Grundmenge A und betrachtest alle k-elementigen Teilmengen von A.
Diejenigen, die a enthalten, entsprechen den k-1-elementigen Teilmengen von [mm] A\setminus\{a\},
[/mm]
die die a nicht enthalten, den k-elementigen.
>
> Zu d)
> Wenn (a) richtig ist, lässt sich dieses leicht auf (d)
> verallgemeinern, man hat ja immerhin einerseits [mm]{n\choose 1}[/mm]
> und andererseits [mm]{k \choose 1}[/mm] stehen... man färbt also
> diesmal nicht ein - sondern [mm]k[/mm] Elemente zu färben. Meine
> Argumente scheinen aber schwammig zu sein... Ich tu mir ein
> wenig schwer hier in der Unterscheidung von "rein
> beliebiges Argument" vs. "beliebiges, jedoch festes
> Element"... Kann mir da jemand ein wenig helfen?
>
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:20 Do 03.11.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
