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 :shock:


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.

[Aenogym]

hi,

(schlagt mich, falls ich voll daneben liege)
ich glaube, für solche probleme gibt es die Fakultät.
die fakultät von 9 zum beispiel ist:

1*2*3*4*5*6*7*8*9 = 9!

also immer das produkt der zahlen von eins bis zur gegebenen zahl.

edit: okay. *schmerz* ;)

aenogym

[StefanDP]

*schlag* ;)

das mit fakultät wär dann richtig, wenn jeder punkt nur einen folgepunkt hat.
jedoch ist die anzahl der folgepunkte für jeden punkt beliebig

[Eichhoernchen]

es müsste für 3 so aussehen wenn man Fakultät benutzen will:

Delphi-Quellcode:

A-B-C
A-C-B
B-A-C
B-C-A
C-B-A
C-A-B

[faux]

Würde es nicht genaugenommen bei 2 2 möglichkeiten geben?

Code:

A-B
B-A

Denn wenn man das mathematisch berechnen will, wird man das berücksichtigen müssen...

[jfheins]

Frage: Ist das für ihn ein Unterschied ?

z.B. bei der Frage: wieviele Isomere gibt es für Heptan sind die Atome nicht nummeriert, und es ist dir egal in welcher Reihenfolge die sind ;)

[StefanDP]

A-B ist gleich wie B-A

man könnte es so sagen:

beginnen wir in einem beliebigen punkt.
von diesem punkt aus können jetzt beliebig viele verbindungen zu noch nicht benutzen punkten gemacht werden. (man kann diesen punkt jetzt z.b. mit 1 weiterem punkt verbinden, mit 2, mit 3 oder auch mit keinem.
und genaus gehts dann weiter, also von allen neuen endpunkten können wieder beliebig viele verbindungen gemacht werden

das ganze gibt dann wie gesagt keine route (punkt 1, punkt 2, punkt 3...) sondern ein netz

[Eichhoernchen]

er sagt ja, er hat nen fest definierten startpunkt, aber dann verstehe ich nicht so ganz wie das hier klappen soll:

Delphi-Quellcode:

A-B  //ist hier a der startpunkt??? dann breitet sich die reihe nach links und nach rechts aus!!!!
|
C

A-B-C

A-C-B

für mich sieht das so aus:

(A-B) = 1 ne möglichkeit:

Delphi-Quellcode:

A-B

(A-B-C) = 2

Delphi-Quellcode:

A-B-C
A-C-B

(A-B-C-D) = 6

Delphi-Quellcode:

A-B-C-D
A-B-D-C
A-C-B-D
A-C-D-B
A-D-C-B
A-D-B-C

EDIT: Sorry ich hab das letzte Posting net gesehen, das hier vergessen!!

[DGL-luke]

*räusper*

Zitat:

(A-B-C) = 2
A-B-C
A-C-B

fehlt da nicht b-a-c?

im übrigen kommen wir doch hier fast schon an permutationen ran - welche abfolgen der buchstaben A,B und C gibt es?

nun, die per-hand-methode: ABC,ACB,BAC,BCA,CAB,CBA - also immer einen anderen buchstaben vorne hin, die hinteren durchwechseln. wenn man alle hat (n² | n=Anzahl Werte??? würde hier stimmen, denn 3²=6 die doppeltzen rausstreichen - oder auch nicht, da die reihenfolge ja wichtig sein kann.

Bitte widerlegt mich, falls das nicht stimmt.

[rascalpo]

also, wenn jeder "Knoten" maximal zwei Verbindungen haben kann, dann kann man es bei N Knoten mit N! berechnen.

Jeder Knoten hat aber maximal 3 Verbindungen.
Falls es einen Knoten gibt, der bevorzugt wird, und die Reihenfolge eine Rolle spielt, gibt es den Binärbaum (Wikipedia). Dieser is aber ein Sonderfall.

Falls es beliebige Anzahl (n) von Knoten gibt:

Delphi-Quellcode:

Verbindungen := 0;
for i := 1 to n do Verbindungen := Verbindungen +(i - 1);