Couple Probability

The problem states that there are 12 boys and 12 girls. Each boy chooses a girl at random and each girl chooses a boy at random. If a boy and a girl choose each other, they form a couple. It then asks to find the probability that no couple is formed.

How should we approach such problems? I get a hint of derangements, but I am not able to apply it. Please help me out. Thank you.

Solution 1:

Probably the best way to solve this question is by computing the completing probability by inclusion-exclusion, as there are far too many dependencies here. It won't give us a nice immediate result, but it does give us a nice summation that is easy to use in this case.

It's enough to consider one side - i.e. only the girls or the boys, when checking how many couples have formed. So let $E_i$ be the event where the $i$th girl is in a couple. For a given $i$, she has $12$ options of choice, and each of them has $12$ options of choise as well - that meanst $12^2$ options of choice in total for a given $i$. Out of them, there are 12 ways to form a couple - each with a different boy. So we have:

$$P(E_i)=\frac{12}{12^2}$$

We are looking for $P(E_1\cup E_2 \cup \dots\cup E_{12})$.

We also have for $i\neq j$:

$$P(E_i\cap E_j)=\frac{12*11}{12^2*12^2}=\frac{12*11}{12^4}$$

As the second one has 11 relevant options out of the total $12^2$. Continuing this way, we reach via inclusion/exclusion:

$$P(E_1\cup E_2 \cup \dots\cup E_{12})=\sum_{i=1}^{12}(-1)^{i-1} {12\choose i}\frac{12*11*\dots *(12-i+1)}{12^{2i}}$$

Which is not that bad to compute. For further exercise, try to extend this summation for the case of $n$ boys and $n$ girls.

Solution 2:

Generalizing Studentmath’s result to $n$ boys and $n$ girls, we have the probability of at least one match being

$$\sum_{k=1}^n(-1)^{k-1}\binom{n}k\frac{n!}{n^{2k}(n-k)!}=\sum_{k=1}^n(-1)^{k-1}\binom{n}k^2\frac{k!}{n^{2k}}=\sum_{k=1}^n\frac{(-1)^{k-1}}{k!}\prod_{i=0}^{k-1}\left(\frac{n-i}n\right)^2\;;$$

call this $p_n$. Note that the first few terms are

$$1-\frac{(n-1)^2}{2!n^2}+\frac{(n-1)^2(n-2)^2}{3!n^4}-\frac{(n-1)^2(n-2)^2(n-3)^2}{4!n^6}\;,$$

or approximately

$$1-\frac1{2!}+\frac1{3!}-\frac1{4!}$$

when $n$ is large. Fix a positive integer $m$. Plainly $$\prod_{i=0}^{k-1}\left(\frac{n-i}n\right)^2$$ decreases as $k$ increases from $1$ to $n$, so

$$\left|\sum_{k=m+1}^n(-1)^{k-1}\binom{n}k^2\frac{k!}{n^{2k}}\right|\le\frac1{(m+1)!}\prod_{i=0}^m\left(\frac{n-i}n\right)^2<\frac1{(m+1)!}\;.$$

By taking $n$ large enough, we can make the approximation

$$\sum_{k=1}^m(-1)^{k-1}\binom{n}k^2\frac{k!}{n^{2k}}\approx\sum_{k=1}^m\frac{(-1)^{k-1}}{k!}$$

as close as we like and hence get

$$\left|p_n-\sum_{k=1}^m\frac{(-1)^{k-1}}{k!}\right|<\frac1{(m+1)!}\;.$$

Finally, $$\sum_{k\ge 1}\frac{(-1)^{k-1}}{k!}=1-\frac1e\;,$$

so $p_n\to1-\dfrac1e$ as $n\to\infty$, and the probability of getting no match approaches $\dfrac1e$.

Solution 3:

An effort that is an $\epsilon$ progress (maybe) in trying to solve it.

The choices of the boys induce a 12-tuple $x_1, x_2, \ldots, x_{12}$ where $x_i$ denotes the number of boys that have picked girl $i$, such that $$x_1+x_2+\ldots+x_{12}=12$$ Now, girl $1$ may pick $12-x_1$ names (without forming a couple) and so on, so that the probability of no couple formation given the 12-tuple of the $x_i$'s is $$\begin{align*}\frac{(12-x_1)(12-x_2)\ldots(12-x_{12})}{12^{12}}=\left(1-\frac{x_1}{12}\right)\left(1-\frac{x_2}{12}\right)\ldots\left(1-\frac{x_{12}}{12}\right)\end{align*}$$ The probability of a certain 12-tuple $x_1,x_2, \ldots, x_{12}$ is equal to $$\left(\dfrac{1}{12}\right)^{x_1}\left(\dfrac{1}{12}\right)^{x_2}\ldots\left(\dfrac{1}{12}\right)^{x_n}=\left(\dfrac{1}{12}\right)^{\sum_{i=1}^{12}x_i}=\left(\dfrac{1}{12}\right)^{12}$$ that is, each 12-tuple is equiprobable. Thus the requested probability is equal to $$\sum_{x \in S}\left(\dfrac{1}{12}\right)^{12}\left(1-\frac{x_1}{12}\right)\left(1-\frac{x_2}{12}\right)\ldots\left(1-\frac{x_{12}}{12}\right)$$

where $$S:=\{x\in\mathbb R^{12}: \sum_{i=1}^{12}x_i=12, x_i \in \mathbb N\}$$

There are of course $12^{12}$ different elements in $S$. However we are not interested in the relative position of the numbers in the 12-tuple but only in their absolute values, since for example the 12-tuples $(11,1,0,\ldots,0)$ and $(1,0,11,0,\ldots,0)$ will induce the same result. So, actually one has to count the different 12-tuples, without caring of their distribution (one can assume that the values of the $x_i$'s are descending) and then count how many there are from each kind. For example one can start with

• $(12,0,0,\ldots,0)$ and there are 12 such tuples,
• $(11,1,0,\ldots,0)$ and there are $?$ such tuples,
• $(10,1,1,0,\ldots,0)$ and there are $?$ such tuples.
• $\ldots$
• $(1,1,1,\ldots,1)$ and there are $12!$ such tuples.

However this process does not seem to be very simple. But perhaps there exists an efficient way to tackle the summation (which now does not come to my mind).