Probability for pairing up

Chebyshev's inequality is the way to go here, though it is overly conservative. Following André's suggestion, the number of couples $X$ is written as $X=\sum_{i=1}^{100}X_i$ where $X_i$ is the indicator of whether woman $i$ is paired with a man. These random variables are exchangeable, which reduces the computations somewhat.

It is easy to see that $\mathbb{E}(X_i)=100/199$ since there are 100 men out of 199 people to choose as the partner of woman $i$. Therefore, the average number of couples is $$\mathbb{E}(X)=100\times {100 \over 199}=50.251.$$

To get the variance we first calculate $\mathbb{E}(X_i X_j)=(100/199)(99/197)$ when $i\neq j$. Therefore $$ \mathbb{E}(X^2)=\sum_i \mathbb{E}(X_i)+\sum_{i\neq j} \mathbb{E}(X_i X_j) =\left(100\times {100 \over 199}\right)+\left(100\times 99\times {100\over199}{99\over 197}\right).$$ This gives us $$\mbox{Var}(X)=\mathbb{E}(X^2)- \mathbb{E}(X)^2= {196020000\over 7801397}= 25.12626905.$$

By Chebyshev's inequality we get $$\mathbb{P}(X\leq 30)\leq {\mathbb P}(|X-\mathbb{E}(X)|\geq 30-50.251)\leq {\mbox{Var}(X)\over(30-50.251)^2}=.0612.$$ This gives you an upper bound.

In fact you can calculate the exact probability as follows. First for $1\leq m \leq 100$ we have $$\mathbb{E}(X_{1}X_{2}\cdots X_{m})={100\over 199}\times{99\over 197}\times \cdots\times{101-m\over 201-2m}.$$ By exchangeability, the probability is the same for any set of $m$ distinct indices.

Using the inclusion exclusion formula $$\mathbb{P}(X\geq k)=\sum_{m=k}^{100}(-1)^{m-k}{m-1\choose m-k}{100\choose m}\mathbb{E}(X_{1}X_{2}\cdots X_{m}),$$ we find that the probability that there are 31 or more couples is $$\mathbb{P}(X\geq 31)={41119425293581046683159071975854440009966486028288 \over 41121343590504031983862003937481222553223476334365}=.9999533503.$$ The exact probability that there are no more than 30 couples is thus only $.0000466497$.

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$.

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$.

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 :)