Kombinatorisch zählen < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:20 Fr 30.12.2005 | | Autor: | kuminitu |
Hallo,
Habe hier zwei Aufgaben mit denen ich leider nicht weiterkomme:
1)
Betrachtet natürliche Zahlen mit streng monoton aufsteigender Folge von positiven (Zehner-)Ziffern, z.B.148,235789. Führende Nullen sind nicht erlaubt. Wieviele solcher Zahlen gibt es?
2)
Wie viele monotone Wege gibt es in einem Gitter mit Kantenlängen 7×5 zwischen den diagonal gegenüberliegenden Eckpunkten A und Z
(wobei Punkt A links unten und Z rechts oben liegt)?
Monoton meint, dass der Weg von jedem besuchten Gitterpunkt aus nur nach rechts oder oben verlaufen darf, nicht nach links oder unten.
Ich komme im Moment auf keine Lösung, man soll alle ergebnisse
kombinatorisch mit begründung lösen.
wäre schon wenn mir jemand helfen könnte!
MFG
kuminitu
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:39 Fr 30.12.2005 | | Autor: | felixf |
> Hallo,
>
> Habe hier zwei Aufgaben mit denen ich leider nicht
> weiterkomme:
Wie weit bist du bei den Aufgaben denn gekommen? Hast du irgendwelche Ideen, Ansaetze, Ueberlegungen?
> 1)
> Betrachtet natürliche Zahlen mit streng monoton
> aufsteigender Folge von positiven (Zehner-)Ziffern,
> z.B.148,235789. Führende Nullen sind nicht erlaubt.
> Wieviele solcher Zahlen gibt es?
Nun, schau dir mal die Menge $A := [mm] \{ 1, 2, 3, 4, 5, 6, 7, 8, 9 \}$ [/mm] an. Faellt dir ein Zusammenhang zwischen solchen 'aufsteigenden' Zahlen und gewissen Teilmengen von $A$ auf?
> 2)
> Wie viele monotone Wege gibt es in einem Gitter mit
> Kantenlängen 7×5 zwischen den diagonal gegenüberliegenden
> Eckpunkten A und Z
> (wobei Punkt A links unten und Z rechts oben liegt)?
> Monoton meint, dass der Weg von jedem besuchten
> Gitterpunkt aus nur nach rechts oder oben verlaufen darf,
> nicht nach links oder unten.
Jeder Weg ist eindeutig durch eine Folge der Laenge 7 + 5 mit Eintraegen [mm] $\{ h, r \}$ [/mm] (hoch, rechts) bestimmt. Jetzt musst du dir ueberlegen, welche solche Folgen zu gueltigen Wegen gehoeren (du musst ja schliesslich von unten links nach oben rechts kommen). Die Bedingung an die Wege kannst du genau charakterisieren, und dies fuehrt zu einer Charakterisierung von Teilmengen von [mm] $\{ 1, 2, 3, \dots, 7 + 5 \}$, [/mm] welche genau den Wegen entsprechen. Wenn du diese gefunden hast kannst siehst du auch die Loesung (hoffentlich).
LG & HTH, Felix
|
|
|
|
