Kombinationsmöglichkeiten berechnen

01.12.2012, 15:45

sam_semillia

Kombinationsmöglichkeiten berechnen

Meine Frage:
Hallo,

ich habe folgende Problemstellung:

Ich habe Gruppen von Zahlen, und möchte die Anzahl der Kombinationsmöglichkeiten von einem gewissen System errechnen. Vom Prinzip her wie beim Lotto: x aus y.
Dieser Screenshot verdeutlicht dies vllt besser:
[attach]26975[/attach]
Bilder bitte im Forum hochladen.

Die gelb eingefärbten Felder, sind meine Zahlen Gruppen. Die weiss eingefärbten Felder sind die möglichen Kombinationen.

Jede Spalte steht für eine Gruppe in meiner Zahlengruppe. Jede Zahlengruppe kann X Gruppen beinhalten. Jede Gruppe kann X Zahlen beinhalten. Zahlen einer Gruppe dürfen jedoch nicht miteinander kombiniert werden.

Systeme die ich gerne berechnen würde, können sein: x aus y.
x ... von 1 bis Anzahl der Gruppen/Spalten
y ... Anzahl der Gruppen/Spalten

Mit Hilfe des Binomialkoeffizienten, habe ich es geschafft aus "einfachen" Gruppen die Kombinationsmöglichkeiten zu berechnen. Ähnlich Lotto. Aber sobald sich die Anzahl der Zahlen iunnerhalb einer Gruppe erhöht, bin ich aufgeschmissen.

Kann mir vllt jemand helfen, danke.

mfg sam

Meine Ideen:
Mit Hilfe des Binomialkoeffizienten, habe ich es geschafft "einfachen" Gruppen die Kombinationsmöglichkeiten zu berechnen. Ähnlich Lotto.

03.12.2012, 10:31

MatheMathosi

Auf diesen Beitrag antworten »

Also ich denke du kannst das wie folgt machen:

Du zählst erst mit dem Binomialkoeffizienten alle Kombinationsmöglichkeiten z.B. in der Tabelle links unten mit

$\begin{eqnarray*} \begin{pmatrix} 5 \\ 2 \end{pmatrix} \end{eqnarray*}$

Und musst dann die zuviel gezählten Kombinationen der Menge {1,2,3} wieder abziehen.

Wie kannst du das machen ?

03.12.2012, 11:53

samse

Auf diesen Beitrag antworten »

also ich würde es versuchen mit

(2:5) - (1:3) = 10 - 3 = 7
(2:5) - (2:3) = 10 - 3 = 7

leider ist das ergebnis nicht eindeutig! ich hab auch gerade "herumprobiert" mit mehr gruppen. also zB
1 5 7 8
2 6
3
4

mit 3:4 komm ich da auf insgesamt 14 möglichkeiten. wenn ich berechne 3:8 = 56. aber dann hänge ich komplett.

danke aif jeden fall für deine hilfe!!
mfg

03.12.2012, 11:57

sam_semillia

Auf diesen Beitrag antworten »

Zitat:

mit 3:4 komm ich da auf insgesamt 14 möglichkeiten.

ich meine natürlich 18 kombinationsmöglichkeiten!

mfg

03.12.2012, 12:17

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von sam_semillia
Jede Spalte steht für eine Gruppe in meiner Zahlengruppe. Jede Zahlengruppe kann X Gruppen beinhalten. Jede Gruppe kann X Zahlen beinhalten. Zahlen einer Gruppe dürfen jedoch nicht miteinander kombiniert werden.

Systeme die ich gerne berechnen würde, können sein: x aus y.
x ... von 1 bis Anzahl der Gruppen/Spalten
y ... Anzahl der Gruppen/Spalten

Diese deine Beschreibung repräsentiert nur unzureichend die Beispiele, die du dann im Excel-Sheet angibst. unglücklich

Anscheinend geht es dir eher darum:

Du hast $\begin{eqnarray*} n \end{eqnarray*}$ verschiedene Zahlen, aufgeteilt auf $\begin{eqnarray*} m\leq n \end{eqnarray*}$ Gruppen mit den jeweiligen Gruppenanzahlen $\begin{eqnarray*} n_1,\ldots,n_m \end{eqnarray*}$ , deren Summe dann natürlich $\begin{eqnarray*} n_1+n_2+\ldots+n_m=n \end{eqnarray*}$ ergibt. Desweiteren sei $\begin{eqnarray*} k\leq m \end{eqnarray*}$ .

Nun willst du die Anzahl der Möglichkeiten wissen, genau $\begin{eqnarray*} k \end{eqnarray*}$ Zahlen auszuwählen mit der Bedingung, dass aus jeder Gruppe nur maximal eine Zahl ausgewählt wird. Im allgemeinen Fall ist das klarerweise

$\begin{eqnarray*} \sum\limits_{\substack{A\subset \{1,\ldots,m\}:\\ |A|=k}} ~ \prod\limits_{j\in A} n_j \qquad (*) \end{eqnarray*}$ ,

was z.B. für deinen zweiten Fall der ersten Zeile mit $\begin{eqnarray*} m=3,k=2,n_1=2,n_2=n_3=1 \end{eqnarray*}$ die Kombinationsanzahl

$\begin{eqnarray*} n_1n_2+n_1n_3+n_2n_3 = 2+2+1 = 5 \end{eqnarray*}$

ergibt. Im dritten Beispiel wäre $\begin{eqnarray*} m=3,k=2,n_1=n_2=2,n_3=1 \end{eqnarray*}$ mit dann

$\begin{eqnarray*} n_1n_2+n_1n_3+n_2n_3 = 4+2+2 = 8 \end{eqnarray*}$

usw.

Der Spezialfall, dass alle $\begin{eqnarray*} n_1,\ldots,n_m \end{eqnarray*}$ einander gleich sind (wie im vierten Beispiel der ersten Zeile mit $\begin{eqnarray*} m=3,k=3,n_1=n_2=n_3=2 \end{eqnarray*}$ ), lässt dich leicht über

$\begin{eqnarray*} \sum\limits_{\substack{A\subset \{1,\ldots,m\}:\\ |A|=k}} ~ \prod\limits_{j\in A} n_j = \sum\limits_{\substack{A\subset \{1,\ldots,m\}:\\ |A|=k}} ~ n_1^k = \binom{m}{k}n_1^k \end{eqnarray*}$

erledigen, hier also $\begin{eqnarray*} \binom{3}{2}2^2 = 12 \end{eqnarray*}$ . Abgesehen von derartigen Spezialfällen ist Anzahlformel (*) aber kaum zu vereinfachen. unglücklich

03.12.2012, 12:24

MatheMathosi

Auf diesen Beitrag antworten »

letzterer Punkt ist richtig Freude

Zitat:

leider ist das ergebnis nicht eindeutig! ich hab auch gerade "herumprobiert" mit mehr gruppen. also zB 1 5 7 8 2 6 3 4

Hier machst du das einfach genauso. Du hast 8 Elemente und du willst dir hieraus eine zweielementige Teilmenge machen. Dafür gibt es
$\begin{eqnarray*} \begin{pmatrix} 8 \\ 2 \end{pmatrix} \end{eqnarray*}$
Möglichkeiten. Nun ziehst du wieder entsprechend ab:

$\begin{eqnarray*} \begin{pmatrix} 8 \\ 2 \end{pmatrix}-\begin{pmatrix} 4 \\ 2 \end{pmatrix}-\begin{pmatrix} 2 \\ 2 \end{pmatrix}=21 \end{eqnarray*}$

Wenn du 3 zahlen herausnimmst entsprechend das selbe.

03.12.2012, 13:21

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von MatheMathosi
Wenn du 3 zahlen herausnimmst entsprechend das selbe.

Im Detail?

$\begin{eqnarray*} \binom{8}{3}-\binom{4}{3}-\binom{2}{3} \end{eqnarray*}$ ist jedenfalls nicht die richtige Anzahl. unglücklich

03.12.2012, 13:32

MatheMathosi

Auf diesen Beitrag antworten »

Zitat:

$\begin{eqnarray*} \binom{8}{3}-\binom{4}{3}-\binom{2}{3} \end{eqnarray*}$ ist jedenfalls nicht die richtige Anzahl. unglücklich

Sorry, da habe ich zu einfach gedacht.

03.12.2012, 13:35

sam_semillia

Auf diesen Beitrag antworten »

danke für eure antworten.
ich habe mal ein bsp grafisch abgebildet, da kam ich mit MatheMathosi's lösungsansatz auch nicht auf die richtigen ergebnisse.

jetzt versuche ich grade HAL 9000's lösungsansatz zu verstehen bzw nachzuvollziehen. kannst du mir vllt mit dem aktuellen bsp die lösungen errechnen. zum genaueren verständnis? die wahl mit 2/3 ist vllt nicht ganz glücklich gewählt gewesen...

danke, mfg

03.12.2012, 13:52

sam_semillia

Auf diesen Beitrag antworten »

//edit 2: kann den beitrag oben leider nicht mehr bearbeiten:

//edit: hier noch der versuch einer genaueren beschreibung meines problems:
ich habe 1...beliebig viel gruppen von zahlen. diese gruppen von zahlen können 1...beliebig viele zahlen beinhalten. diese zahlen der zahlengruppen sollen in bestimmten systemen kombiniert werden.

die anzahl der gruppen in der berechnung ist genau die anzahl der gruppen. die anzahl der zu kombinierenden zahlen kann von 1...anzahl der gruppen annehmen. zahlen der selben gruppe dürfen nicht kombiniert werden. gesucht ist die anzahl der möglichen kombinationen.

ich hoffe jetzt ist es etwas klarer beschrieben!

danke, mfg

03.12.2012, 14:09

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von sam_semillia
kannst du mir vllt mit dem aktuellen bsp die lösungen errechnen. zum genaueren verständnis?

Du meinst jetzt das Beispiel

1 5 7 8
2 6
3
4

und du willst 3 Zahlen auswählen? Das wäre $\begin{eqnarray*} m=4,n_1=4,n_2=2,n_3=n_4=1,k=3 \end{eqnarray*}$ und folglich ist die gesuchte Anzahl

$\begin{eqnarray*} n_1n_2n_3+n_1n_2n_4+n_1n_3n_4+n_2n_3n_4 = 8 + 8 + 4 + 2 = 22 \end{eqnarray*}$ .

Bei $\begin{eqnarray*} k=4 \end{eqnarray*}$ entsprechend

$\begin{eqnarray*} n_1n_2n_3n_4 = 8 \end{eqnarray*}$ .

Im Sonderfall $\begin{eqnarray*} k=m-1 \end{eqnarray*}$ kann man Formel (*) übrigens auch etwas "gefälliger" schreiben:

$\begin{eqnarray*} \sum\limits_{\substack{A\subset \{1,\ldots,m\}:\\ |A|=m-1}} ~ \prod\limits_{j\in A} n_j = \prod\limits_{j=1}^m n_j \cdot \sum_{j=1}^m \frac{1}{n_j} \end{eqnarray*}$ ,

das wäre hier bei deinem schon besprochenen Beispiel $\begin{eqnarray*} m=4,n_1=4,n_2=2,n_3=n_4=1,k=3 \end{eqnarray*}$ dann

$\begin{eqnarray*} n_1n_2n_3n_4\left( \frac{1}{n_1}+\frac{1}{n_2}+\frac{1}{n_3}+\frac{1}{n_4} \right) =4\cdot 2\cdot 1\cdot 1\cdot\left( \frac{1}{4}+\frac{1}{2}+1+1 \right) = 8\cdot \frac{11}{4} = 22 \end{eqnarray*}$ .

P.S.: Für $\begin{eqnarray*} k=2 \end{eqnarray*}$ stimme ich MatheMathosi zu, da ist vermutlich die Berechnungsweise über

$\begin{eqnarray*} \binom{n}{2} - \sum_{j=1}^m \binom{n_j}{2} \end{eqnarray*}$

die günstigste Variante, wenngleich (*) da nicht falsch, aber eben nicht so effizient ist. Leider kann man das aber für größere $\begin{eqnarray*} k \end{eqnarray*}$ nicht so einfach verallgemeinern.

13.12.2012, 12:22

sam_semillia

Auf diesen Beitrag antworten »

danke vielmals, hast mir unheimlich weitergeholfen!!!

mfg

Neue Frage »

Antworten »

Kombinationsmöglichkeiten berechnen

Verwandte Themen