n ueber k - kuerzeste Wege < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 02:25 Do 23.12.2004 | | Autor: | orpicos |
Hallo Zusammen,
Ich hab' das Forum hier bei der Suche nach Hilfe in fragen Mathe gefunden, und erst mal ein wenig "herumgeschnüffelt", also erst einmal ganz großes lob und Dank (ist wirklich interressant und hilfreich).
Ich hoffe, dass mir jemand helfen kann das hier zu verdauen:
Man soll beweisen:
[mm] {m+n \choose k}=\summe_{k=0}^{m}{m \choose k}{n \choose k}[/mm]
Als hilfe war in der Übungsaufgabe ein NxN Gitter gegeben.
Der Startpunkt ist (0,0) Endpunkt (m,n).
Gefragt ist nach der Anzahl der kürzesten Wege vom Startpunkt zum Endpunkt. Mir ist klar das alle kürzesten Wege nur aus schritten nach rechts und nach oben bestehen. (Im Skript hab ich dann den Hinweis mit der 01-Kodierung gefunden). Wenn man jetzt Alle Wege der Länge m+n nimmt und daraus nur die betrachtet die genau n 1sen aufweisen erhällt man die Anzahl der Kürzesten wege als:
[mm]{m+n \choose n}[/mm] für m>n.
Und hier verstehe ich nix mehr... (warum?)
Ich hab mir das Gitter also mal als gerichteten Graphen aufgezeichnet. Jeder Punkt erhällt einen Pfeil zu dem darüberliegenden und zu dem rechten. Ich habe dann in der oberen rechten Ecke angefangen die Punkte mit der Anzahl der Wege zum Endpunkt zu versehen. also für (m-1,n)=1
(m,n-1)=1, für (m-1,n-1)=#(m-1,n)+#(m,n-1), usw... bis zum Startpunkt.
Laut meiner Logik steht dann im Startpunkt die Anzahl der kürzesten Wege vom Startpunkt zum Endpunkt. Wenn a die Anzahl vom rechten Punkt und b die Anzahl vom oberen punkt ist hab ich von a+b mögliche kürzeste Wege.
Beim Ausprobieren komm ich aber nicht auf [mm]{m+n \choose n}[/mm] sondern auf [mm]{m+n+1 \choose n}[/mm]
Und nun bin ich total verwirrt.
Also zum Beispiel gibt es in einem 3x3 Gitter 6 kürzeste Wege von (0,0) nach (2,2).
Halte ich mich an die Formel aus dem Skript erhalte ich [mm]{4 \choose 2}=3[/mm] nehme ich (1,1) als Startpunkt und (3,3) erhalte ich [mm]{6 \choose 3}=10[/mm] was auch keinen Sinn ergibt.
mit [mm]{m+n+1 \choose n}[/mm] [mm] \wedge [/mm] m=2, n=2 erhalte ich [mm]{5 \choose 2}=6[/mm] was auch meinen Erwartungen entspricht.
Kann mir vielleicht jemand hier auf die Sprünge helfen wo mein Denkfehler liegt, oder ob ich doch noch nicht am Ende bin, aber dann auch nicht weiß wie ich mit dieser Hilfe den obrigen Zusammenhang beweisen soll...
Vielen Dank schon mal an alle die sich die Mühe gemacht habeen das ganze hier zu lesen und vielleicht einen Tip für mich haben.
euer,
Tobias
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
PS: Ich hab' die Frage mal mit 48h dringlich hereingestellt, bin aber auch danach noch über jede Antwort dankbar. Mein Problem ist nur das ich am 09.02 eine Prüfung hab' und total unter (wenn auch selbstverschuldetem) Zeitdruck stehe und mir eine schnelle Antwort natürlich sehr lieb wäre...
|
|
| |
|
Hallo Tobias!
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> Ich hab' das Forum hier bei der Suche nach Hilfe in fragen
> Mathe gefunden, und erst mal ein wenig "herumgeschnüffelt",
> also erst einmal ganz großes lob und Dank (ist wirklich
> interressant und hilfreich).
Danke 
> Ich hoffe, dass mir jemand helfen kann das hier zu
> verdauen:
> Man soll beweisen:
> [mm]{m+n \choose k}=\summe_{k=0}^{m}{m \choose k}{n \choose k}[/mm]
Ich nehme an, dass links $n$ statt $k$ stehen sollte.
> Als hilfe war in der Übungsaufgabe ein NxN Gitter
> gegeben.
Was ist hier $N$? Tut wohl nichts weiter zur Sache...
> Der Startpunkt ist (0,0) Endpunkt (m,n).
Aha
> Gefragt ist nach der Anzahl der kürzesten Wege vom
> Startpunkt zum Endpunkt. Mir ist klar das alle kürzesten
> Wege nur aus schritten nach rechts und nach oben bestehen.
> (Im Skript hab ich dann den Hinweis mit der 01-Kodierung
> gefunden). Wenn man jetzt Alle Wege der Länge m+n nimmt
> und daraus nur die betrachtet die genau n 1sen aufweisen
> erhällt man die Anzahl der Kürzesten wege als:
> [mm]{m+n \choose n}[/mm] für m>n.
>
> Und hier verstehe ich nix mehr... (warum?)
Bleibt man in der Sprache der 01-Kodierung, so kann man ja jeden kürzesten Weg als Tupel der Länge $m+n$ schreiben, wobei 0 bedeutet, nach rechts zu gehen und 1, nach oben zu gehen. Wie Du schon richtig bemerkt hast, muss dieses Tupel genau $n$ Einsen enthalten, und die Frage ist nur noch, wie viele Möglichkeiten es gibt, diese Einsen in dem Tupel zu platzieren. Nach den Regeln der Kombinatorik ist diese Anzahl gerade
[mm]{m+n \choose n}[/mm]
(Reihenfolge der Einsen spielt ja keine Rolle).
Die Bedingung $m>n$ ist merkwürdig, wenn ich die Formel von oben betrachte. Dort sollte [mm] $m\le [/mm] n$ sein, damit man alle $k$'s auch einsetzen kann. Für die Überlegungen bisher ist diese Einschränkung aber nicht wichtig.
> Ich hab mir das Gitter also mal als gerichteten Graphen
> aufgezeichnet. Jeder Punkt erhällt einen Pfeil zu dem
> darüberliegenden und zu dem rechten. Ich habe dann in der
> oberen rechten Ecke angefangen die Punkte mit der Anzahl
> der Wege zum Endpunkt zu versehen. also für (m-1,n)=1
> (m,n-1)=1, für (m-1,n-1)=#(m-1,n)+#(m,n-1), usw... bis zum
> Startpunkt.
> Laut meiner Logik steht dann im Startpunkt die Anzahl der
> kürzesten Wege vom Startpunkt zum Endpunkt. Wenn a die
> Anzahl vom rechten Punkt und b die Anzahl vom oberen punkt
> ist hab ich von dem betrachteten Punkt aus a+b mögliche kürzeste Wege.
![[ok]](/images/smileys/ok.gif "[ok]")
> Beim Ausprobieren komm ich aber nicht auf [mm]{m+n \choose n}[/mm]
> sondern auf [mm]{m+n+1 \choose n}[/mm]
> Und nun bin ich total
> verwirrt.
> Also zum Beispiel gibt es in einem 3x3 Gitter 6 kürzeste
> Wege von (0,0) nach (2,2).
Korrekt.
> Halte ich mich an die Formel aus dem Skript erhalte ich
> [mm]{4 \choose 2}=3[/mm]
![[verwirrt]](/images/smileys/verwirrt.gif "[verwirrt]")
[mm]{4 \choose 2}=\frac{4\cdot 3}{2\cdot 1}=6.[/mm]
Ist doch alles in Ordnung!
> nehme ich (1,1) als Startpunkt und (3,3)
> erhalte ich [mm]{6 \choose 3}=10[/mm] was auch keinen Sinn ergibt.
![[notok]](/images/smileys/notok.gif "[notok]")
[mm]{6 \choose 3}=\frac{6\cdot 5\cdot 4}{3\cdot 2\cdot 1}=20.[/mm]
Hast Du vielleicht noch etwas Nachholbedarf beim Berechnen der Binomialkoeffizienten?
> mit [mm]{m+n+1 \choose n}[/mm] [mm]\wedge[/mm] m=2, n=2 erhalte ich [mm]{5 \choose 2}=6[/mm]
> was auch meinen Erwartungen entspricht.
[mm]{5 \choose 2}=10[/mm]
> Kann mir vielleicht jemand hier auf die Sprünge helfen wo
> mein Denkfehler liegt, oder ob ich doch noch nicht am Ende
> bin, aber dann auch nicht weiß wie ich mit dieser Hilfe den
> obrigen Zusammenhang beweisen soll...
Vielleicht nimmst Du mit den neuen Erkenntnissen noch mal einen neuen Anlauf.
Viel Erfolg
Brigitte
|
|
|
|
![[prost]](/images/smileys/prost.gif "[prost]"){kind=small}
