Kombinatorische Beweise < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Behauptung: für alle $n [mm] \in \IN$ [/mm] mit $n [mm] \ge [/mm] 2$ ist [mm] $\vektor{2n \\ 2}=2\vektor{n \\ 2}+n^{2}$
[/mm]
Beweisen Sie die Behauptung
a) durch Anwendung der Definition und ausrechnen.
b) mit kombinatorischen Argumenten. (Hinweis: eine Menge mit 2n Elementen ist eine disjunkte Vereinigung von zwei Mengen mit je n Elementen.) |
Hallo,
mir bereitet bei der (a) leider der 3. Schritt Probleme. Ich sehe nicht, wie man auf den Zähler [mm] $\!(2n)(2n-1)(2n-2)!\$ [/mm] kommt, denn in meiner Formelsammlung habe ich [mm] $\vektor{n \\ k}=\bruch{n(n-1)(n-2)...(n-k+1)}{k!}=\bruch{n!}{(n-k)!k!}$ [/mm] stehen?
Lösung:
[mm] $\vektor{n \\ k}=\bruch{n!}{(n-k)!k!}$
[/mm]
$n!=n(n-1)*...*2*1$
(a) [mm] $\vektor{2n \\ 2}=$
[/mm]
[mm] $=\bruch{(2n)!}{(2n-2)!*2!}=$
[/mm]
[mm] $=\bruch{(2n)(2n-1)(2n-2)!}{2!*(2n-2)!}=$
[/mm]
$=n(2n-1)=$
$=n((n-1)+n)=$
[mm] $=n*(n-1)*n^{2}=$
[/mm]
[mm] $=2\bruch{n(n-1)(n-2)!}{2!(n-2)!}+n^{2}=$
[/mm]
[mm] $=2\bruch{n!}{(n-2)!*2!}+n^{2}=$
[/mm]
[mm] $=2\vektor{n \\ 2}+n^{2}$
[/mm]
Vielen Dank für die Mühe!
Gruß
el_grecco
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:07 Mo 05.09.2011 | | Autor: | statler |
Mahlzeit!
> Behauptung: für alle [mm]n \in \IN[/mm] mit [mm]n \ge 2[/mm] ist [mm]\vektor{2n \\ 2}=2\vektor{n \\ 2}+n^{2}[/mm]
>
> Beweisen Sie die Behauptung
>
> a) durch Anwendung der Definition und ausrechnen.
> b) mit kombinatorischen Argumenten. (Hinweis: eine Menge
> mit 2n Elementen ist eine disjunkte Vereinigung von zwei
> Mengen mit je n Elementen.)
> Hallo,
>
> mir bereitet bei der (a) leider der 3. Schritt Probleme.
> Ich sehe nicht, wie man auf den Zähler
> [mm]\!(2n)(2n-1)(2n-2)!\[/mm] kommt, denn in meiner Formelsammlung
> habe ich [mm]\vektor{n \\ k}=\bruch{n(n-1)(n-2)...(n-k+1)}{k!}=\bruch{n!}{(n-k)!k!}[/mm]
> stehen?
>
> Lösung:
>
> [mm]\vektor{n \\ k}=\bruch{n!}{(n-k)!k!}[/mm]
>
> [mm]n!=n(n-1)*...*2*1[/mm]
>
>
> (a) [mm]\vektor{2n \\ 2}=[/mm]
>
> [mm]=\bruch{(2n)!}{(2n-2)!*2!}=[/mm]
>
> [mm]=\bruch{(2n)(2n-1)(2n-2)!}{2!*(2n-2)!}=[/mm]
Im Zähler hast du einfach (2n)! erst auseinandergefriemelt und dann neu zusammengafaßt:
(2n)! = (2n) [mm] \* [/mm] (2n-1) [mm] \* [/mm] (2n-2) [mm] \* \dots \* [/mm] 2 [mm] \* [/mm] 1 = (2n) [mm] \* [/mm] (2n-1) [mm] \* [/mm] (2n-2)!
> [mm]=n(2n-1)=[/mm]
>
> [mm]=n((n-1)+n)=[/mm]
>
> [mm]=n*(n-1)*n^{2}=[/mm]
[mm]=n*(n-1) + [mm] n^{2}=
[/mm]
> [mm]=2\bruch{n(n-1)(n-2)!}{2!(n-2)!}+n^{2}=[/mm]
>
> [mm]=2\bruch{n!}{(n-2)!*2!}+n^{2}=[/mm]
>
> [mm]=2\vektor{n \\ 2}+n^{2}[/mm]
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Aufgabe | Behauptung: für alle [mm]n \in \IN[/mm] mit [mm]n \ge 2[/mm] ist [mm]\vektor{2n \\ 2}=2\vektor{n \\ 2}+n^{2}[/mm]
Beweisen Sie die Behauptung
a) durch Anwendung der Definition und ausrechnen.
b) mit kombinatorischen Argumenten. (Hinweis: eine Menge mit 2n Elementen ist eine disjunkte Vereinigung von zwei Mengen mit je n Elementen.) |
Hallo Dieter,
> > mir bereitet bei der (a) leider der 3. Schritt Probleme.
> > Ich sehe nicht, wie man auf den Zähler
> > [mm]\!(2n)(2n-1)(2n-2)!\[/mm] kommt, denn in meiner Formelsammlung
> > habe ich [mm]\vektor{n \\ k}=\bruch{n(n-1)(n-2)...(n-k+1)}{k!}=\bruch{n!}{(n-k)!k!}[/mm]
> > stehen?
> >
> > Lösung:
> >
> > [mm]\vektor{n \\ k}=\bruch{n!}{(n-k)!k!}[/mm]
> >
> > [mm]n!=n(n-1)*...*2*1[/mm]
> >
> >
> > (a) [mm]\vektor{2n \\ 2}=[/mm]
> >
> > [mm]=\bruch{(2n)!}{(2n-2)!*2!}=[/mm]
> >
> > [mm]=\bruch{(2n)(2n-1)(2n-2)!}{2!*(2n-2)!}=[/mm]
>
> Im Zähler hast du einfach (2n)! erst auseinandergefriemelt
> und dann neu zusammengafaßt:
> (2n)! = (2n) [mm]\*[/mm] (2n-1) [mm]\*[/mm] (2n-2) [mm]\* \dots \*[/mm] 2 [mm]\*[/mm] 1 = (2n)
> [mm]\*[/mm] (2n-1) [mm]\*[/mm] (2n-2)!
genau das verstehe ich nicht: wie kommt dann die Fakultät (2n-2)! zustande?
Danke
&
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:09 Mo 05.09.2011 | | Autor: | luis52 |
> genau das verstehe ich nicht: wie kommt dann die Fakultät
> (2n-2)! zustande?
>
[mm] $(2n)!=(2n)(2n-1)\underbrace{(2n-2)(2n-3)\cdot\ldots\cdot2\cdot1}_{=(2n-2)!}$.
[/mm]
vg Luis
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:24 Mo 05.09.2011 | | Autor: | el_grecco |
Danke Dir, Luis!
Irgendwie hatte ich da voll den gedanklichen Hänger drinnen...
Gruß
el_grecco
|
|
|
|
