Hallo.
Ich möchte berechnen, wieviele Möglcihkeiten es gibt um Streckennetze zwischen x Punkten zu erstellen. Dabei wird immer von einem Startpunkt ausgegangen, der definiert ist.
Von jedem Punkt dürfen beliebig viele Verbindungen ausgehen.
Beispiel: (A ist immer der Startpunkt)
Bei 2 Punkten (A, B) gibt es nur die eine Möglichkeit:
= 1 Möglichkeit
Bei 3 Punkten (A, B, C) gibt es die Möglichkeiten:
= 3 Möglichkeiten
Bei 4 Punkten (A .. D) gibt es:
Code:
B
|
A-C
|
D
A-B-D A-B
| |
C C-D
A-B-C A-B
| |
D D-C
A-C-B A-C
| |
D D-B
A-B-C A-B-C-D A-B-D-C
|
D
A-C-B A-C-B-D A-C-D-B
|
D
A-D-B A-D-B-C A-D-C-B
|
C
= 16 Möglichkeiten
aber wie zum Teufel kann man das berechnen?
mitn bissl warscheinlichkeitslehren-rechnen hab ich schon n kleinen formelansatz:
für 2 punkte gibt es
(also ein startpunkt * ein von ein mögl. restpunkte)
für 3 punkte gibt es
Code:
1 * [ (2 über 2)
+(2 über 1)*(1 über 1) ] = 3
(erklärung: ein startpunkt * (entweder: 2 von 2 mögl. restpunkten anfahren, [plus] oder: (1 von 2 mögl. restpunkten anfahren) * (1 von 1 mögl. restpunkten anfahren))
für 4 punkte gibt es
?? ich komm nichtmehr weiter, ich kapier die systematik nicht ganz
wär super wenn jmd das problem bzw. n lösungsansatz kennt!
PS: ich hab mit einem programm berechnet wieviel es geben muss (mit ner rekursiven fuktion)
dabei kommen folgende ergebnisse raus:
2 pkt = 1 mögl
3 pkt = 3 mögl
4 pkt = 16 mögl
5 pkt = 137 mögl
6 pkt = 1716 mögl
7 pkt = 29317 mögl
8 pkt = 650854 mögl
9 pkt = 18144065 mögl.