Kombinationsmöglichkeiten errechnen?

[Homer]

Hallo!

Wie kann man ausrechnen, wieviele Kombinationsmöglichkeiten es gibt?

Man hat z.B. die Zahl 1,2,3, die könnte man so kombinieren:

1 || 2 || 3

1+2 || 1+3 || 2+3

1+2+3

Das wären 7 mögliche Kombinationen. Aber gibt es dafür eine Formel, damit ich ausrechnen kann wie das bei 9 Zahlen ausehen würde?

[MudGuard]

Hi,

Man hat z.B. die Zahl 1,2,3, die könnte man so kombinieren:
1 || 2 || 3
1+2 || 1+3 || 2+3
1+2+3

Also ohne Wiederholungen?

Sei n die Anzahl der Ziffern:

Einzelziffern: 1 aus n
Doppelte: 2 aus n
Dreifache: 3 aus n
...
n-fache: n aus n

wobei sich k aus n berechnet zu n! / ((n-k)! * k!)

Zusammen: Summe von 1 bis n über (n! / ((n-k)! * k!))

cu,
Andreas

[Vimes]

Moin,

ja die gibt es. Du suchst die Summe der Binomialkoeefizienten,
denn du suchst die Summe,
 aus n Elementen genau 1 auszuwählen (n über 1)

• aus n Elementen genau 2 auszuwählen (n über 2)
• aus n Elementen genau 3 auszuwählen (n über 3)
• aus n Elementen genau n auszuwählen (n über n)

nun gilt: Summe (k=0 bis k=n) (n über k)=2^n.

Da du aber nur
  Summe (k=1 bis k=n) (n über k)
ausrechnen willst, mußt du (n über 0)=1 abziehen
ERGO:

Die Anzahl der Kombinationen ist 2^n - 1
in deinem Beispiel n=3 -> 2^3=8 8-1=7 voila!

[Homer]

Danke für die beiden Antworten, auch wenn ich nichts verstanden habe!
Vielleicht könnte das jemand mit 9 (1 bis 9) Zahlen mal vorrechnen,
dann hätte ich zumindest schon mal das Ergebnis :)

[romy]

Hi,

Danke für die beiden Antworten, auch wenn ich nichts verstanden habe!

wer lesen kann ist klar im Vorteil!

Die Anzahl der Kombinationen ist 2^n - 1

in deinem Beispiel n=3 -> 2^3=8 8-1=7 voila!

was verstehst Du jetzt nicht?

ciao
romy

[Homer]

Die ganze Erklärung! Das für n, 3 eingestzt wurde habe ich mir fast gedacht, aber warum steht die 2 davor?

[mdkiller]

Die ganze Erklärung! Das für n, 3 eingestzt wurde habe ich mir fast gedacht, aber warum steht die 2 davor?

Reine Mathematik. Du wolltest doch die Formel haben, und die ist eben 2^n-1

Wenn du wissen willst, wieviele Kobinationsmöglichkeiten es gibt, wenn _alle_ Ziffern genau _einmal_ vorkommen: n!

[Homer]

Danke an alle für die Hilfe!

[Tom2]

Hi Homer

Die ganze Erklärung! Das für n, 3 eingestzt wurde habe ich mir fast gedacht, aber warum steht die 2 davor?

Wenn ich dich richtig verstanden habe, dann verstehst du die Zeichen (^,!) nicht.

Bei dem ^ geht es um Potenzen:

m^n (gesprochen: m hoch n), was nichts anderes bedetet, als das die Basis, m, n-mal mit sich selbst multipliziert wird. n heisst übrigens Exponent.

2^3 bedetet demzufolge 2*2*2

Bei den Bits und Bytes des Computers funktioniert das genau gleich: 1 Byte hat 8 Bit, wovon jedes zwei zustände annehmen kann. Daraus ergeben sich für ein Byte 2^8 verschieden kombinationsmöglichkeiten, was 256 ergibt.

Bei dem ! geht es um die Fakultät:

n! (gesprochen: n Fakultät) ist das Produkt aller natürlichen Zahlen von 1 bis n.

3! wäre somit 3*2*1 = 6.

MfG & HtH

Tom2

[Vimes]

moin.

Die ganze Erklärung! Das für n, 3 eingestzt wurde habe ich mir fast gedacht, aber warum steht die 2 davor?

Weil man eben 2^n-1 (sprich: 2 hoch n  minus 1 )ausrechnen muss.

http://mo.mathematik.uni-stuttgart.de/lexikon/B/binomialkoeffizient.html
Der Binomialkoeffizient (n,k) (sprich:n über k) gibt (in der Kombinatorik) an, wieviele Möglichkeiten es gibt, aus einer n-elementigen Menge eine k-elementige Menge zu ziehen, wobei die Reihenfolge keine Rolle spielt (d.h die Ziehungen (1,2) und (2,1) werden nur "einmal" gezählt).
wenn Du nun diese k Elemente aufschreibst und dazwischen ein + machst, hast du genau sowas wie du suchst.

Tabelle
n    Möglichkeiten
1    2^1-1=2-1=1
2    2^2-1=4-1=3
3    2^3-1=8-1=7
4    2^4-1=16-1=15
5    2^5-1=32-1=31
6    2^6-1=64-1=63
.    .
.    .
.    .

[Michael Schröpl]

Hi Homer,

Wie kann man ausrechnen, wieviele Kombinationsmöglichkeiten es gibt?

definiere "kombinieren".

Man hat z.B. die Zahl 1,2,3, die könnte man so kombinieren:
1 || 2 || 3
1+2 || 1+3 || 2+3
1+2+3

ein Beispiel ist keine Definition.

Meinen Kristallkugel sagt mir aber, daß Du bis auf die leere Menge (deren Weglassen Dir die inhärente Symmetrie des Problems verborgen hat) sämtliche Teilmengen einer dreielementigen Menge hingeschrieben hast.
Was Du suchst, das ist die Anzahl der Elemente der _Potenzmenge_ Deiner Ausgangsmenge - und deren Anzahl bei <n> Elementen ist 2 hoch <n>.

Das war die mathematische Lösung Deines Problems - nun diejenige eines Informatikers:

Um eine Teilmenge Deiner Menge als Datentyp darzustellen, könntest Du pro Mengenelement ein Boolean-Flag (0 oder 1 - "drinnen" oder "draußen") verwenden.
Für eine Menge mit <n> Elementen brauchst Du dann also <n> Flags, die sich - nebeneinander geklebt - dann als Binärzahl der Länge <n> Bit interpretieren lassen.

Viele Grüße
      Michael