# How to calculate the probability or 50% or more matches on n randomly assigned unique pairs

FTR: This could not be a lower priority question. It's so not important, but I really want to know.

Let's say I have n unique pairs. They are like keys (A) and locks (B), and every one of the n locks can be opened by exactly one of the n keys. And, of course we are completely randomly assigning each key to a random lock to see if it works.

(BTW, it took me an embarrassing amount of counting combinations to figure out the that number of combinations is n!, but, in my defense, I've never actually used factorials in anything.)

So, given n pairs, there are n! possible combinations. How does one calculate the chances that there are at least x correct matches? I'm in particular looking to see the chances for at least one correct match, and for at least 50% correct matches.

I've tried internet searches, but I haven't been able to word it to get what I'm looking for.

I made a spreadsheet and went up to 5-pair combinations. But I have no idea how to turn that data into any kind of formula.

It doesn't paste well, so I'll paste the text and include an image with better formatting.

Total #     Possible       Combs w/      Probability of   Combs with      Probability
of pairs    combinations   matches ≥ 1   matches ≥ 1      matches ≥ 50%   of matches ≥ 50%
1           1              1             100.00%          ?               ?
2           2              1              50.00%          ?               ?
3           6              4              66.67%          ?               ?
4           24             15             62.50%          ?               ?
5           120            73             60.83%          ?               ?


I think I got all the requirements for a well-formed question. If I missed anything, it was accidental, let me know and I'll fix it.

Again, this is not important, just something that's been bugging me.

Thank you for any help you can provide. Especially replies that explain "this is why/how it works this way" In that "teach a person to fish" kinda way.

Chances of correctly matching pairs

• You want to add up rencontres numbers, though for "at least one match" it would be faster to take $n!$ minus derangements Apr 20, 2022 at 22:20
• Here is another related post on MSE. Apr 20, 2022 at 22:37

Let us put the locks in order and draw the keys in a random order (there are $$n!$$ possibilities to do that). We need to compute the number of possible orders such that exactly $$k$$ keys of $$n$$ match the lock. To do this, we will first count all the possible choices of locks which will get the good key: that's exactly $$n\choose k$$.
Then, for each choice of the $$k$$ locks which will get the right key, we need to make sure that the remaining $$n-k$$ locks will get the wrong key. This is equivalent to computing the number of permutations in a set consisting of $$n-k$$ elements such that no number is mapped to itself. These are called derangements and unfortunately they are a rather intricate thing to compute (see the link). The number of derangements is denoted by $$!(n-k)$$. Then the number of possibile orders in which we get exactly $$k$$ matching keys is $$!(n-k){n\choose k}$$ and so the chance of getting exactly $$k$$ matches is $$P({\rm number\ of\ matches} =k) = \frac{!(n-k){n\choose k}}{n!}.$$
• You're right, the part in edit is not correct. The error is that by using my method of counting (pick $k$ good locks and take the rest arbitrary) counts some of the combinations multiple times. I don't have any idea for a simple formula for at least $k$ matches then, thanks for spotting the mistake! I've removed this part now.