Anzahl von Gitterpfaden < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 11:01 Sa 05.12.2015 | | Autor: | derriemann |
| Aufgabe | Anzahl der Gitterpfade unterhalb der Diagonale von (0,0) nach (m,n), (m und n teilerfremd) gleich
[mm] \bruch{1}{m+n}\vektor{m+n \\ m} [/mm] |
Hallo liebe Mathefreunde,
ich sitze schon einige Zeit an dieser Gleichung und versuche diese zu beweisen.
Was ich weiss:
Anzahl der Gitterpfade von (0,0) nach (n,n) unterhalb oder auf der Diagonalen [mm] =\bruch{1}{n+1}\vektor{2n \\ n}
[/mm]
Anzahl der Gitterpfade von (0,0) nach (m,n) oberhalb oder auf der x-Achse = [mm] \bruch{m+1-n}{m+1}\vektor{m+n \\ m}
[/mm]
Hat jemand eine Ahnung, wie man jetzt darauf kommt?
Viele Grüße
|
|
| |
|
> Anzahl der Gitterpfade unterhalb der Diagonale von (0,0)
> nach (m,n), (m und n teilerfremd) gleich
> [mm]\bruch{1}{m+n}\vektor{m+n \\ m}[/mm]
> Hallo liebe
> Mathefreunde,
>
> ich sitze schon einige Zeit an dieser Gleichung und
> versuche diese zu beweisen.
> Was ich weiss:
> Anzahl der Gitterpfade von (0,0) nach (n,n) unterhalb oder
> auf der Diagonalen [mm]=\bruch{1}{n+1}\vektor{2n \\ n}[/mm]
> Anzahl
> der Gitterpfade von (0,0) nach (m,n) oberhalb oder auf der
> x-Achse = [mm]\bruch{m+1-n}{m+1}\vektor{m+n \\ m}[/mm]
>
> Hat jemand eine Ahnung, wie man jetzt darauf kommt?
>
> Viele Grüße
Hallo derriemann
Ich denke, es sollte noch definiert werden, was unter einem
"Gitterpfad" von A nach B genau zu verstehen ist.
Das Gitter soll sicher das der Punkte (x,y) mit [mm] x\in\IZ [/mm] und [mm] y\in\IZ [/mm] sein.
Ein "Pfad" von (0,0) nach (m,n) soll vermutlich ein Streckenzug
aus genau m+n Einheitsstrecken sein, der in (0,0) beginnt
und in (m,n) endet. Gemeint sind also wohl nur "kürzeste
Pfade" in dieser "Taxigeometrie".
Falls m und n beide positiv sind, führt also jede Einzelstrecke
eines solchen Pfades in der x-y-Ebene entweder nach rechts
oder nach oben und nie nach links oder unten.
Die Voraussetzung, dass m und n teilerfremd sein sollen,
führt dann dazu, dass jeder derartige kürzeste Pfad außer
seinem Startpunkt (0,0) und dem Endpunkt (m,n) lauter
Zwischenpunkte (x,y) mit $\ [mm] 0\le [/mm] y < x [mm] *\frac{n}{m}$ [/mm] hat.
LG , Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion | | Datum: | 13:31 Sa 05.12.2015 | | Autor: | derriemann |
Hi, danke für die Antwort!
Ok, das Prinzip ist mir jetzt schon ein wenig klarer, nur bin ich die ganze Zeit am rumprobieren, wie ich diese Ungleichungen richtig benutzen kann, um den obigen Ausdruck zu erhalten.
Also als erstes gibt es ja [mm] \vektor{m+n \\ m} [/mm] Gitterpfade von (0,0) nach (m,n). Nun muss ich die Einschränkung noch einarbeiten. Das ist irgendwie nur recht schwierig, wüsste jetzt nicht, wie ich die Bedingungen da reinquetschen kann
|
|
|
| |
|
Hallo,
kurzer Zwischenruf:
> Also als erstes gibt es ja [mm]\vektor{m+n \\ m}[/mm] Gitterpfade
> von (0,0) nach (m,n).
Das kann nicht sein, da der Ausdruck nicht symmetrisch in m,n ist!
Mit anderen Worten: die Zahl der Gitterpfade von (0,0) nach (n,m) muss doch genausogroß sein.
Grüße
rev
|
|
|
| |
|
> Hallo,
>
> kurzer Zwischenruf:
>
> > Also als erstes gibt es ja [mm]\vektor{m+n \\ m}[/mm] Gitterpfade
> > von (0,0) nach (m,n).
>
> Das kann nicht sein, da der Ausdruck nicht symmetrisch in
> m,n ist!
> Mit anderen Worten: die Zahl der Gitterpfade von (0,0)
> nach (n,m) muss doch genausogroß sein.
>
> Grüße
> rev
Hallo reverend,
da nötigst du mich aber auch zu einem kleinen Zwischenruf:
Es gilt doch: [mm] $\pmat{m+n\\m}\ [/mm] =\ [mm] \pmat{m+n\\(m+n)-m}\ [/mm] =\ [mm] \pmat{m+n\\n}\ [/mm] =\ [mm] \pmat{n+m\\n}$
[/mm]
Naja, die Rute lassen wir zur Feier des Tages mal sein ...
Schönen Abend !
Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:06 So 06.12.2015 | | Autor: | reverend |
Hallo Al,
ähem.
Da hast du natürlich Recht!
Grüße
rev
|
|
|
| |
|
den Gedanken hatte ich aber anfangs auch 
Nur wie kann man denn da jetzt die Bedingung verarbeiten? Hatte es heute nochmal versucht, aber leider ein wenig glücklos........................
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:20 Di 08.12.2015 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:20 Fr 11.12.2015 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
