Bijektion

28.10.2006, 17:32

Frooke

Auf diesen Beitrag antworten »

Bijektion

Hallo! Sorry, dass ich nochmals störe, aber ich habe erneut eine Aufgabe, bei deren Lösung ich nicht sicher bin:

Für $\begin{eqnarray*} n\in\mathbb N_0 \end{eqnarray*}$ seien die Mengen $\begin{eqnarray*} A_n \end{eqnarray*}$ und $\begin{eqnarray*} B_n \end{eqnarray*}$ folgendermassen definiert:

$\begin{eqnarray*} A_n:=\left.\left\{(k_1,k_2,k_3)\in\mathbb N_0^3\right|k_1+k_2+k_3=n\right\} \end{eqnarray*}$

$\begin{eqnarray*} B_n:=\left.\left\{(k_1,k_2)\in\mathbb N_0^2\right|k_1+k_2\leq n\right\} \end{eqnarray*}$

1. Geben Sie eine Bijektion $\begin{eqnarray*} \phi:B_n\to A_n \end{eqnarray*}$ an.

2. Finden Sie eine Formel für die Anzahl der Elemente in $\begin{eqnarray*} A_n \end{eqnarray*}$ .

Bei 1 habe ich mir Folgendes gedacht:

$\begin{eqnarray*} \phi:=B_n\to A_n,\qquad (x_1,x_2)\mapsto(x_1,x_2,n-(x_1+x_2)) \end{eqnarray*}$

$\begin{eqnarray*} \phi \end{eqnarray*}$ ist injektiv, denn für

$\begin{eqnarray*} (x_1,x_2,n-(x_1+x_2))=(y_1,y_2,n-(y_1+y_2))\Longrightarrow(x_1,x_2)=(y_1,y_2) \end{eqnarray*}$ .

Oder: Falls $\begin{eqnarray*} (x_1,x_2)\ne(y_1,y_2) \end{eqnarray*}$ folgt sofort, dass auch die Bilder von $\begin{eqnarray*} (x_1,x_2)\text{ bzw. }(y_1,y_2) \end{eqnarray*}$ nicht gleich sind.

$\begin{eqnarray*} \phi \end{eqnarray*}$ ist surjektiv, weil für jedes $\begin{eqnarray*} a\in A_n \end{eqnarray*}$ ein $\begin{eqnarray*} b\in B_n \end{eqnarray*}$ existiert, so dass $\begin{eqnarray*} \phi(b)=a \end{eqnarray*}$ .

Seien $\begin{eqnarray*} a_1,a_2,n-(a_1+a_2)\in A \end{eqnarray*}$ . Es folgt dass $\begin{eqnarray*} a_1,a_2\in B_n \forall a_1,a_2 \end{eqnarray*}$ wegen $\begin{eqnarray*} n-(a_1+a_2)\in\mathbb N_0 \end{eqnarray*}$ .

Passt das so?

Und zu 2 habe ich gedacht:

$\begin{eqnarray*} \sharp A_n=\frac{(n+1)(n+2)}{2} \end{eqnarray*}$

Dabei bezeichnet $\begin{eqnarray*} \sharp A_n \end{eqnarray*}$ die Anzahl der in A_n enthaltenen Elemente...

Aber da scheitere ich an einem wohl sehr einfachen Induktionsbeweis...

28.10.2006, 17:37

Dual Space

Auf diesen Beitrag antworten »

RE: Bijektion
1. passt so. Freude

Freude

2. sieht gut aus, aber eine kurze Begründung, warum das stimmen soll, wäre vielleicht nicht schlecht. Augenzwinkern

Augenzwinkern

28.10.2006, 17:46

Frooke

Auf diesen Beitrag antworten »

Vielen Dank für Deine Antwort: Zu zwei habe ich Folgendes:

Schreiben wir für $\begin{eqnarray*} \sharp A_n:=A(n) \end{eqnarray*}$

Behauptung:

$\begin{eqnarray*} A(n)=\frac{(n+1)(n+2)}{2} \end{eqnarray*}$

$\begin{eqnarray*} A(0)=1 \end{eqnarray*}$ (Passt also.)

$\begin{eqnarray*} A(n+1)=\frac{(n+2)(n+3)}{2} \end{eqnarray*}$

Darauf kann ich irgendwie die Induktionsvoraussetzung nur so anwenden, dass ich eine neue Behauptung erhalte, die dann noch bewiesen werden muss:

$\begin{eqnarray*} A(n+1)=\frac{(n+2)(n+3)}{2}=\frac{(n+2)(n+1+2)}{2}=\frac{(n+2)(n+1)}{2}+(n+2) \end{eqnarray*}$

Also

$\begin{eqnarray*} A(n+1)=A(n)+n+2 \end{eqnarray*}$

Wie soll ich das nun beweisen?

Offensichtlich stimmen beide (also die Rekursionsvorschrift und die explizite Angabe), aber es gelingt mir irgendwie nicht die Dinge zu einem Beweis zu verwursteln... unglücklich

unglücklich

...

28.10.2006, 17:55

Dual Space

Auf diesen Beitrag antworten »

Zitat:

Original von Frooke
Also

$\begin{eqnarray*} A(n+1)=A(n)+n+2 \end{eqnarray*}$

Wie soll ich das nun beweisen?

Die Rekursion ist äquivalent zu deiner expliziten Darstellung. Sollte es nicht einfacher sein die Rekursion mittels Induktion zu beweisen?

28.10.2006, 18:00

Frooke

Auf diesen Beitrag antworten »

Genau da ist der Haken... Ich krieg grad mal den Fall n=0 hin.

Ich müsste ja aus $\begin{eqnarray*} A(n+1)=A(n)+n+2 \end{eqnarray*}$ folgern, dass

$\begin{eqnarray*} A(n+2)=A(n+1)+n+3 \end{eqnarray*}$ aber dafür fehlt mir der Ansatz...

28.10.2006, 18:06

Dual Space

Auf diesen Beitrag antworten »

Mir ist übrigens grad aufgefallen, dass für $\begin{eqnarray*} A(n) \end{eqnarray*}$ gelten muss, dass $\begin{eqnarray*} A(n+1)=3A(n) \end{eqnarray*}$ ist. Offenbar liefert diese Rekursion mit dem Anfangswert $\begin{eqnarray*} A(0)=1 \end{eqnarray*}$ die selben Werte wie deine Rekursion. Nützt dir das was?

Anzeige

28.10.2006, 18:10

Frooke

Auf diesen Beitrag antworten »

Ich hab jetzt was Anderes:

$\begin{eqnarray*} A(n+2)=A(n+1)+n+3=A(n)+2n+5 \end{eqnarray*}$

Zeige die Gleichheit der rechten Gleichung:

$\begin{eqnarray*} A(n+1)+n+3=A(n)+2n+5\Leftrightarrow A(n+1)=A(n)+n+2 \end{eqnarray*}$

Passt das so?

28.10.2006, 18:13

sqrt(2)

Auf diesen Beitrag antworten »

Zitat:

Original von Dual Space
Mir ist übrigens grad aufgefallen, dass für $\begin{eqnarray*} A(n) \end{eqnarray*}$ gelten muss, dass $\begin{eqnarray*} A(n+1)=3A(n) \end{eqnarray*}$ ist.

Wie kommst du darauf? Der Quotient deiner A(n+1) und 3A(n) ist i.A. sicher ungleich 1.

Ich würde mal in Richtung

$\begin{eqnarray*} \sum_{k=1}^{n+1} k=\frac{(n+1)(n+2)}{2} \end{eqnarray*}$

nach einer Begründung suchen...

edit:

Zitat:

Original von Frooke
$\begin{eqnarray*} A(n+2)=A(n+1)+n+3=A(n)+2n+5 \end{eqnarray*}$

Zeige die Gleichheit der rechten Gleichung:

$\begin{eqnarray*} A(n+1)+n+3=A(n)+2n+5\Leftrightarrow A(n+1)=A(n)+n+2 \end{eqnarray*}$

Ähm, was beweist du gerade? Wenn du $\begin{eqnarray*} m=n+1 \end{eqnarray*}$ setzt, hast du gerade bewiesen, dass $\begin{eqnarray*} A(n+1)=A(m+1) \end{eqnarray*}$ .

Ich denke, du möchstest beweisen, dass deine Rekursionsformel für die Mächtigkeit von $\begin{eqnarray*} A_n \end{eqnarray*}$ gilt.

28.10.2006, 18:15

Dual Space

Auf diesen Beitrag antworten »

Zitat:

Original von Frooke
Ich hab jetzt was Anderes:

$\begin{eqnarray*} A(n+2)=A(n+1)+n+3=A(n)+2n+5 \end{eqnarray*}$

Zeige die Gleichheit der rechten Gleichung:

Da ist der Haken, denn damit beweist du die Gültigkeit der Induktionsvoraussetzung. Die hast du ja aber schon als gegeben vorausgesetzt.

Mal noch was anderes: Oben hab ich natürlich Unsinn geschrieben $\begin{eqnarray*} A(n+1)=3A(n) \end{eqnarray*}$ liefert natürlich andere Werte als deine Rekursion, aber irgendwie denke ich, das meine stimmt. verwirrt

verwirrt

28.10.2006, 18:18

Frooke

Auf diesen Beitrag antworten »

Das ist natürlich ein Zirkelschluss Hammer

Hammer

Vielleicht bin ich schon zu lange dran...

Zitat:

Original von sqrt(2)
$\begin{eqnarray*} \sum_{k=1}^{n+1}=\frac{(n+1)(n+2)}{2} \end{eqnarray*}$

Was meinst Du damit? Fehlt da nicht etwas hinter dem Summenzeichen?

Zitat:

Original von Dual Space
Mir ist übrigens grad aufgefallen, dass für $\begin{eqnarray*} A(n) \end{eqnarray*}$ gelten muss, dass $\begin{eqnarray*} A(n+1)=3A(n) \end{eqnarray*}$ ist.

Sicher?

28.10.2006, 18:22

sqrt(2)

Auf diesen Beitrag antworten »

Argh, ich hab zu lange nicht aktualisiert und dann noch editiert, tut mir Leid.

Also, was ich meinte, siehe mein Edit oben...

28.10.2006, 18:23

Dual Space

Auf diesen Beitrag antworten »

Zitat:

Original von sqrt(2)

Zitat:

Original von Dual Space
Mir ist übrigens grad aufgefallen, dass für $\begin{eqnarray*} A(n) \end{eqnarray*}$ gelten muss, dass $\begin{eqnarray*} A(n+1)=3A(n) \end{eqnarray*}$ ist.

Wie kommst du darauf? Der Quotient deiner A(n+1) und 3A(n) ist i.A. sicher ungleich 1.

Wieso sollte er auch 1 sein? verwirrt

verwirrt

Zitat:

Original von Frooke

Zitat:

Original von Dual Space
Mir ist übrigens grad aufgefallen, dass für $\begin{eqnarray*} A(n) \end{eqnarray*}$ gelten muss, dass $\begin{eqnarray*} A(n+1)=3A(n) \end{eqnarray*}$ ist.

Sicher?

Naja ... ixch hab mir das so gedacht:
Bei dem Schritt von n zu n+1 kann man jedes der $\begin{eqnarray*} A(n) \end{eqnarray*}$ Tripel aus $\begin{eqnarray*} A_n \end{eqnarray*}$ hernehmen und jedes $\begin{eqnarray*} k_i \end{eqnarray*}$ ( $\begin{eqnarray*} i\in\{1,2,3\} \end{eqnarray*}$ ) um eins erhöhen. *args* Forum Kloppe

Forum Kloppe

Tja ... wenn man's dann mal aufschreibt findet man auch den Fehler. Also Sorry für die Verwirrung ... ziehe mein Vorschlag zurück.

Edit: *gelöscht*

28.10.2006, 18:30

sqrt(2)

Auf diesen Beitrag antworten »

Zitat:

Original von Dual Space

Zitat:

Original von sqrt(2)

Zitat:

Original von Dual Space
Mir ist übrigens grad aufgefallen, dass für $\begin{eqnarray*} A(n) \end{eqnarray*}$ gelten muss, dass $\begin{eqnarray*} A(n+1)=3A(n) \end{eqnarray*}$ ist.

Wie kommst du darauf? Der Quotient deiner A(n+1) und 3A(n) ist i.A. sicher ungleich 1.

Wieso sollte er auch 1 sein? verwirrt

verwirrt

Weil aus $\begin{eqnarray*} A(n+1)=3A(n) \end{eqnarray*}$ folgt $\begin{eqnarray*} \frac{A(n+1)}{3A(n)}=1 \end{eqnarray*}$ Augenzwinkern

Augenzwinkern

Dann hat man einen Bruch, der sich nicht ganz kürzt (x+1), und der ist nicht konstant 1, das war es, was ich meinte.

28.10.2006, 18:32

Frooke

Auf diesen Beitrag antworten »

Ja eben, das war Schwachsinn mein Zirkelschluss, sorry... Neuer Ansatz: Es ist:

$\begin{eqnarray*} \sum_{k=1}^{n+1} k=\frac{(n+1)(n+2)}{2} \end{eqnarray*}$

Damit kann ich A_n anders definieren:

$\begin{eqnarray*} A(n)=\sum_{k=1}^{n+1} k=\frac{(n+1)(n+2)}{2} \end{eqnarray*}$

Zurück zur Rekursionsformel:

$\begin{eqnarray*} A(n+1)=A(n)+n+2 \end{eqnarray*}$

Das kann ich nun für allgemeine n zeigen:

Nun soll folgen:

$\begin{eqnarray*} A(n+1)=\sum_{k=1}^{n+2} k=\sum_{k=1}^{n+1} k+n+2 \end{eqnarray*}$

Und das passt.

Vielen mächtigen Dank für die tolle Hilfe euch beiden!

@DualSpace. Ich muss heute auch Schluss machen... Siehe meine im Kreis-umdrehungen smile

smile

...

28.10.2006, 18:38

sqrt(2)

Auf diesen Beitrag antworten »

Nur, was hast du jetzt bewiesen, Frooke? Dass deine Rerkusionsformel gleich deiner expliziten ist, aber nicht, dass diese Formel gleich der Mächtigkeit von $\begin{eqnarray*} A_n \end{eqnarray*}$ ist, oder?

28.10.2006, 18:55

Dual Space

Auf diesen Beitrag antworten »

Zitat:

Original von sqrt(2)
Weil aus $\begin{eqnarray*} A(n+1)=3A(n) \end{eqnarray*}$ folgt $\begin{eqnarray*} \frac{A(n+1)}{3A(n)}=1 \end{eqnarray*}$ Augenzwinkern

Augenzwinkern

Dann hat man einen Bruch, der sich nicht ganz kürzt (x+1), und der ist nicht konstant 1, das war es, was ich meinte.

Sorry, aber ich sehe immer noch nicht, auf was du hinauswillst. verwirrt

verwirrt

Dafür bin ich jetzt neugierig, was du wohl meinst ... Augenzwinkern

Augenzwinkern

28.10.2006, 18:55

Frooke

Auf diesen Beitrag antworten »

Ja natürlich Hammer

Hammer

... Mannomann... Shit... Ich weiss irgendwie nicht mehr weiter... Irgendwie ist das Ganze ja ein kombinatorisches Problem... *ratlossei*...

EDIT: Bei beiden Fällen kann ich die Induktionsvoraussetzung nicht nutzen. Hat da jemand einen Tipp?

28.10.2006, 19:14

Mathespezialschüler

Auf diesen Beitrag antworten »

Ich glaube, mit einer Induktion nach $\begin{eqnarray*} n \end{eqnarray*}$ kommt man hier nicht sehr weit. Man kann allgemein zeigen, dass die Menge

$\begin{eqnarray*} A_{m,n}=\{(k_1,\ldots,k_m)\in \mathbb N_0^m\ |\ k_1+\ldots+k_m=n\} \end{eqnarray*}$

$\begin{eqnarray*} {m+n-1\choose m-1}={m+n-1\choose n} \end{eqnarray*}$ Elemente hat, und zwar mit einer Induktion nach $\begin{eqnarray*} m \end{eqnarray*}$ . Versuch das mal!

Gruß MSS

28.10.2006, 19:44

sqrt(2)

Auf diesen Beitrag antworten »

Zitat:

Original von Dual Space
Sorry, aber ich sehe immer noch nicht, auf was du hinauswillst. verwirrt

verwirrt

Ich glaube, das ist ein Missverständnis. Ich bin von der Richtigkeit von Frookes expliziter Formel ausgegangen, du anscheinend nicht.

29.10.2006, 10:03

Dual Space

Auf diesen Beitrag antworten »

Zitat:

Original von sqrt(2)

Zitat:

Original von Dual Space
Sorry, aber ich sehe immer noch nicht, auf was du hinauswillst. verwirrt

verwirrt

Ich glaube, das ist ein Missverständnis. Ich bin von der Richtigkeit von Frookes expliziter Formel ausgegangen, du anscheinend nicht.

Ahhh .... verstehe. Mittlerweile bin ich aber auch von der Richtigkeit von Frookes Formel überzeugt. Augenzwinkern

Augenzwinkern

29.10.2006, 10:51

Frooke

Auf diesen Beitrag antworten »

Zitat:

Original von Mathespezialschüler
Man kann allgemein zeigen, dass die Menge

$\begin{eqnarray*} A_{m,n}=\{(k_1,\ldots,k_m)\in \mathbb N_0^m\ |\ k_1+\ldots+k_m=n\} \end{eqnarray*}$

$\begin{eqnarray*} {m+n-1\choose m-1}={m+n-1\choose n} \end{eqnarray*}$ Elemente hat, und zwar mit einer Induktion nach $\begin{eqnarray*} m \end{eqnarray*}$ . Versuch das mal!

Gruß MSS

Vermutlich mache ich es schon am Anfang falsch, aber auch hier komme ich nur auf eine Rekursionsformel...

Verankerung ist klar. Für m=1, gibt es 1 Element (passt also).

Dann habe ich sowas:

$\begin{eqnarray*} \sharp A_{m,n}={m+n-1\choose n}=\frac{(m+n-1)!}{n!(m-1)!} \end{eqnarray*}$

$\begin{eqnarray*} \sharp A_{m+1,n}={m+n\choose n}=\frac{(m+n-1)!(m+n)}{m(m-1)!n!}=\sharp A_{m,n}\cdot\frac{m+n}{m}=\sharp A_{m,n}\cdot\left(1+\frac{n}{m}\right) \end{eqnarray*}$ ...

verwirrt

verwirrt

29.10.2006, 16:04

Mathespezialschüler

Auf diesen Beitrag antworten »

Hmm, was bringt es, wenn du eine Rekursionsformel für den Term herleitest? Du sollst doch zeigen, dass die Menge $\begin{eqnarray*} A_{m+1,n} \end{eqnarray*}$ genau $\begin{eqnarray*} {m+n\choose n} \end{eqnarray*}$ Elemente hat! Bis jetzt hast du die Menge noch gar nicht mit einbezogen ...
Schreiben wir die Menge $\begin{eqnarray*} A_{m+1,n} \end{eqnarray*}$ mal etwas um:

$\begin{eqnarray*} A_{m+1,n}=\{(k_1,\ldots,k_{m+1})\in\mathbb N_0^{m+1}\ |\ k_1+\ldots+k_{m+1}=n\} \end{eqnarray*}$

$\begin{eqnarray*} =\{(k_1,\ldots,k_{m+1})\in\mathbb N_0^{m+1}\ |\ k_1+\ldots+k_m=n-k_{m+1}\} \end{eqnarray*}$ .

Du kannst diese Menge auch so darstellen:

$\begin{eqnarray*} A_{m+1,n}=\bigcup_{i=0}^n~\{(k_1,\ldots,k_m)\in\mathbb N_0^m\ |\ k_1+\ldots+k_m=n-i\}=\bigcup_{i=1}^n~A_{m,n-i} \end{eqnarray*}$ ,

da $\begin{eqnarray*} k_{m+1} \end{eqnarray*}$ ja alle Werte von $\begin{eqnarray*} 0 \end{eqnarray*}$ bis $\begin{eqnarray*} n \end{eqnarray*}$ annehmen kann. Diese Vereinigung ist disjunkt, sodass gilt:

$\begin{eqnarray*} |A_{m+1,n}|=\sum_{i=0}^n~|A_{m,n-i}| \end{eqnarray*}$ .

Und die Anzahl der Elemente dieser Mengen kennst du nach Induktionsvoraussetzung. Der Trick dabei ist, $\begin{eqnarray*} k_{m+1} \end{eqnarray*}$ auf die andere Seite zu bringen und als fest anzunehmen ...

Gruß MSS

29.10.2006, 16:42

Frooke

Auf diesen Beitrag antworten »

Zitat:

Original von Mathespezialschüler
Du kannst diese Menge auch so darstellen:

$\begin{eqnarray*} A_{m+1,n}=\bigcup_{i=0}^n~\{(k_1,\ldots,k_m)\in\mathbb N_0^m\ |\ k_1+\ldots+k_m=n-i\}=\bigcup_{i=1}^n~A_{m,n-i} \end{eqnarray*}$ ,

da $\begin{eqnarray*} k_{m+1} \end{eqnarray*}$ ja alle Werte von $\begin{eqnarray*} 0 \end{eqnarray*}$ bis $\begin{eqnarray*} n \end{eqnarray*}$ annehmen kann. Diese Vereinigung ist disjunkt, sodass gilt:

$\begin{eqnarray*} |A_{m+1,n}|=\sum_{i=0}^n~|A_{m,n-i}| \end{eqnarray*}$ .

Und die Anzahl der Elemente dieser Mengen kennst du nach Induktionsvoraussetzung. Der Trick dabei ist, $\begin{eqnarray*} k_{m+1} \end{eqnarray*}$ auf die andere Seite zu bringen und als fest anzunehmen ...

Gruß MSS

Das ist echt genial Gott

Gott

aber dummerweise würd ich auf sowas selbst wohl nicht kommen...

Nun damit Folgendes gegeben:

Wir haben: $\begin{eqnarray*} |A_{m+1,n}|={m+n\choose n}=\sum_{i=0}^n~|A_{m,n-i}|=\sum_{i=0}^n~{m+n-i-1\choose n-i} \end{eqnarray*}$

Passt es, dass ich nun diese Aussage mittels vollständiger Induktion beweisen muss oder übersehe ich etwas?

$\begin{eqnarray*} \sum_{i=0}^n~{m+n-i-1\choose n-i}={m+n\choose n} \end{eqnarray*}$

29.10.2006, 16:48

Mathespezialschüler

Auf diesen Beitrag antworten »

Ja, du musst jetzt noch

$\begin{eqnarray*} \sum_{i=0}^n~{m+n-i-1\choose n-i}=\sum_{i=0}^n~{m+n-i-1\choose m-1}={m+n\choose n} \end{eqnarray*}$

beweisen. Du kannst die Summe auch umschreiben zu

$\begin{eqnarray*} \sum_{i=0}^n~{m-1+i\choose m-1}=\sum_{k=m-1}^{m+n-1}~{k\choose m-1} \end{eqnarray*}$

und das ist ja eigentlich eine bekannte Summe. (Du kannst die Gleichung natürlich auch nochmal beweisen ...)

Gruß MSS

29.10.2006, 17:37

Frooke

Auf diesen Beitrag antworten »

Zitat:

Original von Mathespezialschüler
das ist ja eigentlich eine bekannte Summe. (Du kannst die Gleichung natürlich auch nochmal beweisen ...)

Gruß MSS

Ja vielen Dank. Den Beweis spar ich mir jetzt. Was ich noch wollte für mich, war die Äquivalenz zu meiner Formel zeigen resp. widerlegen.

Es gilt also nun:
$\begin{eqnarray*} |A_{m,n}|={m+n-1 \choose n} \end{eqnarray*}$

Für m=3 ist also:

$\begin{eqnarray*} |A_{3,n}|={3+n-1 \choose n}={2+n \choose n}=\frac{n!(n+1)(n+2)}{n!2!}=\frac{(n+1)(n+2)}{2} \end{eqnarray*}$

Damit ist die Richtigkeit meiner angenommenen Formel gezeigt.

Vielen lieben Dank für die tolle Hilfe!!! Freude

Freude

29.10.2006, 17:51

Mathespezialschüler

Auf diesen Beitrag antworten »

Gern geschehen. smile

smile

Gruß MSS

30.10.2006, 22:46

Frooke

Auf diesen Beitrag antworten »

Ich eröffne nochmals, weil mir mittlerweile noch eine andere Beweismöglichkeit eingefallen ist. Sie ist zwar nicht so schön, wie Deine, Max, dafür aber weniger knifflig:

Aufgrund der (im ersten Posting von mir angegebenen) Bijektivität von $\begin{eqnarray*} \phi:B_n\to A_n \end{eqnarray*}$ , können wir schliessen, dass $\begin{eqnarray*} \operatorname{card}(B_n)=\operatorname{card}(A_n) \end{eqnarray*}$ .

Betrachten wir nun zunächst die Menge $\begin{eqnarray*} C_n:=\left.\left\{\left(k_1,k_2\right)\in\mathbb N_0^2\right|k_1+k_2=n\right\} \end{eqnarray*}$

$\begin{eqnarray*} C_n \end{eqnarray*}$ kann folgendermassen geschrieben werden:

$\begin{eqnarray*} C_n:=\{\underbrace{(0,n),(1,n-1),(2,n-2)\ldots(n-1,1),(n,n)}_{n+1\text{ Elemente}}\} \end{eqnarray*}$

Definitionsgemäss ist (Die C_i's sind disjunkt): $\begin{eqnarray*} B_n=\bigcup_{i=0}^nC_i\Longrightarrow \operatorname{card}(B_n)=\sum_{i=0}^n\operatorname{card}(C_n)=\sum_{i=0}^n(i+1)=\sum_{i=1}^{n+1}i=(n+1)\frac{n+2}{2} \end{eqnarray*}$ , womit wir fertig wären smile

smile

.

EDIT: Noch ein IN^2 eingefügt.

01.11.2006, 23:37

diana

Auf diesen Beitrag antworten »

RE: Bijektion
$\begin{eqnarray*} \sharp A_n=\frac{(n+1)(n+2)}{2} \end{eqnarray*}$

ch verstehe nicht wie das die formel sein soll für die anzahl der elemente in a(n)
n= 1 ergibt 3 elemente
n=2 ergibt 6 elemente

bitte helft mir mal weiter.

01.11.2006, 23:44

Mathespezialschüler

Auf diesen Beitrag antworten »

Für $\begin{eqnarray*} n=1 \end{eqnarray*}$ hat man die drei Elemente $\begin{eqnarray*} (1,0,0); (0,1,0); (0,0,1) \end{eqnarray*}$ . Für $\begin{eqnarray*} n=2 \end{eqnarray*}$ sind es $\begin{eqnarray*} (2,0,0); (0,2,0); (0,0,2); (1,1,0); (1,0,1); (0,1,1) \end{eqnarray*}$ usw.

Gruß MSS

04.11.2006, 13:22

diane

Auf diesen Beitrag antworten »

Dann habe ich sowas:

$\begin{eqnarray*} \sharp A_{m,n}={m+n-1\choose n}=\frac{(m+n-1)!}{n!(m-1)!} \end{eqnarray*}$

wie sähe dieser koeffizient aus wenn ich die null nicht zu den natürlichen zahlen zähle

oder ist dass dann nicht mehr so machbar?
keine ganzen versuche sind daneben gegangen

ich müsste am ende auf die formel kommen:

$\begin{eqnarray*} \frac{(n-1)(n-2)}{2} \end{eqnarray*}$
also demnach so in der art wie das hier:
$\begin{eqnarray*} \begin{pmatrix} n \\ n-2 \end{pmatrix} =\frac{n!}{(n-2)!*(-2)!} \end{eqnarray*}$

EDIT by Frooke: $\begin{eqnarray*} \text{\LaTeX} \end{eqnarray*}$

04.11.2006, 14:36

Frooke

Auf diesen Beitrag antworten »

Nun, wenn Du die Null nicht dazuzählst, ist die Menge mit der wenigsten Anzahl von Elementen halt (1,1,1,1,....,1) (je nach m). Im Fall von m=3 gibt es dann einfach eine Indexverschiebung...

Also (1,1,1) statt (0,0,0)
Dann (1,2,1); (2,1,1); (1,1,2) statt (0,0,1); (1,0,1); (0,0,1)
usw...

Es verschiebt sich aber n, nicht m. Insofern verstehe ich Deinen letzten Binomialkoeffizienten nicht. verwirrt

verwirrt

EDIT: Strichpunkt vor Klammer hat ungewollte heulende Smilies produziert Augenzwinkern

Augenzwinkern

...

04.11.2006, 14:45

diane

Auf diesen Beitrag antworten »

also

m+n-2 statt m+n-1
und unten n-1? (zu faul für formeleditor)

04.11.2006, 15:32

Mathespezialschüler

Auf diesen Beitrag antworten »

Wenn du die $\begin{eqnarray*} 0 \end{eqnarray*}$ nicht dazuzählst, kannst du das auch einfach auf den anderen Fall zurückführen.

$\begin{eqnarray*} A'_{m,n}=\{(k_1,\ldots,k_m)\in\mathbb N^m\ |\ k_1+\ldots+k_m=n\} \end{eqnarray*}$ .

Sei $\begin{eqnarray*} x_i:=k_i-1 \end{eqnarray*}$ für $\begin{eqnarray*} 1\leq i\leq m \end{eqnarray*}$ . Dann gilt $\begin{eqnarray*} x_1+\ldots+x_m=(k_1-1)+\ldots+(k_m-1)=k_1+\ldots+k_m-m=n-m \end{eqnarray*}$ und damit:

$\begin{eqnarray*} \left|A'_{m,n}\right|=\left|\{(x_1,\ldots,x_m)\in\mathbb N_0^m\ |\ x_1+\ldots+x_m=n-m\}\right| \end{eqnarray*}$

Für $\begin{eqnarray*} n<m \end{eqnarray*}$ gibt es keine Elemente. Für $\begin{eqnarray*} n\geq m \end{eqnarray*}$ gilt:

$\begin{eqnarray*} \left|A'_{m,n}\right|={n-1\choose n-m}={n-1\choose m-1} \end{eqnarray*}$ .

Gruß MSS

04.11.2006, 16:07

diane

Auf diesen Beitrag antworten »

m ist ja dabei die anzahl der elemente k_i

ich hab das eben mal gemacht für m = 3
da ich in meinem beispiel 3 elemente habe und nur dafür die anzahl aller möglichen tripel berechnen soll
demnach heißt es

also
$\begin{eqnarray*} \begin{pmatrix} n-1 \\ 2 \end{pmatrix} \end{eqnarray*}$
komme dami aber nie auf die form:
$\begin{eqnarray*} \frac{(n-2)(n-1)}{2} \end{eqnarray*}$

wie formst du eigenlich das hier um?
$\begin{eqnarray*} \begin{pmatrix} n-1 \\ n-m \end{pmatrix}=\begin{pmatrix} n-1 \\ m-1 \end{pmatrix} \end{eqnarray*}$

04.11.2006, 19:54

Mathespezialschüler

Auf diesen Beitrag antworten »

Zitat:

Original von diane
$\begin{eqnarray*} \begin{pmatrix} n-1 \\ 2 \end{pmatrix} \end{eqnarray*}$
komme dami aber nie auf die form:
$\begin{eqnarray*} \frac{(n-2)(n-1)}{2} \end{eqnarray*}$

Wie ist denn der Binomialkoeffizient definiert?

Zitat:

Original von diane
wie formst du eigenlich das hier um?
$\begin{eqnarray*} \begin{pmatrix} n-1 \\ n-m \end{pmatrix}=\begin{pmatrix} n-1 \\ m-1 \end{pmatrix} \end{eqnarray*}$

Es gilt für $\begin{eqnarray*} k,l\in\mathbb N \end{eqnarray*}$ :

$\begin{eqnarray*} {k\choose l}={k\choose k-l} \end{eqnarray*}$ .

Gruß MSS

04.11.2006, 20:17

Frooke

Auf diesen Beitrag antworten »

Schau Dir sonst mal die Wikiseite über den Binomialkoeffizienten an (ist sehr gut) oder diese Seite hier (zur Veranschaulichung der Symmetrie der Binomialkoeffizienten).

EDIT: Interpunktion.

04.11.2006, 21:07

diane

Auf diesen Beitrag antworten »

Zitat:

Original von Mathespezialschüler

Zitat:

Original von diane
$\begin{eqnarray*} \begin{pmatrix} n-1 \\ 2 \end{pmatrix} \end{eqnarray*}$
komme dami aber nie auf die form:
$\begin{eqnarray*} \frac{(n-2)(n-1)}{2} \end{eqnarray*}$

Wie ist denn der Binomialkoeffizient definiert?

$\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} =\frac{n!}{k!(n-k)!} \end{eqnarray*}$
so isser definiert
und damit komme ich nicht auf die gewollt formel

04.11.2006, 21:13

diane

Auf diesen Beitrag antworten »

sorry meine dummheit ziehe meine aussage zurück natürlich mit produktzeichen

04.11.2006, 21:17

diane

Auf diesen Beitrag antworten »

aber eins weiß ich imemrnoch nicht
ich will die ja jetzt mit induktion beweisen

aber mein problem dabei ich habe keine gewöhnliche aussage

wie wenn es heißt summe von k=1 bin n von k^2 = irgendein ausdruck

hier habe ich ja einfach nur die formel ( n-1)*(n-2) / 2
mit was setzte ich das nun gleich?

04.11.2006, 21:27

Frooke

Auf diesen Beitrag antworten »

Hier hast Du ja ein Beispiel eines Induktionsbeweises ohne «normale» Aussage. Dieser ist natürlich wirklich genial! Und dieser hier (obwohl etwas simpler) zeigt ja auch Umformungen bei nicht «normale» Aussagen. Oder schreib doch mal genau auf, wie weit Du kommst.

12 nächste Seite »

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »