3
$\begingroup$

The problem: We have N (even) objects ordered $o_1 ... o_N$ , each having their own label. The labels are reassigned to the objects randomly. What is the probability that that neither of the first $N/2$ objects ($o_1 ... o_{N/2}$) are matched with their own label?


My attempt: We use the inclusion-exclusion principle:

$$\mathbb{P}\left(\bigcup_{i=1}^n A_i\right) = \sum_{k=1}^n\left((-1)^{k-1}\sum_{I\subset\{1,...,n\} ; |I|=k} \mathbb{P}(A_I)\right )$$

We let $A_i$ denote the event that object $i$ get's matched with its own label. Then

$$\mathbb{P}\left(\bigcup_{i=1}^{N/2} A_i\right)$$

is the probability that at least one of the first half of the objects gets a match and

$$1 - \mathbb{P}\left(\bigcup_{i=1}^{N/2} A_i\right)$$

is the probability that none of the first half get a match, which is the result we want.

Now for the probability of any combination of $n$ matches from the first half of the objects we have:

$$\sum_{(i_1,...,i_k):1\leq i_1 \leq ... \leq i_k \leq N/2} \mathbb{P}(A_{i_1}\cap ...\cap A_{i_k})$$

And we want to rewrite this using factorial notation:

We have

$$\frac{(N/2)!}{n!(N/2-n)!}$$

possible combinations of matches. For each of those, the probability that that arrangement will happen is $$\frac{(N-n)!}{N!}$$

so we can say:

$$\sum_{(i_1,...,i_k):1\leq i_1 \leq ... \leq i_k \leq N/2} \mathbb{P}(A_{i_1}\cap ...\cap A_{i_k}) = \frac{(N/2)!}{n!(N/2-n)!} \times \frac{(N-n)!}{N!}$$

and then our final answer would be:

$$1 - \sum_{n=1}^{N/2}\left((-1)^{n-1} \frac{(N/2)!}{n!(N/2-n)!} \times \frac{(N-n)!}{N!} \right)$$

Does this make sense? Is there any easier way of solving this?

$\endgroup$
4
  • $\begingroup$ For large (and even modest) $N$, this is approximately the value of the Poisson distribution of mean $\frac{1}{2}$ at zero, namely $\frac{1}{\sqrt{e}} = 0.60653\!\ldots$. en.wikipedia.org/wiki/Poisson_distribution $\endgroup$ Commented Apr 28, 2016 at 19:06
  • $\begingroup$ @Travis I tried it in wolframalpha for N=2000 and got 0.606493. Should I take it as an indication that my answer is correct? $\endgroup$
    – S. Tessa
    Commented Apr 28, 2016 at 19:20
  • $\begingroup$ Agreement to four decimal places is certainly strong evidence. $\endgroup$ Commented Apr 28, 2016 at 19:26
  • $\begingroup$ You can use \ldots instead of ... to get the right spacing. $\endgroup$
    – joriki
    Commented Apr 28, 2016 at 22:38

2 Answers 2

1
$\begingroup$

This makes a lot of sense, and I doubt that there's a significantly easier way of solving this. You basically followed the usual derivation of the number of derangements, and the result in that case, where there's greater symmetry, can't be simplified, so it would be surprising if it could be simplified in this case. The only simplification I see is that you could include $n=0$ in the sum instead of writing the $1$ separately; your result is actually

$$ \sum_{n=0}^{N/2}(-1)^n\frac{(N/2)!(N-n)!}{n!(N/2-n)!N!}\;. $$

$\endgroup$
2
  • $\begingroup$ Do you have an extra factor here or am I misreading things? $\endgroup$ Commented Apr 28, 2016 at 22:52
  • $\begingroup$ @MarkoRiedel: The extra factor $\frac1{N!}$ is there because the question asked for the probability and you gave the count instead; other than that the results are identical. $\endgroup$
    – joriki
    Commented Apr 28, 2016 at 22:54
1
$\begingroup$

This is a classic scenario where the underlying poset has the subsets of $[m]$ (where $n/2=m$) as nodes, order is by set inclusion, and the Mobius function on the nodes is the usual $(-1)^q$ with $q$ the number of elements. Therefore we can just plug these data into the usual inclusion-exclusion formula to get

$$\sum_{q=0}^m {m\choose q} (-1)^q (2m-q)!$$

which is the sequence

$$1, 14, 426, 24024, 2170680, 287250480, \\ 52370755920, 12585067447680,\ldots$$

which is OEIS A033815.

Now this is a very simple problem but just in case we have any sceptics remaining here is a script to help verify the above computation.

with(combinat);

Q :=
proc(m)
local res, perm, pos;
option remember;

    res := 0;

    perm := firstperm(2*m);

    while type(perm, `list`) do
        for pos to m do
            if perm[pos] = pos then
                break
            fi;
        od;

        if pos = m + 1 then
            res := res + 1
        fi;

        perm := nextperm(perm);
    od;

    res
end;

T := m -> add(binomial(m,q)*(-1)^q*(2*m-q)!, q=0..m);
$\endgroup$
2
  • $\begingroup$ Thanks; I wasn't aware of this connection between Möbius inversion and inclusion-exclusion. $\endgroup$
    – joriki
    Commented Apr 28, 2016 at 22:58
  • $\begingroup$ It is a useful exercise and might help the OP in understanding to draw the poset and the Mobius function for the case of set inclusion (case A, size zero is wanted, case B, size $m$ is wanted) and in the case of the divisor poset, where we get the Mobius function from number theory. $\endgroup$ Commented Apr 28, 2016 at 23:01

You must log in to answer this question.

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