Imported the original cryp.to site for re-publishing with ikiwiki.
[cryp.to.git] / kombinatorik-von-mann-und-frau.mdwn
1 [[!meta title="Kombinatorik von Männern und Frauen"]]
2 [[!tag stochastik]]
3
4 ## Die Frage
5
6 8 Männer und 7 Frauen kaufen unabhängig voneinander Karten in derselben
7 Reihe im Theater. Wie viele nebeneinandersitzende Mann-Frau- oder
8 Frau-Mann-Paare erwartet man am Abend der Vorstellung in dieser Reihe?
9
10 ## Die Antwort ...
11
12 ... auf diese Frage hat mehrere Ebenen. Die einfachste davon ist die
13 nach dem Mittelwert --- also nach der Anzahl von Paaren, die bei
14 häufiger Wiederholung dieses Experiments im Durchschnitt auftritt. Auf
15 den ersten beiden Plätzen der Reihe sitzen Mann-Frau oder Frau-Mann mit
16 der Wahrscheinlichkeit
17 $$\frac{8}{15}\cdot\frac{7}{14}+\frac{7}{15}\cdot\frac{8}{14}\;=\;\frac{8}{15}$$
18 nebeneinander. Man erwartet also $\frac{8}{15}$ Paare auf den ersten
19 beiden Plätzen. Dieselbe Anzahl Paare erwartet man natürlich auch auf
20 allen anderen benachbarten Plätzen, und davon gibt es bei 15 Leuten
21 insgesamt 14 verschiedene. Daher erwartet man im Mittel
22 $$14\cdot\frac{8}{15}\;\approx\;7,46$$ Mann-Frau oder Frau-Mann Paare in
23 der besagten Theaterreihe.
24
25 Außerdem läßt sich feststellen, dass nur zwei Anordnungen existieren,
26 MMMMMMMMFFFFFFF und FFFFFFFMMMMMMMM, in denen lediglich ein Paar
27 nebeneinandersitzt. In allen anderen Reihenfolgen gibt es mehrere Paare.
28
29 Das Maximum von 14 Paaren erreicht die Anordnung MFMFMFMFMFMFMFM. Da es
30 sich dabei aber nur um eine unter $$\frac{15!}{8!\cdot{}7!}\;=\;6\,435$$
31 möglichen Reihenfolgen der 8 Männer und 7 Frauen handelt, tritt dieser
32 Fall selten auf.
33
34 Allgemeinen kann jede Anordnung dadurch vereinfacht werden, dass alle
35 belanglosen Mann-Mann und Frau-Frau Paare zu jeweils einer Person
36 zusammengefasst werden. Dadurch zeigt sich, dass scheinbar verschiedene
37 Anordnungen in Wahrheit nur eine Variation desselben Musters sind. Zur
38 Illustration sind im folgenden alle 2-Paar-Kombinationen von 5 Männer
39 und 4 Frauen angegeben:
40
41 > <table border="0" cellspacing="2" cellpadding="2">
42 >   <tr align="center"> <td>MMMMFFFFM</td> <td>&rArr;</td> <td>MFM</td> </tr>
43 >   <tr align="center"> <td>MMMFFFFMM</td> <td>&rArr;</td> <td>MFM</td> </tr>
44 >   <tr align="center"> <td>MMFFFFMMM</td> <td>&rArr;</td> <td>MFM</td> </tr>
45 >   <tr align="center"> <td>MFFFFMMMM</td> <td>&rArr;</td> <td>MFM</td> </tr>
46 >   <tr align="center"> <td>FMMMMMFFF</td> <td>&rArr;</td> <td>FMF</td> </tr>
47 >   <tr align="center"> <td>FFMMMMMFF</td> <td>&rArr;</td> <td>FMF</td> </tr>
48 >   <tr align="center"> <td>FFFMMMMMF</td> <td>&rArr;</td> <td>FMF</td> </tr>
49 > </table>
50
51 Alle möglichen Anordnungen mit 2-Paaren lassen sich also auf zwei Muster
52 reduzieren: MFM und FMF. Genauso lassen sich die Lösungen für andere
53 Anzahlen von Paaren stark vereinfachen:
54
55 > <table border="0" cellspacing="2" cellpadding="2">
56 >   <tr align="center"> <td>Paare</td> <td>vereinfachte Lösungen</td> </tr>
57 >   <tr align="center"> <td>1</td> <td>MF, FM</td> </tr>
58 >   <tr align="center"> <td>2</td> <td>MFM, FMF</td> </tr>
59 >   <tr align="center"> <td>3</td> <td>MFMF, FMFM</td> </tr>
60 >   <tr align="center"> <td>4</td> <td>MFMFM, FMFMF</td> </tr>
61 >   <tr align="center"> <td>5</td> <td>MFMFMF, FMFMFM</td> </tr>
62 >   <tr align="center"> <td>6</td> <td>MFMFMFM, FMFMFMF</td> </tr>
63 >   <tr align="center"> <td>7</td> <td>MFMFMFMF, FMFMFMFM</td> </tr>
64 >   <tr align="center"> <td>8</td> <td>MFMFMFMFM</td> </tr>
65 > </table>
66
67 In einer Anordnung entstehen jedesmal 2 Paare, wenn eine Frau zwischen
68 zwei Männern sitzt (oder ein Mann zwischen zwei Frauen). Ein einzelnes
69 Paar kann hingegen nur am Rand entstehen. Sitzen an den Außenpositionen
70 jeweils zwei Männer oder zwei Frauen, dann ist die Anzahl der
71 entstehenden Paare gerade. Sitzen an den Außenpositionen aber jeweils
72 ein Mann und eine Frau, dann entsteht eine ungerade Anzahl von Paaren.
73
74 Eine beliebige Anordnung von $m$ Männern und $n$ Frauen mit $k$ Paaren
75 läßt sich wie folgt erzeugen. Wenn $k=2i+1$ ungerade ist, dann sitzen
76 auf den beiden Außenplätzen Personen mit verschiedenem Geschlecht. Für
77 diese Sitze gibt es also nur 2 Möglichkeiten. Darüber hinaus werden die
78 Plätze besetzt, indem man aus den $m-1$ möglichen Sitzen zwischen den
79 Männern genau $i$ auswählt, auf denen Frauen sitzen müssen (um
80 $2i+1=k$ Paare zu erzeugen). Aus Perspektive der Frauen findet
81 gleichzeitig derselbe Vorgang statt. Wir wählen aus den $n-1$ möglichen
82 Plätzen zwischen den Frauen genau $i$ aus, auf denen Männer sitzen
83 müssen (um $2i+1=k$ Paare zu erzeugen). Die Anzahl aller Anordnungen mit
84 $k$ Paaren ist die Vereinigung (das Produkt) beider Möglichkeiten:
85
86 $$2\,\binom{m-1}{i}\,\binom{n-1}{i}.$$
87
88 Für gerade $k=2i$ sind zwei Fälle zu unterscheiden. Einmal sitzen auf
89 den beiden Außenpositionen zwei Männer. Es sind also aus $m-1$ möglichen
90 Sitzen zwischen den Männern genau $i$ mit Frauen zu besetzen. Aus den
91 $n-1$ möglichen Plätzen zwischen den Frauen sind aber nur $i-1$ für
92 Männer zu vergeben, denn 2 Männer sind fest für die Außenpositionen
93 eingeplant. Im anderen Fall sitzen Frauen auf den Außenpositionen: dann
94 sind aus $n-1$ möglichen Plätzen zwischen den Frauen $i$ mit Männer
95 besetzt, von den $m-1$ Plätzen zwischen den Männern aber nur $i-1$ mit
96 Frauen. Es gibt somit insgesamt
97 $$\binom{m-1}{i}\,\binom{n-1}{i-1}+\binom{m-1}{i-1}\,\binom{n-1}{i}$$
98 mögliche Anordnungen.
99
100 Als Schmankerl erhält man aus diesen Überlegungen sogar noch eine
101 überraschende Gleichung. Die Wahrscheinlichkeit dafür, dass eine
102 bestimmte Anzahl von Paaren entsteht, gleicht dem Verhältnis von
103 günstigen Anordnungen zu möglichen Anordnungen, und diese Informationen
104 sind uns inzwischen bekannt. Weiterhin ist der Erwartungswert definiert
105 als Summe aller möglichen Anzahlen von Paaren jeweils gewichtet mit der
106 Wahrscheinlichkeit, dass diese konkrete Anzahl von Paaren auftritt:
107
108 $$\sum\limits_{k=0}^\infty \,k\,p(X=k).$$
109
110 Auf unseren konkreten Fall angewendet ist diese Summe sehr beeindruckend
111 (siehe weiter unten). Das Ergebnis dieser Summe --- der Erwartungswert
112 --- ist uns jedoch bereits bekannt, nämlich
113 $$(m+n-1)\,\left(\frac{m}{n+m}\,\frac{n}{n+m-1}+\frac{n}{n+m}\,\frac{m}{n+m-1}\right).$$
114
115 Daher wissen wir, dass diese komplizierte Summe am Ende nichts anderes
116 bedeutet als $\frac{2mn}{n+m}$. Sollte es einem der geneigten Leser
117 gelingen, diese Gleichung algebraisch herzuleiten, dann würde ich mich
118 freuen, wenn er oder sie sich die Zeit nähme, mir den Beweis
119 mitzuteilen.
120
121 $$\sum\limits_{i=0}^{\left\lfloor{\frac{m+n-1}{2}}\right\rfloor}\frac{(2i+1)\left(2\,\binom{m-1}{i}\,\binom{n-1}{i}\right)+2i\left(\binom{m-1}{i}\,\binom{n-1}{i-1}+\binom{m-1}{i-1}\,\binom{n-1}{i}\right)}{\frac{(m+n)!}{m!\,n!}}\;=\;{\frac{2\,m\,n}{n+m}}$$