Frage an die Mathe Profis: Anzahl mögl. kombinationen bestimmen

[Corny]

Hallo,

Ich such nun schon eine ganze Weile im Internet, kann aber nichts zu der Aufgabenstellung finden:
Ich will die Anzahl der Kombinationsmöglichkeiten errechnen. Es dürfen keine Namen doppelt vorkommen, jeder Name darf auch eigenständig genannt werden und es darf auch kleinere Kombinationen geben.

Beispiel:

Vorgabe:
Schnitzel, Pommes, Ketchup

Ergebnis:
1. Schnitzel
2. Pommes
3. Ketchup
4. Schnitzel Pommes
5. Schnitzel Ketchup
6. Pommes Ketchup
7. Schnitzel Pommes Ketchup

In diesem Fall wäre das Ergebnis also 7. Aber wie siehts aus wenn ich mehr als drei verschiedene Wörter verwende? Wie errechne ich die Anzahl der Möglichkeiten?

Gruß - Corny

PS: wenn jemand ein Programm hat das alle Möglichkeiten Auflistet (bevorzugt Excel Tool - muss aber nicht) wäre das sehr gut. Sowas suche ich nämlich auch.

[Mark]

!x-1 (x € N), wobei ich mir da absolut nicht sicher bin, is nur gut geraten :)

[Oberon]

Die Systematik ist die: Du hast n Elemente, in diesem Fall 3. Dann ist die Anzahl der gesamten Möglichkeiten nC0+ nC1+........nCn-1 + nCn. In deinem Fall also 3C0+3C1+3C2+3C3 = 1+3+3+1 = 8. ( denn ich denke, 0 Elemente darf man auch herausnehmen.
nCx ist übrigens n!/(x! * (n-x)!) falls dir die Schreibweise nix sagt.

[mofa84]

die Lösung sollte unter Kombinatorik (http://de.wikipedia.org/wiki/Kombinatorik) zu finden sein.

[Corny]

mofa84[/POST]']die Lösung sollte unter Kombinatorik (http://de.wikipedia.org/wiki/Kombinatorik) zu finden sein.

darüber hab ich schon ewig gebrütet. Allerdings kombinieren die immer alles mit allem, da gibts nie einen Namen einzeln. :|

Die anderen beiden Vorschläge schaue ich mir mal an. Muss mich erst in die Formeln rein denken, bin da nicht so der Profi.

[Corny]

Oberon[/POST]']Die Systematik ist die: Du hast n Elemente, in diesem Fall 3. Dann ist die Anzahl der gesamten Möglichkeiten nC0+ nC1+........nCn-1 + nCn. In deinem Fall also 3C0+3C1+3C2+3C3 = 1+3+3+1 = 8. ( denn ich denke, 0 Elemente darf man auch herausnehmen.
nCx ist übrigens n!/(x! * (n-x)!) falls dir die Schreibweise nix sagt.

kannst du das bitte für DAU's erklären wie man das ausrechnet? :biggrin:
Danke!

Edit: okay, hat sich erledigt, ich habs geschafft. Danke für eure Hilfe :)

[Corny]

Kann es stimmen das ich mit 2^n-1 auf das selbe Ergebnis komme?

bei meinem obigen Beispiel mit drei Werten habe ich ja 7 Möglichkeiten.
2^3 = 8
8-1 = 7

Das gleiche klappt scheinbar mit einer manuell ausgetüftelten Version mit 4 Wörtern.
Ich kanns nicht glauben das es so einfach ist? :|
Vor allem nicht das mir dann Oberon so eine komplexe Formel gegeben hat. Er scheint sich ja auszukennen und hätte doch dann sicherlich auch diese einfache Variante gekannt?
Oder steh ich nur mal wieder aufm Schlauch?

[wetterwax]

Corny[/POST]']Kann es stimmen das ich mit 2^n-1 auf das selbe Ergebnis komme?

bei meinem obigen Beispiel mit drei Werten habe ich ja 7 Möglichkeiten.
2^3 = 8
8-1 = 7

Ich war sicher, dass 2^n richtig ist. :| Ist es in deinem Fall ja eigentlich auch, denn kein Schnitzel, keine Pommes und kein Ketchup ist definitiv auch eine Möglichkeit. (Auch, wenn man von dieser nicht satt wird. ;D )

[Corny]

Richtig, deshalb halt -1.

obs auch bei größeren Zahlen wie 3 und 4 stimmt weiß ich noch nicht. ich bin grad drann da was zu basteln. Blöderweise gibts scheinbar nirgens ein Tool das einem alle Kombinationsmöglichkeiten auflistet. Oder kennt jemand eins?

Ich verdrahte das grad im Excel per Hand, für bis zu 8 Wörter :eek:

[Spasstiger]

Corny[/POST]']Kann es stimmen das ich mit 2^n-1 auf das selbe Ergebnis komme?
Ja, die Rechnung ist korrekt. Du musst im Prinzip nur die Summe einer Reihe im Pascalschen Dreieck berechnen:

0 W: 1
1 W: 1 1
2 W: 1 2 1
3 W: 1 3 3 1
4 W: 1 4 6 4 1
5 W: 1 5 10 10 5 1
etc.

D.h. bei 0 Wörtern (0 W) gibt es genau 1 Kombination, nämlich kein Wort (was du nicht als Kombination zählst, deshalb immer -1).
Bei 3 Wörterm gibt es dann 1 Kombination mit 0 Wörtern, 3 Kombinationen mit 1 Wort, 3 Kombinationen mit 2 Wörtern und 1 Kombination mit 3 Wörtern.
Bei 5 Wörtern gibt es 1 Kombination mit 0 Wörtern, 5 Kombinationen mit 1 Wort, 10 Kombinationen mit 2 Wörtern, 10 Kombination mit 3 Wörtern, 5 Kombinationen mit 4 Wörtern und 1 Kombination mit 5 Wörtern.

[Corny]

So, jetzt klappt so gut wie alles. Ich hab sogar schon im Excel eine Formel gebastelt die mir alles auflistet wie ichs will.

Die Formel mit der Fakultät die Oberon vorgeschlagen hat ist auch sehr hilfreich. Damit kann ich feststellen wieviel beispielsweise 5-Stellige kombinationen es bei x Wörtern gibt. :)

Danke für eure Hilfe!

[Oberon]

Also:
2^n = (1+1)^n

(1+1)^n= nC0* (1^n) + nC1* (1^(n-1))*1+ .......nCn-1 * (1^(n-1))*1 + nCn* 1^n

Das ist der binomische Satz, vielleicht siehst du jetzt den Zusammenhang :)

[Corny]

Oberon[/POST]']Also:
2^n = (1+1)^n

(1+1)^n= nC0* (1^n) + nC1* (1^(n-1))*1+ .......nCn-1 * (1^(n-1))*1 + nCn* 1^n

Das ist der binomische Satz, vielleicht siehst du jetzt den Zusammenhang :)

ganz Ehrlich?
Ich versteh nur Bahnhof :| :biggrin:
du brauchst es mir aber auch nicht erklären, sonst komm ich nur durcheinander. Es funktioniert jetzt sogar alles und ich bin zufrieden :D


Mir fehlt einfach das ich in der Schule ab der 7ten Klasse kein Mathe mehr hatte. (Wirtschaftsschule -> Handels-Zweig)