Treppenlauf < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Für zwei natürliche Zahlen m, n sei ein Gitte mit m + 1 horizontalen und n + 1 vertikalen Linien gegeben. Ein (n, m)-Treppenlauf ist eine Möglichkeig vom Gitterpunkt (0, 0) (links unten) zum Gitterpunkt (n, m) rechts oben) zu gelangen, indem man immer entweder einen Schritt nach rechts oder einen nach oben macht. Wieviele (n, m)-Treppenläufe gibt es? |
Ehrlich gesagt fällt mir hier leider nichts brauchbares ein, könnt ihr mir da ein paar Tipps geben ?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo bluepeople,
> Für zwei natürliche Zahlen m, n sei ein Gitte mit m + 1
> horizontalen und n + 1 vertikalen Linien gegeben. Ein (n,
> m)-Treppenlauf ist eine Möglichkeig vom Gitterpunkt (0, 0)
> (links unten) zum Gitterpunkt (n, m) rechts oben) zu
> gelangen, indem man immer entweder einen Schritt nach
> rechts oder einen nach oben macht. Wieviele (n,
> m)-Treppenläufe gibt es?
> Ehrlich gesagt fällt mir hier leider nichts brauchbares
> ein, könnt ihr mir da ein paar Tipps geben ?
Das ist keine leichte Aufgabe.
Es macht Sinn sich erstmal etwas in dieser Richtung zu überlegen:
Wir stellen uns die Punkte des Gitters mit ganzzahligen x- und y-Koordinaten vor. Das Gitter hat die Höhe m. Ein Treppenlauf bewegt sich also genau m Schritte nach oben. Nun ist die Frage: Wie können wir diese m 'Steigungsschritte' auf die n+1 Wegpunkte in x-Richtung (das ist die Menge W der x-Koordinaten des Gitters [mm] \{0,1,\ldots,n\}) [/mm] verteilen?
Die Anzahl an Möglichkeiten dafür ist äquivalent zur gesuchten, da die waagerechten Verbindungen durch eine jede dieser Verteilungen eindeutig bestimmt sind.
Die Anzahl der Möglichkeiten, die m Höhenschritte auf die n+1 Elemente der Menge W aufzuteilen, ist die Anzahl der Zerlegungen der Zahl m in n+1 (nichtnegative ganzzahlige) Summanden. Dabei ist die Reihenfolge relevant. Bezeichnen wir diese mit S(m,n+1). Hier kommt nun die Hauptarbeit. Wir müssen Eigenschaften von S finden.
Es ist klar, dass S(0, n)=0, denn die einzige Möglichkeit ist [mm] 0=\underbrace{0+0+\ldots+0}_{n \text{ mal}}.
[/mm]
Ferner ist S(1, n)=n, denn in der Zerlegung kann die 1 an n verschiedenen stellen stehen.
Hm, nun könnte man versuchen ein paar rekursive Abhängigkeiten zu bestimmen. Mir ist z. B. aufgefallen
[mm] S(m,n+1)=\sum_{i=0}^mS(m-i,n) [/mm]
Ich werde mich noch ein bisschen mit der Aufgabe beschäftigen, da ich sie sehr interessant finde. Man kann sich hier sicherlich sehr viel herleiten. Es kommt letztendlich drauf an, in welcher Form du die Aufgabe lösen musst.
Hattet ihr schon ähnliche Probleme behandelt? Ist das eine Olympiadeaufgabe?
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
Gruß
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:13 So 27.02.2011 | | Autor: | Teufel |
Hi!
Sei z.B. n=2, m=3.
Dann kann man einen Treppenlauf so darstellen:
ROORO, wobei R heißt, dass man eben nach rechts geht, O nach oben.
Oder RROOO, OORRO, ...
Jede Zeichenkette, die aus 3 Os und 2 Rs besteht, steht also genau für einen Weg (und umgedreht, ein Weg kann man eindeutig als solch eine Zeichenkette schreiben).
Also musst du nur zählen, wie viele solcher Zeichenketten es gibt. Und dafür habt ihr sicher eine Formel.
|
|
|
| |
|
Danke für den Hinweis, er hat mir geholfen etwas ein wenig mehr zu verstehen (+ die Lösung eines Freundes):
Das ist wie eine eine Multimenge:
Wir haben eine Menge mit m O's und n R's
=> [mm] \vektor{n + m \\ n} [/mm] = [mm] \vektor{n + m \\ m}
[/mm]
Das ist die Lösung. Nur eine Frage hab ich noch als Verständnis: Warum gerade wird bei diesem Binomialkoeffizienten unten n bzw. m genommen und nichts anderes. Das konnte ich mir leider nicht erklären bisher. Wäre nett wenn ihr mir das erklären könntet...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:47 Mo 28.02.2011 | | Autor: | Teufel |
Hi!
Genau.
Also du hast ja m+n Zeichen (z.B. m Os und n Rs oder umgedreht), von denen eben n untereinander gleich sind und m untereinander gleich sind.
Willst du die m+n Zeichen rumpermutieren, hast du dafür (n+m)! Möglichkeiten. Weil aber, wie gesagt, n und m unter ihnen gleich sind, musst du (n+m)! noch durch n! und durch m! teilen.
Daher hast du [mm] \bruch{(n+m)!}{n!*m!}=\vektor{n+m \\ n} [/mm] als Ergebnis.
Eine andere Sichtweise ist folgende:
Du hast n+m Xe vor dir liegen. Nun willst du m von diesen Xen in Os verwandeln und die restlichen n in Rs (denn so kriegst du ja auch eine gewünschte Zeichenkette raus).
Dazu musst du nur wissen, auf wie viele Arten du m Xe von diesen n+m Xen raussuchen kannst, die du in Os verwandelst (der Rest wird dann zu Rs). Da die Reihenfolge auch egal ist, hast du auch hier den Binomialkoeffizienten [mm] \vektor{n+m \\ m}=\vektor{n+m \\ n}, [/mm] der dir ja genau angibt, auf wie viele Arten du m Elemente aus m+n raussuchen kannst.
|
|
|
|
