Anzahl der Kombinationen < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
Hi! Ich hoffe, ich bin hier im richtigen Unterforum!
Ich benötige mal einen Tipp, weil ich hier mit meiner Schulmathematik nicht weiterkomme.
Ich habe bei einer Abfrage über einen Sprachkorpus die Möglichkeit, die Resultate (=Textauszüge, in denen z.B. ein bestimmtes Wort vorkommt), die in der Stichprobe sein werden, einzuschränken und zwar mit Hilfe von Werten aus verschiedenen Kategorien.
Es gibt:
- 14 Kategorien (bspw.: Alter des Textpoduzenten, Geschlecht des Textproduzenten, etc.)
- insg. 104 Werte, verteilt über diese 14 Kategorien. Allerdings ist die Zahl der Werte pro Kategorie unterschiedlich.
Nun brauche ich die Anzahl der möglichen Kombinationen von Werten für die Abfrage, bzw. einen *Weg* dahin.
Beispiel:
- Kat. A hat 3 Werte. Alleine in dieser Kat. gibt es also bereits 7 Möglichkeiten, Werte zu kombinieren (A1, A1+A2, A1+A3, A1+A2+A3, A2, A2+A3, A3).
- Kat. B hat 2 Werte. Hier gibt es X Möglichkeiten, die Werte zu kombinieren (B1, B1+B2, B2)
- Da es sich bei den Werten um "Auswahlfelder" handelt, hat die Auswahl von allen Werten das gleiche Resultat, wie wenn keine Werte ausgewählt sind.
Jetzt geht es mir daum zu ermitteln, um am Beispiel zu bleiben, wieviele Kombinationen es über die Kategorien gibt. Ich fang die Reihe mal an:
(Alle Wertkombinationen aus A + keine Wertauswahl in B), (alle Wertkombinationen aus B + keine Wertauswahl in A), (A1+B1), (A1+A2+B1), (A1+A2+A3+B1), (A1+A3+B1), (A1+B2), (A1+B1+B2), etc. pp.
Die Anzahl der Werte in den einzelnen Kategorien folgt:
- Kat I: 3 Werte
- Kat II: 5 Werte
- Kat III: 5 Werte
- Kat IV: 6 Werte
- Kat V: 6 Werte
- Kat VI: 3 Werte
- Kat VII: 3 Werte
- Kat VIII: 5 Werte
- Kat IX: 6 Werte
- Kat X: 3 Werte
- Kat XI: 3 Werte
- Kat XII: 4 Werte
- Kat XIII: 3 Werte
- Kat XIV: 46 Werte
Ich wäre SOWAS von unglaublich dankbar, wenn mir hier jemand auf die Sprünge helfen könnte!
Vielen Dank im Voraus!
Stephan
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt: http://www.onlinemathe.de/
|
|
| |
|
Huhu,
dir ist schon klar, dass die Zahl sehr schnell sehr groß werden wird?
Aber nun gut.....
Ok, halten wir fest: Bei einer Kategorie mit n Eigenschaften, gibt es [mm] $2^n [/mm] - 1$ Möglichkeiten, diese zu verwenden.
Dazu gibts mehrere Erklärungen, wieso das so ist. Die einfachste ist wohl, man wählt die Eigenschaften wie folgt:
[mm] $A_1*\{0,1\} [/mm] + [mm] A_2*\{0,1\} [/mm] + .... + [mm] A_n*\{0,1\}$
[/mm]
D.h. wir addieren erstmal alle Eigenschaften und wählen jeweils nur zwischen den beiden Faktoren 0 und 1, ob wir die Eigenschaft haben wollen, oder nicht. Wir haben also 2 Möglichkeiten und da wir n mal wählen [mm] 2^n [/mm] Möglichkeiten.
Eine schließen wir aus (alle 0, da wir mindestens eine Eigenschaft haben wollen) also bleiben [mm] $2^n [/mm] - 1$
Das Tolle bei mehreren Kategorien und deren Kombinationsmöglichkeiten ist nun, dass wir die nicht getrennt betrachten müssen, sondern wir nehmen einfach alle Eigenschaften und packen die in eine Kategorie "Alle" und berechnen die Möglichkeiten genau wie oben.
d.h. haben wir wie in deinem Beispiel Kategorie A und B, betrachten wir hier die Kategorie "Alle" mit
Alle = {A,B} und die hat Folglich 3 (Werte aus A) + 2 (Werte aus B) = 5 Werte und damit [mm] $2^5 [/mm] - 1 = 31$ Kombinationsmöglichkeiten.
Naja, deine Anzahl an Werten zusammenzurechnen und [mm] 2^n [/mm] - 1 zu berechnen, spar ich mir mal, kriegst du auch allein hin. 
MFG,
Gono.
|
|
|
| |
|
Wow, das ist eine gute Erlärung, selbst für einen Laien wie mich verständlich. Vielen Dank erstmal!
Eine kurze Rückfrage, ich habe auf meinen Crosspost "drüben" eine (wie ich glaube, wie gesagt, bin Laie) ähnliche Antwort erhalten, die allerdings in einer Formel mit Pi beginnt. Vllt. hast Du Lust, Dir das mal anzuschauen und Deine Meinung zu verraten?
In der Zwischenzeit rechne ich ein wenig  .
Hier ist der Link: ![[]](/images/popup.gif) http://www.onlinemathe.de/forum/Anzahl-Kombinationen-von-104-Werten
Tausend Dank nochmal!
EDIT: Ich glaube, ich habe das Ergebnis:
20282409603651670000000000000000-1, also:
20282409603651669999999999999999. Juchu!
|
|
|
| |
|
Huhu,
deine Formel beginnt mit einem großen "pi", da es nicht anderes als das Produktzeichen darstellt:
[mm] $\produkt_{i=1}^{n}a_i [/mm] $ ist nichts anderes als [mm] $a_1 [/mm] * [mm] a_2 [/mm] * [mm] a_3 [/mm] * [mm] \ldots [/mm] * [mm] a_n$
[/mm]
Wenn man die Formel dort vereinfacht (wie später ja auch getan), stellt man fest, dass man auch einfach alle n's zusammenzählen kann und dann auf
[mm] $2^{\summe_{i=1}^{n}n_i} [/mm] - 1$ kommt.
MFG,
Gono.
|
|
|
| |
|
Hallo Stephan,
mir ist bei dieser Kombinatorikaufgabe nicht so recht geheuer,
weil ich denke, dass du gar nicht klar beschreibst, was du genau
zählen willst. Zwar schreibst du von gewissen "Kategorien" und
"Werten" innerhalb dieser Kategorien. Was du aber wirklich mit
einer "Kombination" meinst, ist (wenigstens mir) keineswegs
klar. Ist innerhalb einer "Kategorie" jeweils genau einer der
zugelassenen Werte möglich oder sind Mehrfachankreuzungen
generell oder nur bei bestimmten Kategorien zugelassen ?
Ich denke, dass du das Problem zuerst genau beschreiben solltest,
bevor man über einen Lösungsansatz nachdenken kann.
LG Al-Chwarizmi
|
|
|
|
