www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Graphentheorie" - Anzahl von Gitterpfaden
Anzahl von Gitterpfaden < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Anzahl von Gitterpfaden: Idee
Status: (Frage) reagiert/warte auf Reaktion Status 
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

        
Bezug
Anzahl von Gitterpfaden: Definition "Pfad"
Status: (Antwort) fertig Status 
Datum: 11:45 Sa 05.12.2015
Autor: Al-Chwarizmi


> 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

Bezug
                
Bezug
Anzahl von Gitterpfaden: Frage (reagiert)
Status: (Frage) reagiert/warte auf Reaktion Status 
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

Bezug
                        
Bezug
Anzahl von Gitterpfaden: Antwort
Status: (Antwort) fertig Status 
Datum: 15:28 Sa 05.12.2015
Autor: reverend

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

Bezug
                                
Bezug
Anzahl von Gitterpfaden: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:38 Sa 05.12.2015
Autor: Al-Chwarizmi


> 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

Bezug
                                        
Bezug
Anzahl von Gitterpfaden: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:06 So 06.12.2015
Autor: reverend

Hallo Al,

ähem.
Da hast du natürlich Recht!

Grüße
rev

Bezug
                                                
Bezug
Anzahl von Gitterpfaden: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 15:47 So 06.12.2015
Autor: derriemann

:-)

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........................

Bezug
                                                        
Bezug
Anzahl von Gitterpfaden: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:20 Di 08.12.2015
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
                                                                
Bezug
Anzahl von Gitterpfaden: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 12:11 Mi 09.12.2015
Autor: derriemann

keiner? :-(

Bezug
                                                                        
Bezug
Anzahl von Gitterpfaden: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:20 Fr 11.12.2015
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]