# Formula for the probabilities of guessing x correct pairings

Suppose:

• we have a set A with n elements
• we have a set B with n elements
• every element in A has exactly one "friend" in B
• every element in B has exactly one "friend" in A
• someone blindly guesses x pairings correctly
• p is the probability of guessing x pairings correctly

How might one calculate each p for x=0 to x=n?

Sorry in advance if there is a better way to word this problem; I am not a mathematician.

• It sounds as though you are asking for the probability that a permutation selected uniformly at random from $S_n$ contains precisely $x$ fixed points. There are $\binom{n}{x}\cdot !(n-x)$ permutations with $x$ fixed points, where $!k$ counts the number of derangements of $k$ elements. This would make the probability $\dfrac{\binom{n}{k}\cdot !(n-k)}{n!}$ Aug 22, 2018 at 22:20
• A more common description of the problem that my previous comment answers is the following "There are $n$ envelopes each uniquely labeled with a number from $\{1,2,\dots,n\}$ and there are similarly $n$ pieces of paper each uniquely labeled with a number from $\{1,2,\dots,n\}$. We randomly place each piece of paper into an envelope so that each envelope receives exactly one piece of paper. What is the probability that exactly $x$ envelopes contain the piece of paper with the corresponding matching number?" Aug 22, 2018 at 22:30
• Note: in the phrasing you currently have posted, you specify that "every element in $A$ has exactly one 'friend' in $B$" however you didn't mention whether or not each element in $B$ has exactly one 'friend' in $A$. Supposing $A$ is a set of boys: Al, Ben, Charles, ... and $B$ is a set of girls: Alice, Betty, Candice, ... it is possible that every boy is friends with Alice, meanwhile Betty, Candice, etc... all have no male friends. You also didn't adequately describe how the person guesses the pairings, leading to ambiguity there too. Aug 22, 2018 at 22:34
• Thanks for the comments! The first one is over my head but I'm trying to digest it. You're absolutely right in your third comment. I'll edit the question. Aug 22, 2018 at 23:58
• You also didn't adequately describe how the person guesses the pairings, leading to ambiguity there too. Could you recommend a better wording for this? I thought "blindly" sufficed, but correct me if I'm wrong. Aug 23, 2018 at 0:00

Probability that at least one pairing is correct (probability that at least one letter is placed in the correct envelope) $$=$$ $$\sum_{k=1}^{k=n} \frac{(-1)^{k+1}}{k!}$$
Probability that exactly x pairings are correct (that exactly x letters are placed in the correct envelope) $$=$$ $$\frac{1}{x!}\sum_{k=0}^{k=n-x} \frac{(-1)^k}{k!}$$