Kombinatorik - Anzahl Pfade der Länge n bestimmen?

Question

Aufgabe:

(1.) Bestimme die Anzahl der Pfade von 1 nach 3 der Länge 7 sowie (2.) die Anzahl der Pfade von 1 nach 7 der Länge 9.

Problem/Ansatz:

Definition Länge Pfad: Die Länge eines Pfades v0 , v1 , . . . , vl ist l, d.h. die Anzahl der Kanten (Schritte), von v0 bis vl.

Nach der Definition gibt es doch für die erste Teilaufgabe gar keine Pfade die lang genug sind, da der längste mögliche Pfad | (1,1),(1,2),(2,2),(2,3)(3,3) |= 5 ist?

Was verstehe ich falsch? Ich habe für "0" keine Punkte bekommen.

Answer 1

Du kannst hier beliebig viele (1,1), (2,2), (3,3) einschieben bzw. anhängen und damit auch Pfade beliebiger Länge erhalten.

U.a. | (1,1),(1,2),(2,2),(2,3)(3,3),(3,3),(3,3) | =7

oder | (1,1),(1,1),(1,2),(2,2),(2,2),(2,3)(3,3) | =7.

Comments

Ah danke!

Dann hab ich ein Urnen Problem mit (nach (1,2) (2,3)) 5 übrigen Schritten/Bällen auf 3 Zahlen/Urnen und komme auf (5+2) über 5 also 21 mögliche Pfade richtig?

---

Ja, stimmt, 21.

Answer 2

Bestimme

1) die Anzahl der Pfade von 1 nach 3 der Länge 7.

(7 über 3 - 1) = (7 über 2) = 7*6/2 = 21

2) die Anzahl der Pfade von 1 nach 7 der Länge 9.

(9 über 7-1) = (9 über 6) = (9 über 3) = 9*8*7/6 = 84