What is probability that out of the first half on N objects, none will be matched with their own label?

Question

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?

Answer 1

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!}\;. $$

Answer 2

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