anzahl möglicher Kombinationen berechnen

lordfritte

Lieutenant
Registriert
Juli 2006
Beiträge
955
Hallo! Ich stehe gerade ein wenig auf dem Schlauch.

Ich habe folgendes Problem: Ich habe z.b. 20 Optionen, jede Option kann AN oder AUS sein.
Wie viele verschiedene Möglichkeiten gibt es?
Die Reihenfolge spielt keine Rolle also A+B+C ist das gleiche wie C+A+B

Ich habe mich schon ein bisschen mit Google bemüht und bin auf "Kombinatorik" gestoßen, aber! So ganz verstehe ich das nicht. z.b. "M Elemente auszuwählen aus N Elementen." was bei mir wäre M und was wäre N?
 
Zuletzt bearbeitet:
Hi,

nachdem es quasi nur die Zustände "1" und "0" für jede Option gibt kann man sich das sehr schön in Bits, also Binär, vorstellen. Das sind einfach 20 Bits, die jeweils "1" oder "0" haben können. Die mögliche Anzahl wäre demnach wie tobisson richtig schreibt 2 hoch 20.

VG,
Mad
 
Wenn du mit
lordfritte schrieb:
Die Reihenfolge spielt keine Rolle also A+B+C ist das gleiche wie C+A+B
meinst, dass z.B. 001 das gleiche ist wie 100, ist 2^20 nicht die richtige Antwort
 
MoTKaD schrieb:
Wenn du mit

meinst, dass z.B. 001 das gleiche ist wie 100, ist 2^20 nicht die richtige Antwort
Wenn man das annimmt dann müsste die Lösung 21 sein.
Alle auf 0 = 1 Zustand
Alle Signalwerte von 1 - 20 = 20 Zustände

Lösung = 21
 
MoTKaD schrieb:
Wenn du mit

meinst, dass z.B. 001 das gleiche ist wie 100, ist 2^20 nicht die richtige Antwort

doch... 2^3 in deinem Beispiel, 8 möglichkeiten.

000
001
010
011
100
101
110
111

Stimmt schon so...
 
thecain schrieb:
doch... 2^3 in deinem Beispiel, 8 möglichkeiten.

000
001
010
011
100
101
110
111

Stimmt schon so...



001 = 010 = 100 ... dann nimm alles weg was du nicht brauchst und es sind ganz wenige Combos noch.

Da die Reihenfolge egal ist gibts 21 Schaltzustände ... alles aus und jeweils einen mehr an .
 
lordfritte schrieb:
Ich habe folgendes Problem: Ich habe z.b. 20 Optionen, jede Option kann AN oder AUS sein.
Wie viele verschiedene Möglichkeiten gibt es?
Die Reihenfolge spielt keine Rolle also A+B+C ist das gleiche wie C+A+B

Wie hier schon mehrfach richtig erwähnt wurde, ist das keine Kombinatorik sondern einfach die Frage, wie viele Schalter man "umlegen" kann. Wenn man 20 Schalter hat, kann man 20 Schalter umlegen + die Ausgangskonfiguration.
 
Hi,

Die Reihenfolge spielt keine Rolle also A+B+C ist das gleiche wie C+A+B

den Satz hatte ich gekonnt ignoriert, dann sind es tatsächlich nur 20 + Start Kombinationen und nicht mit Bits vergleichbar.

VG,
Mad
 
Leute, lesen, nachdenken verstehen. Es gibt 20 unterschiedliche Optionen (A, B, C...) Es ist egal in welcher Reihenfolge die gesetzt werden aber es ist doch nicht egal, ob Option A oder B gesetzt wurde. 2^20 ist also vollkommen richtig.

Soo und jetzt kann lordfritte kommen und mir sagen, dass ich die Angabe falsch verstanden habe. ;)
 
2^20 ist korrekt. Du hast 20 variablen mit jeweils 2 möglichkeiten, die UNABHÄNGIG voneinander sind, da multiplizieren sich die möglichkeiten.

Darf ich vermuten, dass du dann wahrscheinlichkeiten der art "es sind 7 schalter an" berechnen möchtest. Auf diese vermutung komme ich aufgrund deiner erwähnung k aus n auswählen. Denn dann musst du die möglichkeiten dieses ereignisses zählen. Für das erwähnte ist das 20 über 7, da egal welche 7 an sind. Und das teilst du duch die gesamtzahl der möglichkeiten 2^20. Also P (k schalter von insgesamt n schalter an)=n! / k! (n-k)! 2^n
 
@blöderidiot:
Es geht nicht nur darum, wie viele Optionen gesetzt sind, sondern auch welche. Er hat geschrieben, dass z.B. A+B+C das gleiche ist wie C+A+B, nicht, dass A+B das gleiche wie B+C ist jetzt überleg mal, wie viele Kombinationen du aus den Buchstaben A bis T bilden kannst, selbst wenn du die Reihenfolge der Buchstaben nicht berücksichtigst (Nur A, nur B, nur C, ..., A und B, A und C, A und D...).

Manchmal könnte man echt glauben, die Leute können nur Aufgaben verstehen, wenn sie - wie in der Schule/ Studium - genau nach Schema F formuliert sind.

Entschuldige bitte meinen harten Tonfall.
 
Miuwa schrieb:
Er hat geschrieben, dass z.B. A+B+C das gleiche ist wie C+A+B, nicht, dass A+B das gleiche wie B+C ist jetzt überleg mal, wie viele Kombinationen du aus den Buchstaben A bis T bilden kannst, selbst wenn du die Reihenfolge der Buchstaben nicht berücksichtigst (Nur A, nur B, nur C, ..., A und B, A und C, A und D...).
Ich denke, Du lehnst Dich hier vielleicht etwas zu weit aus dem Fenster. Wenn ich mir sein Posting ansehe, sind mehrere Interpretationen möglich. Du willst es in diese Richtung deuten, dass unterschiedliche Positionen { 1 ... 20 } eines gesetzten Schalters auch unterschiedliche Zustände sind. Mann kann es aber auch so deuten, dass die Position egal ist und nur die Anzahl der Schalter entscheidet. Das solltest Du m. E. nach zugeben können. So lange der TE nicht genauer spezifiziert, was er meint, ist keine Aussage möglich.

Manchmal könnte man echt glauben, die Leute können nur Aufgaben verstehen, wenn sie - wie in der Schule/ Studium - genau nach Schema F formuliert sind.

Nö, ich denke mal, die "Aufgabe" lässt Interpretationsspielraum zu. Beide Deutungsvarianten sind wahrscheinlich. Ich kann auch akzeptieren, dass ich möglicherweise bei der Deutung falsch geraten habe.

Entschuldige bitte meinen harten Tonfall.
Hättest Du das nicht geschrieben, hätte ich es gar nicht gemerkt. Nun aber weiß ich, dass Du einen harten Tonfall gewählt hast!!!!!
 
blöderidiot schrieb:
Wie hier schon mehrfach richtig erwähnt wurde, ist das keine Kombinatorik sondern einfach die Frage, wie viele Schalter man "umlegen" kann. Wenn man 20 Schalter hat, kann man 20 Schalter umlegen + die Ausgangskonfiguration.

Genauer gesagt handelt es sich hierbei schon um Kombinatorik. Allgemein gibt es bei einer Menge mit n verschieden Elementen (hier n=2, da man die Elemente 0 und 1 hat), aus der k Elemente (hier k=20) ausgewählt werden bei sortiertem Ziehen mit Zurücklegen (n+k-1) über k Möglichkeiten (Binomialkoeffizient), also in diesem Fall 21 über 20 Möglichkeiten.

a über b lässt sich für a >= b auch schreiben als a!/(b!*(a-b)!), also in diesem Fall 21!/(20!*1!)=21!/20!=21 Möglichkeiten.

Gruß
Infi

Edit:
Miuwa schrieb:
Manchmal könnte man echt glauben, die Leute können nur Aufgaben verstehen, wenn sie - wie in der Schule/ Studium - genau nach Schema F formuliert sind.
Die Aufgabe ist doch nach Schema F formuliert, Reihenfolge egal entspricht sortiertem Ziehen/Kombination der Ergebnisse.
 
Zuletzt bearbeitet:
Eigentlich alles ganz einfach:

1. 21 Zustände gibt es nur dann, wenn jeweils nur eine Option aktiv sein kann und auch keine Option aktiv ist.
2. Für 20 Optionen mit An/Aus Zustand unter der Bedingung, dass die Reihenfolge keine Rolle spielt, gibt es 2^20 Möglichkeiten, da ja auch mehr als eine Option gleichzeitig aktiv sein kann. Im Binärformat ist die Reihenfolge gar nicht kodiert.
3. Würde die Reihenfolge eine Rolle spielen gäbe es für 3 Optionen beim Ziehen unter Beachtung der Reihenfolge A, B, C, AB, AC, BA, BC, CA, CB, ABC, ACB, BAC, BCA, CAB, CBA und 0 als keinen aktiven Zustand, insgesamt also 16 Zustände. Das entspricht 1+3!/(3-1)!+3!/(3-2)!+3!/(3-3)! oder für n: 1 + sum_{i=1}^n n!/(n-i)!
 
blöderidiot schrieb:
Hättest Du das nicht geschrieben, hätte ich es gar nicht gemerkt. Nun aber weiß ich, dass Du einen harten Tonfall gewählt hast!!!!!
Nicht absichtlich, aber als ich meinen Post fertig hatte und ihn nochmal zusammen mit meinem ersten gelesen hatte, habe ich gemerkt, dass ich vielleicht etwas zu aggressiv rüber komme. Daher die provisorische Entschuldigung.

Dass ich mich - ohne die Originalaufgabe gesehen zu haben - etwas weit aus dem Fenster lehne ist mir klar und wenn sich herausstellt, dass ich doch falsch liege, werde ich das (hoffentlich) ohne Wenn und Aber akzeptieren.

@Infi<3:
Du denkst vermutlich, sie wäre nach Schema F formuliert, weil die Frage einen bestimmten Begriff enthält, der dort üblicherweise vorkommt. Ich weiß aber nicht, ob du die Möglichkeit berücksichtigst, dass es sich um eine "Nicht-Schema F Formulierung" handelt, die zufälligerweise den selben Begriff benutzt, diesen jedoch auf etwas anderes bezieht.

Was man nicht vergessen sollte: Schema F Formulierungen in der Lehre stammen von Leuten, die sich A) mit der Materie auskennen und B) meistens die Antwort schon wissen bzw. einen bestimmten Lösungsweg abprüfen wollen und daher normalerweise selten unnötige Informationen in die Aufgabenstellung mitaufnehmen.
All das ist aber bei echten Problemstellungen häufig nicht der Fall. Daher reicht es dann auch nicht nur zu schauen, ob die Stichworte zu bekanntem Standardproblem XY passen, sondern man muss wirklich genau prüfen in welchem Kontext diese Begriffe verwendet werden.

Nach meinem Verständnis ist die Frage ist eben nicht äquivalent zu "Wie viele verschiedene mögliche Kombinationen aus weißen und schwarzen Kugeln gibt es bei 20 Mal ziehen mit zurücklegen, wenn man die Reihenfolge ignoriert" (hier wäre die Reihenfolge ohnehin irrelevant).

Sondern eher: "Ich hab 20 Säcke mit je einer schwarzen und einer Weißen Kugel. Beide Kugeln sind jeweils mit dem gleichen Buchstaben (A,B,C,D...T beschriftet) und ich ziehe aus jedem Sack eine Kugel. Wie viele verschiedenen Kombinationen sind möglich, ohne die Reihenfolge in der ich die Säcke auswähle zu berücksichtigen". Bei fast allen Standardaufgaben, die ich kenne wird letzteres einfach angenommen und deshalb nicht explizit erwähnt. Entweder ist es egal (ziehen aus N Säcken mit identischen Kugeln/ziehen mit zurücklegen), oder die Reihenfolge ist vorgegeben.

Nunja, bevor ich mich jetzt noch weiter aus dem Fenster lehne warte ich erstmal was der TE dazu sagt.
 
190
20 über 2
http://www.schulminator.com/mathematik/kombinatorik
Ohne Reihenfolge und ohne Wiederholung.

21 ist auf jeden Fall falsch, denn egal wie man es versteht: es können auch 2, 3, 4... der 20 aktiviert sein und nicht nur "alle aus = 20 plus einer an".


Edit:
Ich lass meinen obigen unsinn mal stehen aber er ist falsch.
190 war falsch weil eben nicht genau 2 mal gezogen wird (k=2) sondern unterschiedlich oft
Meine kritik an 21 ist auch falsch weil "alle aus" natürlich nur genau eine möglichkeit ist. Dh ich schließe mich der 21 an!
Es können 0-20 schalter umgelegt sein und somit hat man 20+1 möglichkeiten.
 
Zuletzt bearbeitet:
Der Knackpunkt ist das hier:
Die Reihenfolge spielt keine Rolle also A+B+C ist das gleiche wie C+A+B
Was heißt das konkret an einem Beispiel?

2^20 ist bekanntlich die Anzahl der Möglichkeiten, Nullen und Einsen (An/Aus) auf ein Feld mit 20 Elementen zu verteilen. Oder anders gesagt, wenn ich 20 Schalter in einem Raum habe, gibt es eben 2^20 mögliche Stellungen. Die Reihenfolge, in der diese gesetzt werden, interessiert dabei aber niemanden, aber es ist eben ein Unterschied, ob Schalter 19 "an" ist oder Schalter 7.

21 kommt einfach daher, dass gesagt wird, dass alle möglichen Kombinationen wo genau n Schalter "an" sind, äquivalent sind. Ob Schalter 7 und 3 oder Schalter 4 und 6 gesetzt sind, macht keinen Unterschied.

20 über 2 ist nach meinem Verständnis aber die Anzahl der möglichen Paare aus der Menge {1,...,20}. Aufs Schalter-Beispiel übertragen also "ich renne blind durch den Raum und mache zwei zufällige Schalter an, wie viele Möglichkeiten gibt es?" - das dürfte von allen präsentierten Lösungen noch am weitesten am Ziel vorbei schießen.
 
Zuletzt bearbeitet:
Zurück
Oben