Wieviele Verbindungen gibt es bei x Punkten?

[StefanDP]

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:

Code:

A-B

= 1 Möglichkeit

Bei 3 Punkten (A, B, C) gibt es die Möglichkeiten:

Code:

A-B
|
C

A-B-C

A-C-B

= 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

Code:

1 * (1 über 1) = 1

(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.