Kombination von beliebig vielen Mengen

Wissenschaft Mathematik
#1

Hi,
ich suche eine explizite Formel zur Berechnung der Kombinationsmöglichkeiten für folgendes Problem:

Gegeben seien n Mengen mit jeweils beliebig vielen Elementen. Elemente aus einer Menge dürfen nicht kombiniert werden. Eine Kombination besteht aus wenigstens 1 und höchstens n Elementen. Außerdem zählen Kombinationsmöglichkeiten, die exakt die gleichen Elemente enthalten (zB. ab und ba), als eine Kombination.

Wenn jede Menge nur ein Element enthält, gibt es (2^n)-1 Kombinationsmöglichkeiten: Menge 1 = {a} Menge 2 = {b} Kombinationen: a b ab

Bei mehrelementigen Mengen, weiß würde ich gerne auch die explizite Formel wissen.

Kleines Beispiel für mehrelementige Mengen: Menge 1 = {a,b} Menge 2 = {c,d} Menge 3= {e} Daraus ergeben sich folgende 17 Kombinationen: a b c d e ac ad bc bd ae be ce de ace ade bce bde

#2

Hallo, tut mir leid, hbe im Moment keinen Kopf dafür frei…

#3

Tut mir leid keine Ahnung…

#4

Hallo.

So wie ich Dich verstanden habe, wird aus jeder Menge ein oder kein Element genommen und die Mengen sind disjunkt (Schnittleer).
Seinen mal j Mengen gegeben mit jeweils n1,…,nj Elementen

Überlege erstmal wieviele Möglichkeiten Du für die Kombinationen hast, wenn Du aus jeder Menge GENAU ein Element nimmst: Für die erste Menge n1 Möglichkeiten, für die zweite n2, usw.

Damit ist die Zahl der Möglichkeiten = n1 * n2 * … * nj

Wenn man jetzt auch zulassen möchte, dass entweder ein oder kein Element einer Menge kombiniert werden, so stelle Dir vor Du fügst jeder Menge noch ein Platzhalterelement z hinzu. Das Platzhalterelement wird immer dann gewählt, wenn eigentlich kein Element der Menge kombiniert werden soll.

So kannst du den Fall, dass ein oder kein Element ausgewählt wird auf den Fall zurückführen, dass genau eines gewählt werden muss.

Damit ergeben sich für die Zahl der Möglichen Kombinationen (n1 + 1)*(n2 + 2)*…*(nj + 1)

Aber vorsicht: Jetzt zählt man auch die leere Kombination mit, die gar keine Elemente aus irgendeiner Menge enthält. Will man dies nicht, muss man noch diese Möglichkeit abziehen. Es ergibt sich also:

(n1 + 1)*(n2 + 2)*…*(nj + 1) - 1

In Deinem Beispiel heisst das: n1 = 2, n2 = 2, n3 = 1
(2 + 1)*(2 + 1)*(1 + 1) - 1
=3*3*2 - 1
=17

Ich hoffe das konnte helfen.
Lieber Gruß,
Peter