Statistik, Stochastik, Kombinatorik?
Hallo zusammen,
ich sitze gerade an einer Aufgabe,
es gibt einen 12er und einen 8er Tisch, 10 mänl. und 10 weibl. Personen sollen sich an den Tischen verteilen. Wie viele Möglichkeiten haben die Personen sich an den Tischen zu verteilen, wenn an einem exakt sechs weibliche sitzen sollen?
Über jegliche Hilfestellung bin ich sehr dankbar.
2 Antworten
Wir wollen erreichen, dass an mindestens einem Tisch genau sechs Frauen sitzen. Betrachte zwei Fälle:
- Wir wählen 6 Frauen aus und platzieren sie an Tisch 1. Wir fordern, dass an diesem Tisch keine weiteren Frauen sitzen, um unsere Bedingung zu erfüllen. Das bedeutet, dass wir die restlichen 12 - 6 = 6 Plätze mit Männern auffüllen, die wir vorher auswählen. Die restlichen 8 Menschen verteilen wir beliebig auf Tisch 2.
- Wir wählen wieder 6 Frauen aus, platzieren sie allerdings nun an Tisch 2. Die restlichen zwei Plätze sind wieder mit beliebigen Männern aufzufüllen. Außerdem können wir die restlichen 12 Menschen wieder beliebig auf die Plätze an Tisch 1 verteilen.
Abstrahieren wir das Problem etwas. Bezeichne ...
- Nm: die Zahl der Männer,
- Nw: die Zahl der Frauen,
- T1: die verfügbaren Plätze an Tisch 1,
- T2 = (Nm+Nw) - T1: die verfügbaren Plätze an Tisch 2 und
- Kw: die Zahl der Frauen, die wir exakt an mindestens einem Tisch platzieren wollen (in unserem Beispiel ist Kw = 6).
Betrachten wir mal Fall 1 en détail. Zunächst müssen wir Kw aus den Nw Frauen, sowie Kw der T1 vielen Stühle an Tisch 1 auswählen. Anschließend wollen wir die Kw Frauen 1:1 auf die Kw Stühle abbilden. Offensichtlich ist die Zahl der Möglichkeiten, dies zu tun, insgesamt gegeben durch
Damit sind wir aber noch nicht fertig. Jetzt haben wir fixiert, welche Frauen auf welchen Stühlen des ersten Tisches sitzen. Nun bleiben T1-Kw Stühle frei, auf die wir T1-Kw Männer verteilen müssen. Der gleichen Argumentation folgend, ergibt dies die Faktoren
Damit haben wir den Tisch 1 abgefrühstückt. Aber der zweite Tisch ist momentan noch völlig unbesetzt. Soll heißen, wir müssen die übrigen T2 = (Nm+Nw)-T1 vielen Menschen auf eben jene T2 Plätze an Tisch 2 verteilen. Das ist aber einfach gemacht, denn dafür gibt es einfach T2! viele Möglichkeiten. Wenn wir nun all diese Faktoren multiplizieren, erhalten wir im ersten Fall also insgesamt
viele Möglichkeiten, genau sechs Frauen an Tisch 1 zu platzieren.
Analog gehst du im zweiten Fall vor. Das Ergebnis ist identisch zum ersten Fall, wenn du lediglich T1 und T2 vertauscht. Das gesamte Ergebnis, d.h. die Gesamtzahl an Möglichkeiten, die Leute auf die Tische zu verteilen, sodass an einem Tisch genau sechs Frauen sitzen, ergibt sich dann einfach als Summe der gefundenen Möglichkeiten der beiden Fälle.
Hier noch eine naive (sequentielle) Implementierung des Ganzen. Ist zwar quick 'n' dirty, funktioniert aber für kleine Werte.
import itertools
from scipy.special import binom, factorial
class Person:
def __init__(self, gender, idx):
self.gender = gender
self.idx = idx
def num_females(t):
return sum([1 for pers in t if pers.gender == 'female'])
def valid_perm(t1, t2, Kw):
n1, n2 = num_females(t1), num_females(t2)
return n1 == Kw or n2 == Kw
def exact_solution(T1, Nm, Nw, Kw):
N = Nm + Nw
T2 = N - T1
def tmp(Ti, Tj):
return binom(Ti, Kw) * binom(Nm, Ti-Kw) * factorial(Ti-Kw) * factorial(Tj)
return factorial(Kw) * binom(Nw, Kw) * (tmp(T1, T2) + tmp(T2, T1))
def count_cases(T1, Nm, Nw, Kw):
population = [Person('male', idx) for idx in range(Nm)]
population = population + [Person('female', idx) for idx in range(Nw)]
cnt = 0
for perm in itertools.permutations(population):
t1, t2 = perm[:T1], perm[T1:]
cnt += 1 if valid_perm(t1, t2, Kw) else 0
return cnt
def main():
T1, Nm, Nw, Kw = 6, 5, 5, 4
cnt1 = count_cases(T1, Nm, Nw, Kw)
cnt2 = exact_solution(T1, Nm, Nw, Kw)
print(cnt1, cnt2)
if __name__ == '__main__':
main()
Nennen wir die Tische A und B. A hat die 12 Sitze, B 8 Sitze.
Es gibt grundsätzlich 2 vershciedene Fälle:
Fall 1: an A sitzen 6 Frauen und an B 4 Frauen.
Fall 2: an A sitzen 4 und an B sitzen 6 Frauen.
ich würde die Tische bis auf Weiteres separat betrachten:
gehen wir einfahc mal von Fall 1 aus (Fall 2 müssen wir später analog machen).
und betrachten Tisch A:
dort sitzen zwangsläufig 6 Frauen und 6 Männer. (Alle anderne hocken an Tisch B, jetzt aber gerade unwichtig).
Wir haben also 6 "Steckplätze", wo wir Frauen platzieren können.
Und 6 Steckplätze wo wir Männer platzieren können.
Wie viele Möglichkeiten gibt es, aus einem Pool von 10 Frauen 6 Stück, ohne zurücklegen, zu ziehen?
genau. 10*9*8*7*6*5
Wie viele Möglichkeiten gibt es aus 10 Männer 6 stük zu ziehen?
Das Selbe wie eben 10!/4!
beides multiplizieren um alle Ziehungsmlglichkeiten für die Folge
FFFFFFMMMMMM zu kriegen.
nun kann man bei einer vorgegebenen Menge an Frauen und Männern diese noch auf diverse Arten auf den 12 Stühlen verteilen.
Ist einfach die Formel, auf wie viele Arten man 12 vorgegebene leute auf 12 Stühle verteilt.
Musst du die Formal googeln, und das dann mit dem ergebnis von oben wiederum multiplizieren.
somit sind wir mit Tisch A fertig.
Nun zu Tisch B.
Sagen wir einfach mal, wir betrachten eine ganz bestimmte Konstellation von Tisch A.
dann verbleibt ein Pool von 4 Frauen und 4 Männern.
wir gehen analog zu oben vor.
4 frauen aus 4 frauen ziehen? 4!
4 männer aus 4 männer?4!
8 leute auf 8 stühle? keine ahnung, nimm die formel die du oben gegoogelt hast.
alle 3 ausdrücke multiplizieren miteinander. weil ichs nicht ausrechnen will, sagen wir dieses ergebnis aus den 3 termen sei K.
was nun?
wir haben für eine ganz bestimmte feste sitz und personenkosntellation an tishc A bestimmt, wie viele mögliche kombinationen es an Tisch B gibt. nämlich K .
Um nun auf das gesamtertebnis zu kommen, müssen wie alle möglichen kosntellationen von tisch A mit allen kosntellationen für tisch B kombinieren.
heißt den gesamtterm, den wir für A hatten, mit dem gesamtterm (K) für TZisch B multiplizieren.
ergibt uns einen schönen gesamtterm für das Ganze.
Sind wir fertig?
Nö! :-P
Denn das war nur Fall 1!
Nun noch dasselbe für Fall 2!
Und am Ende die Gesamtzahl, die für Fall 1 rauskam, zur Gesamtzahl von Fall 2 addieren.
DAS ist dann das Gesamtergebnis der Aufgabe :-)
Weils vielleicht unverständlich ist was ich oben mit der bestimmten Konstellation für Tisch A und so meine:
Sagen wir mal , wir haben 2 4er Tische.
und haben die Frauen ABCD und die Männer MNOP.
Aus Gründen sollen an Tisch 1 2 Männer und 2 Frauen sitzen.
EINE von vielen Konstellationen für Sitzplatzverteilungen an Tishc 1 könnte
ABMN sein. heißt A sitzt auf Stuhl 1, B auf Stuhl 2, M auf Stuhl 3 , N auf Stuhl 4.
heißt also betreffend Tisch 2:
bei den Frauen verbleiben noch CD, also 2 Stück.
und noch die 2 Männer OP.
Mit den selben Rechnungen wie oben kommen wir auf 2! Möglichkeiten fpr die Männer, 2! für die Frauen.
macht zusammen 2!*2!=4 möglichkeiten.
Jede dieser Möglichkeiten kann abr noch auf den 4 Stühlen hin und her geshcoben werden, sprich: wie kann man 4 Leute auf 4 Stühle verteilen.
Ist der Term den ich oben dich anwies zu googeln, wo ich mir nun aber sicher bin dass er einfach 4! ist.
Also die 4 von eben noch mit 4! multiplizieren:
=4*4!=96 Möglichkeiten irgendwie die noch vorhandenen Frauen und Männer am Tisch 2 zu platzieren.
Jetzt bezogen sich aber diese Tisch 2 berechnungen auf die Annahme dass an Tisch 1 Frauen und Männer in genau der Reihenfolge ABMN sitzen.
Könnte ja auch anders sitzen.
Nämlcih auf genau 4!/2!*4!/2!*4!=3456 Arten.
daher die 96 Kombinationen für Tisch 2 mit den 3456 Möglichkeiten von Tisch 1 kombinieren:
96*3456= 331776 Möglichkeiten.
Aber jetzt, wo ich die großen Zahlen so vor mir sehe, bin ich mir recht sicher dass ich irgendwo einen Denkfehler drin habe :-)
ich glaube fast, die Reihenfolgenbetrachtung ist nicht nötig.
heißt, das "wie verteile ich X Leuten auf Y Stühle" kannst du rauslassen bei den berechnungen.
Rest dürfte stimmen