Probability for pairing up A set of 200 people, consisting of 100 men and 100 women, is randomly divided into 100 pairs of 2 each. Give an upper bound to the probability that at most 30 of these pairs will consist of a man and a woman.
I intend to use the Chebyshev Inequality to solve it but it turns out that the prob. dist. for # of pairs consisting of a man and a woman is hard to find.
Anyone have any thought on it? Thanks a lot!
 A: Making two columns, one for the left element of each pair, one for the right, there are $\binom{100}{k}$ ways to have $k$ men and $100-k$ women in the left column.
For each arrangement of $k$ men on the left, there are $\binom{k}{n}$ ways to match $n$ men and $k-n$ women in the right column with the $k$ men in the left column.  There are $\binom{100-k}{n}$ ways to match $n$ women and $100-k-n$ men in the right column with the $100-k$ women in the left column.
Thus, there are $\binom{100}{k} \binom{k}{n} \binom{100-k}{n}$ ways to get $100-2n$ man-woman couples with $k$ men in the left column.  Considering the permutations of the $200$ taken $100$ at a time, the total number of arrangements should be $\binom{200}{100}$.  Let's check
$$
\begin{align}
\sum_k\sum_n \binom{100}{k} \binom{k}{n} \binom{100-k}{n}
&= \sum_k \binom{100}{k} \binom{100}{k}\\
&= \binom{200}{100}
\end{align}
$$
Now the number of arrangements with $100-2n$ man-woman couples is
$$
\begin{align}
\sum_k \binom{100}{k} \binom{k}{n} \binom{100-k}{n}
&= \sum_k \binom{100}{2n} \binom{2n}{n} \binom{100-2n}{k-n}\\
&= \binom{100}{2n} \binom{2n}{n} 2^{100-2n}
\end{align}
$$
Thus, the probability of getting exactly $100-2n$ man-woman couples is
$$
\frac{\binom{100}{2n} \binom{2n}{n} 2^{100-2n}}{\binom{200}{100}}
$$
Summing for $n=35\dots50$ yields the probability of getting at most $30$ man-woman couples to be $p=.000046649665489730847082$.
Interestingly, the probability of matching at most $48$ man-woman couples is $p=.40103407701938908115$ and the probability of matching at most $50$ man-woman couples is $p=.55961680234890506571$.
A: Let there be $n$ men and $n$ women. Consider a pairing with $k_{m,m}$ man-man pairs, $k_{w,w}$ woman-woman pairs, $k_{m,w}$ and $k_{w,m}$ opposite gender pairs. Total number of pairs $k_{m,m}+k_{w,w}+k_{m,w}+k_{w,m} = n$. Total number of men and women respectively $2 k_{m,m} + k_{m,w}+k_{w,m} = n$ and $2 k_{w,w} + k_{m,w}+k_{w,m} = n$. It follows that $k_{m,m}=k_{w,w}$. This configuration can be built by splitting $n$ men into $\binom{n}{2 k_{m,m}}$ partitions of $2 k_{m,m} + (n-2k_{m,m})$, likewise for women. $2 k_{m,m}$ men are permuted in $(2k_{m,m})!$ ways, and remaining men permuted in $(n-2k_{m,m})!$ ways. Resulting $n$ pairs can be rearranged in $\mathrm{multinom}(k_{m,m},k_{w,w}, k_{m,w}, k_{w,m})$ ways.
So we have 
$$
 (2n)! = \sum_{k_{m,m}, k_{m,w}, k_{w,m} >=0 } \chi_{2 k_{m,m}+k_{m,w}+k_{w,m}=n}  \left( \binom{n}{2 k_{m,m}} (2k_{m,m})! (n- 2k_{m,m})! \right)^2 \mathrm{multinom}(k_{m,m},k_{w,w}, k_{m,w}, k_{w,m})
$$
Which is 
$$
   1 = \frac{1}{\binom{2n}{n}} \sum_{k_{m,m}, k_{m,w}, k_{w,m} >=0 } \chi_{2 k_{m,m}+k_{m,w}+k_{w,m}=n} \mathrm{multinom}(k_{m,m},k_{w,w}, k_{m,w}, k_{w,m})
$$
Now to find the requested probability we restrict the summation to $k_{m,w}+k_{w,m} <= 30$.
This gives
In[114]:= With[{n = 100}, (n!)^2/(2 n)! Sum[
   Boole[2 k + m + w == n] Boole[m + w <= 30] Multinomial[k, k, m, 
     w], {k, 0, n}, {m, 0, n}, {w, 0, n}]]

Out[114]= \
1918296922985300702931961626782543256990306077/\
41121343590504031983862003937481222553223476334365

which approximately is $0.0000466497$.
A: One may also use Cantelli inequality (one-sided version of Chebyshev):
$$P(X\leq 30)\leq \frac{Var(X)}{Var(X)+(E(X)-30)^2}\approx \frac{25.12}{25.12+410.10}\approx 0.0577$$
However it's not much better than Chebyshev :) 
