Ein Problem aus der Kombinatorik

Da ich in diesem Blog so wenig über Mathematik schreibe, habe ich mir gedacht, ich poste hier meine Lösung zu einem Problem aus der Kombinatorik, das mir am 1. Februar 2018 gestellt worden ist. Das Problem lautete:
20 people work in an office, and the boss is about to select six people at random to form a committee. What are the chances that Albert and Bilbert both end up on that committee?
Die Lösung:
Zu Ihrer Frage: Ich werde sie gleich für den allgemeinen Fall beantworten. Für Ihren speziellen Fall gilt: 
n := 20
k := 6
p := 2 
Es gibt insgesamt n choose k Möglichkeiten, wie man aus einer Gesamtmenge von n Personen Gruppen mit k Mitgliedern bilden kann (siehe Wikipedia, Stichwort "Binomialkoeffizient"). Uns interessiert, wie viele von diesen Möglichkeiten die p angegebenen Personen beinhalten. Dazu rechnen wir aus, wie viele Möglichkeiten mindestens eine dieser p Personen nicht beinhalten, und subtrahieren diesen Wert von n. Wie viele Möglichkeiten beinhalten genau eine bestimmte dieser p Personen nicht? Ganz einfach: (n - 1) choose k. Diesen Wert müssen wir mit p multiplizieren, um alle p Personen abzudecken. Nun gibt es (n - p) choose k Möglichkeiten, wie Gruppen zu k Personen gebildet werden können, ohne dass auch nur eine der p genannten Personen darin vorkommt. Diese Anzahl müssen wir mit p - 1 multiplizieren und von p * ((n - 1) choose k) abziehen, um alle "Duplikate" zu eliminieren (denn diese Möglichkeiten sind in jeder Menge von (n - 1) choose k Möglichkeiten "enthalten", wir haben sie also (p - 1)-mal zu oft gezählt). 
Das ergibt als Formel:
1 - (p * ((n - 1)! / (k! * (n - 1 - k)!) - ((p - 1) * (n - p)! / (k! * (n - p - k)!)) / (n! / (k! * (n - k)!)) 
In Ihrem speziellen Fall lautet das Ergebnis:
1 - (54264 - 18564) / 38760 = 1 - 35700 / 38760 = 1 - 35 / 38 = ca. 8% 
Ich muss sagen: kein triviales Beispiel. Es hat mich einiges an Zeit und Energie gekostet, diese Lösung zu finden. Danke für die Herausforderung!

Kommentare

Beliebte Posts aus diesem Blog

The Demoscene

Digital Art Natives

Autobiographical Sketch