matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 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
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheorieAnzahl von Gitterpfaden
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
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 ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]