anderer Beweis binom Lehrsatz < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:19 Di 05.02.2013 | | Autor: | quasimo |
| Aufgabe | Ein Beweis des binomischen Lehrsatzes:
(1+x)*(1+x)...*(1+x)= [mm] \sum_{T\subseteq [n]} x^{|T|} [/mm] = [mm] \sum_{T\subseteq[n]} \prod_{s \in T}x^{1_T(s)} [/mm] = [mm] \sum_{k=0}^n \vektor{n \\ k} x^k
[/mm]
wobei: [n]:= [mm] \{1,2,..n\}
[/mm]
|T|:= Kardinalität von T
[mm] 1_T [/mm] charakteristische Funktion der Teilmenge T
[mm] 1_T [/mm] (i) = 1 falls i [mm] \in [/mm] T
[mm] 1_T [/mm] (i) = 0 falls i [mm] \not\in [/mm] T |
Hallo
Bei dem Beweis steige ich beim letzten Gleichheitszeichen aus.
Kommt der binomialkoeffizient deshlab hier hin, da es eine Bijektion zwischen der Familie aller teilmengen von [n] auf das cartesische Produkt [mm] \{0,1\}^n [/mm] gibt? Ist |T|=k ?
Würde mich freuen, wenn mir wer den Schritt erklärt!
Liebe Grüße
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:18 Di 05.02.2013 | | Autor: | Marcel |
Hallo,
> Ein Beweis des binomischen Lehrsatzes:
>
> (1+x)*(1+x)...*(1+x)= [mm]\sum_{T\subseteq [n]} x^{|T|}[/mm] =
> [mm]\sum_{T\subseteq[n]} \prod_{s \in T}x^{1_T(s)}[/mm] =
> [mm]\sum_{k=0}^n \vektor{n \\ k} x^k[/mm]
>
> wobei: [n]:= [mm]\{1,2,..n\}[/mm]
> |T|:= Kardinalität von T
> [mm]1_T[/mm] charakteristische Funktion der Teilmenge T
> [mm]1_T[/mm] (i) = 1 falls i [mm]\in[/mm] T
> [mm]1_T[/mm] (i) = 0 falls i [mm]\not\in[/mm] T
> Hallo
> Bei dem Beweis steige ich beim letzten Gleichheitszeichen
> aus.
> Kommt der binomialkoeffizient deshlab hier hin, da es eine
> Bijektion zwischen der Familie aller teilmengen von [n] auf
> das cartesische Produkt [mm]\{0,1\}^n[/mm] gibt? Ist |T|=k ?
in Eurer Notation ist doch einfach
[mm] $$\binom{n}{k}=\left|\left\{A \subseteq [n]:\;\;\;|A|=k\right\}\right|\,.$$
[/mm]
In der Kombinatorik lernt man, dass [mm] $\binom{n}{k}$ [/mm] angibt, auf wieviele
verschiedene Arten man [mm] $k\,$ [/mm] Objekte aus einer [mm] $n\,$-elementigen [/mm] Menge
ziehen kann, wobei hier "Ziehen ohne Zurücklegen" gemeint ist und die
Reihenfolge keine Rolle spielt.
Genau das ist es doch, was Du oben brauchst. Was Dich hier übrigens
eigentlich interessiert, ist doch eher sowas:
Bei
[mm] $$(1+x)^n$$
[/mm]
stehen da [mm] $n\,$-Faktoren, [/mm] und Du kannst Dir kombinatorisch (und mit dem
Distributivgesetz) überlegen, dass da dann erstmal [mm] $2^n\,$ [/mm] Summanden rauskommen.
Jeder Summand ist wiederum selbst ein Produkt aus [mm] $n\,$ [/mm] Faktoren:
Schreibst Du den Summand als [mm] $n\,$-Tupel, [/mm] so enthält er [mm] $k\,$ [/mm] Mal das [mm] $x\,$
[/mm]
und dann [mm] $n-k\,$-Mal [/mm] die [mm] $1\,.$ [/mm] (Sei dabei $x [mm] \not=1$ [/mm] angenommen!)
Erstmal zu Verdeutlichung:
[mm] $$(1+x)^2=1*1+1*x+x*1+x*x\,.$$
[/mm]
Das sind [mm] $4=2^2$ [/mm] Summanden:
Der erste Summand (die Reihenfolge der Nummerierung der Summanden spielt keine Rolle)
$$1*1 [mm] \leftrightarrow (1,1)\,,$$
der zweite
$$1*x \leftrightarrow (1,x)\,,$$
der dritte
$$x*1 \leftrightarrow (x,1)\,,$$
der vierte
$$x*x \leftrightarrow (x,x)\,.$$
Mach' das ganze mal mit $n=3\,.$
Dann wirst Du (deutlicher) sehen, dass Du alle Summanden aufgezählt hast,
wenn Du angibst, auf wieviele Arten man ein 3-Tupel "füllen" kann, wenn dabei
für jede Stelle des 3-Tupels $1\,$ oder $x\,$ eingesetzt werden kann. Und
dabei kann etwa
$\bullet$ das $x\,$ an keiner Stelle stehen,
$\bullet$ das $x\,$ an genau einer Stelle stehen,
$\bullet$ das $x\,$ an genau zwei Stellen stehen,
$\bullet$ das $x\,$ an allen drei Stellen stehen.
Im Endeffekt ist es doch so:
$$\{(y_1,...,y_n):\;\;\;y_j \in \{1,x\} \text{ für }j=1,...,n\}=\{f\colon [n] \to \{1,x\}\}$$
hat für $x \not=1$ sicher $2^n$ Elemente.
Weiter kann man aber
$$\{(y_1,...,y_n):\;\;\;y_j \in \{1,x\} \text{ für }j=1,...,n\}=\{f\colon [n] \to \{1,x\}\}={\bigcup^d}\blue{\limits_{j=0}^{n}}\{g\colon [n] \to \{1,x\}:\;\;\;|\{k \in [n] \text{ mit }g(k)=x\}|=j\}$$
schreiben, wobei die letzte Vereinigung eine disjunkte ist. Das sieht jetzt
vielleicht symbolisch wild aus, ist aber recht einfach:
Dort steht einfach nur, dass die Menge aller Abbildungen $\{1,...,n\} \to \{1,x\}$
einfach die (disjunkte) Vereinigung über alle Abbildungen $\{1,...,n\} \to \{1,x\}\,,$
wobei der Wert $x\,$ genau $k\,$ Mal angenommen wird, und diese
Vereingung wird gebildet, indem $k\,$ die Werte von $0\,$ bis $n\,$ durchläuft, ist.
Und in der Notation
$$\sum_{T\subseteq[n]} \prod_{s \in T}x^{1_T(s)}$$
kannst Du quasi sagen:
Wenn man sich bei einem Summanden, der ja ein Produkt aus $n\,$ Faktoren
ist, sich vorstellt, dass dieser ein $n\,$-Tupel ist, und ich stelle mir vor, dass
ich die Stellen durchnummeriert habe
(1.Stelle, 2.Stelle, ..., n-te Stelle)
dann ist $T\,$ eine Teilmenge, die die Nummern enthält, an denen das $x\,$
steht.
Allerdings finde ich es ziemlich unsinnig, dass oben
$$\produkt_{s \in T}x^{1_T(s)}$$
steht, denn genau für $s \in T$ gilt $1_T(s)=1\,.$
Es ist also
$$\produkt_{s \in T}x^{1_T(s)}=\produkt_{s \in T}x^{1}=\produkt_{s \in T}x=x^{|T|}\,,$$
so dass ich oben
$$\sum_{T\subseteq[n]} \prod_{s \in T}x^{1_T(s)}=\sum_{T\subseteq[n]} x^{|T|}=\sum_{\substack{T \subseteq [n]:\;\;|T|=k\\k \in \{0,...,n\}}}x^k$$
ersetzen würde, und dann ist alles klar, wenn man die erste Gleichheit, die
ich hier nannte, beachtet.
Ich habe hier auch so 'n bisschen das Gefühl, dass der Dozent/die
Dozentin hier ein wenig hin und herspringt und einmal diese erstgenannte
Gleichheit benutzen will und dann aber auch wiederum mit den
Abbildungen
$$Z^D=\{f \colon D \to Z\}$$
arbeitet, wobei ein Tupel bzw. ein kartesisches Produkt ja damit
identifiziert werden kann (bzw. manchmal auch einfach damit definiert
wird).
Und vielleicht sollte anstatt
$$\sum_{T\subseteq[n]} \prod_{s \in T}x^{1_T(s)}$$
dort ja auch stehen
$$\sum_{T\subseteq[n]} \prod_{s \in \red{[n]}}x^{1_T(s)}\,,$$
denn für was will man sonst hier die Indikatorfunktion $1_T$ mitschleppen,
wenn man in dem Produkt eh nur die $s\,$ betrachtet, für die
$1_T(s)=1$ gilt? Dann kann man auch direkt $1_T(s)=1\,$ dort verwenden...
Gruß,
Marcel
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:39 Do 07.02.2013 | | Autor: | quasimo |
Hallo
Vielen Dank für die Erkärungen dazu
> Und vielleicht sollte anstatt
$ [mm] \sum_{T\subseteq[n]} \prod_{s \in T}x^{1_T(s)} [/mm] $
> dort ja auch stehen
$ [mm] \sum_{T\subseteq[n]} \prod_{s \in \red{[n]}}x^{1_T(s)}\,, [/mm] $
Kann sein, ich habe kein Skript dazu. Da kann es sich um einen Abschreibfehler von mir oder um einen "Flüchtigkeitsfehler" vom Prof. handeln, beides möglich.
LG
|
|
|
|
