infostudium.de

von **bugs** » 21.02.07 14:00

wie geht man denn am einfachsten an solche aufgaben ran?

zu zeigen oder widerlegen:
$\sum_{i=0}^{n} \sum_{k=0}^{i} {n+k \choose i} = \sum_{i=0}^{n} \sum_{k=0}^{i} {n+k \choose n +2k - i}$

von **philipp** » 21.02.07 14:43

Also du musst viele Sachen beachten:
Es ist egal wierum die Summen laufen, du kannst also beliebig
$k$ durch $i - k$
und $i$ durch $n-i$ ersetzen. (Musst es natuerlich dann ueberall gleichzeitig ersetzen)

Ausserdem ist
${n \choose k} = {n \choose {n-k}}$

Also:
${{n+k} \choose i} = {{n+k} \choose {n+k-i}} \stackrel{\wedge}{=} {{n+k} \choose {n+k-(i-k)}} = {{n+k} \choose {n+2k-i}}$

Dann wuesstest du, dass es dasselbe ist.

von **bugs** » 21.02.07 15:31

hm ... ok, aber laut musterlösung der MC ist die von mir aufgestellte aussage falsch

von kb » 21.02.07 16:09

richtig, denn das stimmt nicht:

philipp hat geschrieben: ${{{n+k} \choose {n+k-i}} \stackrel{\wedge}{=} {{n+k} \choose {n+k-(i-k)}}}$

setzte für alle 2 ein. ${{4} \choose {2}} \not = {{4} \choose {4}}$

bei der Aufgabe kannst du einen widerspruch einfach durch Einsetzen von n=i=1 herleiten.

von **bugs** » 21.02.07 16:41

naja, ich glaube bei der ersten kann man das auch ziemlich schnell sehen, wenn man nur die symmetrie des binomialkoeffizienten ausnutzt:

${n \choose k} = {n \choose n-k}$

$\Rightarrow {n + k \choose i} = {n+k \choose n+k-i} \not= { n+k \choose n+2k-i}$

aber wie ist das zb bei

$\sum_{k=1}^{n}\sum_{l=1}^k e^k\cdot\pi^l = \sum_{l=1}^{n} \cdot \sum_{k=1}^l e^{n-l+k} \cdot \pi^{n-l+1}$

das soll laut MC-Lösung stimmen

von **philipp** » 21.02.07 18:29

philipp hat geschrieben:...und $i$ durch $n-i$ ersetzen.

philipp hat geschrieben:Also:
${{n+k} \choose i} = {{n+k} \choose {n+k-i}} \stackrel{\wedge}{=} {{n+k} \choose {n+k-(i-k)}} = {{n+k} \choose {n+2k-i}}$

Ist natuerlich Mist weil ich es durch n-i haette ersetzen muessen.

edit: Hm verdammt ich muss das nochmal ueberdenken. Poste meine Ergebnisse dann hier

edit: Ok, also wenn die Summen so laufen:
$\sum_{a=0}^{n}\sum_{b=0}^a$
Kann man diese Ersetzungen vornehmen, ohne die Summe zu ändern:
Entweder: $b \to a-b$
oder: $b \to n-a \text{ und } a \to n-b$
Es muesste noch eine dritte Mglk. geben, aber ich komm grad nicht drauf.
Ihr koennt euch das ganz gut in sonem Dreieck vorstellen. Sind ja quasi nur zwei for-Schleifen

Aufpassen muss man wenn es nicht bei 0 losgeht:
$\sum_{a=1}^{n}\sum_{b=1}^a$
Entweder: $b \to a+1-b$
oder: $b \to n+1-a \text{ und } a \to n+1-b$

Und mit dieser Ersetzung haut's dann auch mit dem $e \pi$ ding hin:
Also erstmal schreibe ich einfach die Variablennamen auf der rechten Seite um. Aendert ja schonmal gar nix: (k und l in der gesamten Summe vertauschen, damit die Summen vorne schonmal gleich sind)
Zu zeigen: $\sum_{k=1}^{n}\sum_{l=1}^k e^k\cdot\pi^l = \sum_{k=1}^{n} \sum_{l=1}^k e^{n-k+l} \cdot \pi^{n-k+1}$

Jetzt schreibe ich den linken Teil mit den obigen Regeln um:
$\sum_{k=1}^{n}\sum_{l=1}^k e^k\cdot\pi^l = \sum_{k=1}^{n}\sum_{l=1}^k e^{n+1-l}\cdot\pi^{n+1-k}$ (Die zweite Regel).

Jetzt die erste Regel:
$\sum_{k=1}^{n}\sum_{l=1}^k e^{n+1-l}\cdot\pi^{n+1-k} = \sum_{k=1}^{n}\sum_{l=1}^k e^{n+1-(k+1-l)}\cdot\pi^{n+1-k}= \sum_{k=1}^{n}\sum_{l=1}^k e^{n-k+l}\cdot\pi^{n+1-k}$
Und das ist das ist das wo wir hinwollten. Gezeigt.

von **bugs** » 21.02.07 22:30

weißt du vielleicht auch, warum man das so ersetzen darf? das habe ich bisher nicht so ganz verstanden ...

von **Muffi** » 21.02.07 23:28

Ganz kurz: Weil es egal ist, ob man n + (n-1) + (n-2) + ... + 2 + 1 oder 1 + 2 + ... + (n-2) + (n-1) + n rechnet. Für die innere Summe wird das ganz schnell klar, für die äußere dann mit dem Verständnis auch.

von **philipp** » 21.02.07 23:31

Ja das dumme ist, dass ich mir das auch nur so ueberlegt habe und es schon verdammt logisch ist, ich aber keinen Beweis habe.

Aber mach dir mal ne Tabelle mit Zeilen und Spalten 0 bis 4 zum Beispiel.
x-Koordinate mit a und y-Koordinate mit b bezeichnet.
Jede Zelle sei ein Summand.
Mach einmal das hier:
$\sum_{a=0}^{4}\sum_{b=0}^a markiere(a,b)$

einmal das hier:
$\sum_{a=0}^{4}\sum_{b=0}^a markiere(a,a-b)$

und einmal das hier:
$\sum_{a=0}^{4}\sum_{b=0}^a markiere(n-b,n-a)$

Und du wirst sehen, du markierst immer dieselben Summanden, nur in einer anderen Reihenfolge.

infostudium.de

Forum zum Informatikstudium an der RWTH Aachen

[Diskrete] MC 4.5 umsummieren oder doppeltes Abzählen

MC 4.5 umsummieren oder doppeltes Abzählen