15
$\begingroup$

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.

$\endgroup$
11
  • 1
    $\begingroup$ Can two boys choose the same girl or two girls choose the same boy? $\endgroup$
    – JiK
    Commented Oct 20, 2014 at 7:37
  • $\begingroup$ It’s not derangements, despite the resemblance. This doesn’t really help, but in essence you’re choosing at random two functions, $f$ and $g$, from $[12]$ to $[12]$ and asking for the probability that the composition $f\circ g$ has no fixed point. $\endgroup$ Commented Oct 20, 2014 at 7:44
  • $\begingroup$ Correction: If the functions have to be bijections, it is of course precisely derangements, but as worded it's not. $\endgroup$ Commented Oct 20, 2014 at 7:56
  • $\begingroup$ @JiK I presume yes. But one girl can choose only one boy and vice versa. $\endgroup$ Commented Oct 20, 2014 at 8:01
  • $\begingroup$ @BrianM.Scott Can't it be considered as just one function $f:\text{Boys} \rightarrow \text{Girls}$? Why two? It won't be a bijection though.. $\endgroup$ Commented Oct 20, 2014 at 8:04

3 Answers 3

8
$\begingroup$

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

$$\begin{align*} \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\;; \end{align*}$$

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

$\endgroup$
2
  • $\begingroup$ Extremely interesting! Did not think of it that way! $\endgroup$ Commented Oct 20, 2014 at 22:05
  • $\begingroup$ @Studentmath: I noticed it when I started doing some numerical calculations. $\endgroup$ Commented Oct 20, 2014 at 22:09
7
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Yes..that is pretty neat. $\endgroup$ Commented Oct 20, 2014 at 17:55
  • $\begingroup$ Try to extend it for $n$ boys and $n$ girls - the summation is still simple then! $\endgroup$ Commented Oct 20, 2014 at 17:57
  • 1
    $\begingroup$ Sure I will. But later, when I get time, because it is time to sleep here in my ccountry.. $\endgroup$ Commented Oct 20, 2014 at 18:00
  • $\begingroup$ "Detonating" events is ever funny :D. Just joking, very clear approach and interesting explanation. Ty. $\endgroup$
    – Masacroso
    Commented Oct 20, 2014 at 18:23
  • $\begingroup$ @Masacroso wops, thanks for pointing that out! $\endgroup$ Commented Oct 20, 2014 at 18:45
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Yes, this is how I generated the figures for $n=2$ and $n=3$. $\endgroup$ Commented Oct 20, 2014 at 20:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .