KOmbinatorik Problem
-
Hi,
Wenn ich eine Menge M mit |M| = n habe, und möchte alle Kombinationen finden, die mit den Elementen aus M Möglich sind, wobei Nicht zurückgelegt wird, und die Anzahl der Verwendeten Elemente egal ist, und die Reihenfolge egal ist, wie viele Kombinationen gibt es dann abhängig von n?Beispiel:
M={a; b; c}
dann gibt es die Kmbinationen:
a b c
ab ac bc
abc
also 7 Kombinationen.für |M|=4 wären das schon 15...
-
Letztlich gibt es dadurch, dass du nicht zurücklegst und die Reihenfolge vernachlässigst genau zwei Möglichkeiten pro Element: entweder es ist dabei, oder es ist nicht dabei.
Macht insgesamt 2^n Möglichkeiten. Wobei da die Möglichkeit mit drin ist, dass Du die leere Menge erzeugst, also kein einziges Element darin enthalten ist. Wenn Du das nicht mitzählen willst halt 2^n - 1.
Siehe auch: http://de.wikipedia.org/wiki/Potenzmenge
-
aber dann ists ja mit zurücklegen, dann gibts die menge {a,a} zB doch auch !?
-
Ich brauche das, um herauszufinden, wie viele Verschiedene Teiler ich aus einer reihe von primfaktoren erzeugen kann. wenn ich da 2 ma den faktor zwei hab, kann ich das ja auch zu {a, a} kombinieren. Dh, es gibt mehrere a, die man miteinander kombinieren kann, aber {b, a} ist immer das gleiche.
Dh, wenn die Menge an faktoren die elemente {a, a, b, c} hat, dann ergeben sich daraus nur noch 10 Kombinationen.
Für alles andere Funktioniert die sache mit der Potenzmenge ganz gut.
-
piXelshooter schrieb:
Dh, wenn die Menge an faktoren die elemente {a, a, b, c} hat, dann ergeben sich daraus nur noch 10 Kombinationen.
Ah, wir sprechen von Multimengen.
Die Menge {a,a,b,c} ist das Gleiche wie {a,b,c}.Wenn Du manche Elemente mehrfach haben willst, dann mußt Du das anders machen. Für Dein konkretes Problem so:
Du hast Primzahlen p_1,...,p_r wobei Du p_i n_i mal hast. Dann lässt sich die allgemeine Zahl schreiben als
p_1^k_1 * ... * p_r^k_r mit 0<=k_i<=n_i.
Also haste für die Primzahl p_i genau r_i+1 Möglichkeiten. Macht insgesamt (r_1 + 1)* ... * (r_n + 1) Möglichkeiten.
Für Dein a,a,b,c-Beispiel ergibt das (2+1)(1+1)(1+1) = 3*4=12 mögliche Zahlen.