91Ó°ÊÓ

Each of $n$boys and$n$girls, independently and randomly, chooses a member of the other sex. If a boy and girl choose each other, they become a couple. Number the girls, and let $G_i$be the event that girl number $i$is part of a couple. Let $P_0=1-P\left({∪}_{i=1}^n{G}_i\right)$be the probability that no couples are formed.

We have that,

$P\left(G_i\right)=\underset{k=1}{\overset{n}{∑}}P\left(G_iâˆ\pounds i\right.$th girl chooses kth boy $)P(i$th girl chooses kth boy $)$

$=\underset{k=1}{\overset{n}{∑}}\frac{1}{n}·\frac{1}{n}=n·\frac{1}{n^2}=\frac{1}{n}$

We know that$P\left(G_iâˆ\pounds \right.$$i$th girl chooses kth boy $)=\frac{1}{n}$since if $ith$girl chooses kth boy $)=\frac{1}{n}$since if $ith$girl chooses $kth$boy, they will become a couple if any only if $kth$boy has chosen $ith$girl and probability for that is$1/n.$

$P\left(G_i\right)=$$\frac{1}{n}$

Each of $n$ boys and $n$ girls, independently and randomly, chooses a member of the other sex. If a boy and girl choose each other, they become a couple. Number the girls, and let$G_i$ be the event that girl number $i$ is part of a couple. Let $P_0=1-P\left({∪}_{i=1}^n{G}_i\right)$ be the probability that no couples are formed.

If we are given that $j$girl is in a couple with some boy, we can exclude them from the story. So, we remain with $n-1$boys and $n-1$girls. Here we can repeat the story from part (a), so the required probability is

$P\left(G_iâˆ\pounds G_j\right)=\frac{1}{n-1}$

The required probability is

$P\left(G_iâˆ\pounds G_j\right)=\frac{1}{n-1}$

Each of $n$boys and $n$ girls, independently and randomly, chooses a member of the other sex. If a boy and girl choose each other, they become a couple. Number the girls, and let$Gi$ be the event that girl number $i$is part of a couple. Let $P0=1−P(∪ni=1Gi)$ be the probability that no couples are formed.

Define random variable $X$that counts how many of events $G_i$are active. The average number of active events is 1 since we have that each of $G_i$is active with the probability $1/n$. So, we can approximate $X~$Pois $\left(1\right)$. Hence

$P_0≈P(X=0)=e^{-1}$

$P_0≈P(X=0)=e^{-1}$

Each of $n$boys and $n$girls, independently and randomly, chooses a member of the other sex. If a boy and girl choose each other, they become a couple. Number the girls, and let $Gi$ be the event that girl number$i$is part of a couple. Let$P0=1−P(∪ni=1Gi)$be the probability that no couples are formed.

Using the same notation and idea from part (c), we get

$P_k≈P(X=k)=\frac{1^k}{k!}{e}^{-1}=\frac{1}{k!·e}$

$P_k≈P(X=k)=\frac{1^k}{k!}{e}^{-1}=\frac{1}{k!·e}$

Each of $n$boys and $n$ girls, independently and randomly, chooses a member of the other sex. If a boy and girl choose each other, they become a couple. Number the girls, and let$Gi$ be the event that girl number $i$ is part of a couple. Let $P0=1−P(∪ni=1Gi)$ be the probability that no couples are formed.

Use inclusion-exclusion formula to obtain that

$P\left({∪}_{i=1}^n{G}_i\right)=\underset{i_1}{∑}P\left(G_{i_1}\right)-\underset{i_1<i_2}{∑}P\left(G_{i_1},G_{i_2}\right)+⋯+(-1{)}^{k+1}$

$\underset{i_1<i_2<⋯<i_k}{∑}P\left(G_{i_1},G_{i_2},…,G_{i_k}\right)+⋯+(-1{)}^{n+1}P\left(G_1,G_2,…,G_n\right)$

$=n·P\left(G_1\right)-\left(\begin{array}{l}n\\ 2\end{array}\right)P\left(G_1,G_2\right)+\left(\begin{array}{l}n\\ 3\end{array}\right)P\left(G_1,G_2,G_3\right)$

$-⋯+(-1{)}^{n+1}P\left(G_1,G_2,…,G_n\right)$

$=n·\frac{1}{n}-\frac{n(n-1)}{2}·\frac{1}{n(n-1)}+\frac{n(n-1)(n-2)}{3!}·\frac{1}{n(n-1)(n-2)}-…$

$=1-\frac{1}{2}+\frac{1}{3!}-\frac{1}{4!}+⋯+\frac{(-1{)}^{n+1}}{n!}$

The probability $P\left(G_{i_{1}}, G_{i_{2}}, \ldots, G_{i_{k}}\right)$ can be obtained using the similar argument as in part (b). Finally, we have that

$P_0=1-\left(1-\frac{1}{2}+\frac{1}{3!}-\frac{1}{4!}+⋯+\frac{(-1{)}^{n+1}}{n!}\right)$

$P_0=1-\left(1-\frac{1}{2}+\frac{1}{3!}-\frac{1}{4!}+⋯+\frac{(-1{)}^{n+1}}{n!}\right)$