0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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!}$ $\endgroup$
    – JMoravitz
    Aug 22, 2018 at 22:20
  • 1
    $\begingroup$ 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?" $\endgroup$
    – JMoravitz
    Aug 22, 2018 at 22:30
  • $\begingroup$ 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. $\endgroup$
    – JMoravitz
    Aug 22, 2018 at 22:34
  • $\begingroup$ 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. $\endgroup$
    – sleeparrow
    Aug 22, 2018 at 23:58
  • $\begingroup$ 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. $\endgroup$
    – sleeparrow
    Aug 23, 2018 at 0:00

1 Answer 1

0
$\begingroup$

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!}$$

These can be found by using inclusion-exclusion and derangement ideas.

$\endgroup$

You must log in to answer this question.

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