www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

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:

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 ^
www.vorhilfe.de