Mathefrage: Kombinatorik

[engelswut]

Hallo,

ein Freund und ich waren letztens in einem Restaurant wo man sich sein Gericht quasi selbst zusammen stellen konnte, das heißt Soßen Beilagen etc. aussuchen.

Wir haben uns gefragt wieviele Möglichkeiten es gibt alles zu Kombinieren. Jetzt stellt sich mir die Frage wie berechnet man das.

Gegeben sind z.B. 5 Kategorien mit 4-7 verschiedenen Sachen, wobei man etwas auch weglassen kann. Und ganz wichtig man kann aus einer Kategorie mehrere Sachen nehmen.
Wie berechne ich nun alle Möglichkeiten ?

 

[maxFrisch]

nur eine wahl pro kategorie? dann ist es simpel, du nimmst von jeder kategorie die anzahl und multiplizierst.
also z.b. 5 kategorien mit 3,4,5,6,7 auswahlmöglichkeiten: 3*4*5*6*7. wenn man was weglassen kann halt 4*5*6*7*8.

 

[w0nd4bra]

fakultäten und binomialkoeffizienten ^^

 

[engelswut]

nur eine wahl pro kategorie? dann ist es simpel, du nimmst von jeder kategorie die anzahl und multiplizierst.

Ja sorry, habs eben nochmal editiert, man kann auch mehrere bis hin zu alles aus einer Kategorie nehmen.

 

[Cheetah1337]

naja ... 0-7 @ 5 Kategorien = 8*8*8*8*7 (weil bei EINER Kategorie muss man ja was nehmen, sonst hast ja kein Gericht ^^)
Aso dann is das natürlich wieder bissi anders, wenn du plötzlich die Angabe änderst.

 

[CarterIII]

mMn ist diese aufgabe sehr leicht zu lösen.
du nimmst einfach die kategorien sagen wir 5, dann guckst du wie viele auswahlmöglichkeiten es dort gibt, sagen wir in den ersten 3 gibt es 4 und in den anderen beiden 6.
dann rechnest du 4*4*4*6*6 und kommst auf 2304.
wenn du jetzt noch einrechnen willst, dass du bei manchen sachen noch was weglassen kannst sagen wir bei den ersten beiden sachen dann rechnest du 5*5*4*6*6 und landest bei 3600

 

[R3ddy]

Ihr habt wohl überlesen, dass aus einer Katergorie auch mehrere Sachen genommen werden können. Somit ergibt sich die Anzahl der möglichen Kombinationen aus 2^"Anzahl aller Gerichte". Also völlig unabhängig von der Anzahl der Kategorien.

Edit:
Mit Fakultät muss nur gerechnet werden, wenn es auf die Reihenfolge ankommt. Dies wird es aber in diesem Fall wohl kaum.

 

[timo82]

@ Cheetah: Das ist falsch.

8*8*8*8*8 - 1 wäre korrekt, wenn man in 5 Kategorien 7 Sachen zur Wahl hat und auch weglassen kann.

Wieviele Sachen kann man pro Kategorie nehmen?

@ R3ddy: auch falsch. Du rechnest aus, wieviele Möglichkeiten es gibt, wenn man0, 1 oder 2 Sachen nimmt. Es können aber auch 3 oder mehr genommen werden.

 

[Warhorstl]

Es gibt ja mehrere Kategorien mit der gleichen Anzahl verschiedener Sachen, also muss für jede Kategorie mit einer anderen Anzahl verschiedener Sachen einzeln die Zahl der Kombinationen berechnet werden.

Wie in den meisten Fällen lohnt sich auch hier ein Baumdiagramm (natürlich in vereinfachter Form). Dann zählt man aber nicht nur die Zahl aller Stränge, sondern wie oft alle Sachen in dem Baumdiagramm vorhanden sind.

Bei 7 Sachen gäbe es beispielsweise zu Anfang 7 Möglichkeiten, dann 6, dann 5, dann 4, dann 3, dann 2, dann 1. Man hätte also so schon 7*6*5*4*3*2*1 Ereignisse. Dann kann man aber auch noch ohne die letzte Beilage ein Gericht zusammenstellen, also 7*6*5*4*3*2. Ohne 2 Beilagen wäre das dann 7*6*5*4*3 Möglichkeiten. So macht man das Weiter, addiert die Produkte und fertig ist die Kategorie mit 7 Sachen.

 

[simpsonsfan]

Wenn man tatsächlich alles komplett frei miteinander kombinieren könnte:

von mir aus 5 Kategorien mit jeweils etwa 7 Möglichkeiten.

das ergibt 5*7 = 35 einzelne Komponenten.

Für jede Komponente gibt es zwei Möglichkeiten: wählen oder weglassen.

Also 35^2 (da zwei Möglichkeiten für jedes einzelne Teil).

Und nicht 2^35.

Falls doch etwas nicht passt, das hier einfach ignorieren.

Edit: Wobei man wohl eher nicht alles frei kombinieren kann. Ich mein nur, wenn dem so wäre...

Edit: Ups, das war wohl nix, hab mich vertan, 2^x stimmt, naja kann passieren

 

[F_GXdx]

2^x stimmt schon.

 

[R3ddy]

mMn ist 2^x richtig, wie ich es oben beschrieben hab!

Bsp. es gibt Gerichte A,B,C,D.
Möglichkeiten:
nix
A
AB
ABC
ABCD
ABD
AC
ACD
AD
B
BC
BCD
BD
C
CD
D

=16=2^4

P.S. Mir ist bewusst, dass ein Beispiel nichts beweist.

 

[GregoryH]

Zuerst einmal - Ja die 2^x Version ist richtig. Auch der Ansatz über die Binominal-Koeffizienten führt zu diesem Ergebnis:

= 2^35

Da drin ist aber beispielsweise auch die Kombination ich esse nichts, da man aber eigentlich was isst, wäre die Richtige antwort 2^35 - 1 ;P

Wer nicht weiß was Binominal-Koeffizienten sind, googlen

 

[Kopfkirmes]

Falls ich das richtig verstanden habe, ist hier nach einen allgemeinen Formel für die Berechnung der Anzahl der Kombinationsmöglichkeiten gefragt. Wie bereits oben erwähnt wurde muss man hier Binomialkoeffizienten benutzen. Letztenendes läuft es hier auf einem Produkt von n Summen aus Binomialkoeffizienten hinaus (n = Anzahl der Kategorien). Diese kann man mit Hilfe des binomischen Lehrsatzes vereinfachen und man erhält als Ergebnis (2^m1)*(2^m2)*....*(2^mn) - 1, wobei mi die Anzahl der Auswahlen in der i-ten Kategorie ist. Das minus 1 zieht man ab, weil man die leere Kombination (also dass nichts aus allen Kategorien gewählt wird) nicht haben will.

So, das war lang. Ich hab´s nur kurz aus´m Stegreif geschrieben. Der Beweis dazu ist nicht lang, aber ohne Formeleditor hier nicht so einfach einzugeben. Falls doch Fehler drinnen sein sollte, bitte mich nicht gleich lynchen ^^.

 

[timo82]

mMn ist 2^x richtig, wie ich es oben beschrieben hab!

Bsp. es gibt Gerichte A,B,C,D.
Möglichkeiten:
nix
A
AB
ABC
ABCD
ABD
AC
ACD
AD
B
BC
BCD
BD
C
CD
D

=16=2^4

P.S. Mir ist bewusst, dass ein Beispiel nichts beweist.

Das sind 15

 

[GregoryH]

@Kopfkirmes
Warum für jede Kategorie eigene Binomialkoeffizienten? So wie ich die Aufgabenstellung verstehe, kann man frei aus den Kategorien wählen, auch mehrfach oder garnicht -> Vereinfachung auf einen "großen Pool" aus Essen.

Oder irre ich mich?

@timo82
Nix mitgezählt?

 

[R3ddy]

Wenn ich noch korrekt bis 16 zählen kann und auch "nix" mitzähle komme ich auf 16.

 

[Kopfkirmes]

Unterschiedliche Koeffizienten deshalb, weil ich den allgemeinen Fall betrachtet hab, wo es in jeder Kategorie unterschiedlich viel Auswahl geben kann (daher die Unterscheidung zwischen den mi´s).

 

[TheGreatMM]

Es gibt insgesamt vier Möglichkeiten Wahrscheinlichkeiten zu errechnen: Mit/Ohne zurücklegen und Mit und Ohne Wiederholung.

Mit jeweils anderen Formeln thats it

 

[timo82]

Nix ist kein Gericht.

Ausserdem rechnet ihr so, als wenn alles eine Kategorie wäre und man alle Gerichte nehmen kann.
Da gibt es sicher ne Geenze, man kann also nicht 100 Sachen bestellen, wenn es 100 verschiedene gibt.